Surjektivität von \phi < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:49 Fr 07.12.2007 | | Autor: | freki |
| Aufgabe | | Ich möchte zeigen, dass eine Standardnummerierung [mm] \phi [/mm] der berechenbaren Funktionen _nicht_ surjektiv sein kann. |
[Anmerkung: das gehört eigentlich in das Unterthema "Berechenbarkeit" der Theoretischen Informatik, ein solches Forum habe ich aber nicht gefunden.]
Sei [mm] \phi: \IN \to P^{(1)} [/mm] eine Standardnummerierung der partiell berechenbaren einstelligen Zahlenfunktionen [mm] ("P^{(1)}"). [/mm] Es ist ohne weiteres möglich, eine solche surjektiv zu definieren (z.B. über eine Nummerierung aller Band- (oder Turing-)maschinen). Dann ist z.B. [mm] \phi(i) [/mm] die von der i-ten Bandmaschine berechnete Zahlenfunktion, und [mm] \phi(i)(j) [/mm] ist der Wert, den die i-te Bandmaschine bei Eingabe von j berechnet (falls er existiert).
Jetzt habe ich mir folgenden Beweis ausgedacht:
Ich definiere eine Funktion h mit h(i) = [mm] \phi(i)(i) [/mm] + 1 [1].
Dann ist h eine berechenbare Funktion, also gibt es ein k [mm] \in \IN [/mm] mit [mm] \phi(k) [/mm] = h [2].
(denn [mm] \phi [/mm] ist ja surjektiv).
Dann ist [mm] \phi(k)(k) [/mm] =[wegen 2] h(k) =[wegen 1] [mm] \phi(k)(k) [/mm] + 1.
Widerspruch! Also ist [mm] \phi [/mm] nicht surjektiv.
Ich habe aber gelernt, dass die Standardnummerierung von P(1) surjektiv ist (was man sich ja auch veranschaulichen kann, wenn man das Alphabet der Turingmaschinen lexikographisch auflistet, erreicht man irgendwann jede Turingmaschine und damit jede berechenbare Funktion).
Ergo stimmt etwas mit dem "Beweis" nicht. Ich denke, es hat mit der Tatsache zu tun, dass [mm] \phi(i)(j) [/mm] ja nicht unbedingt definiert sein muss, also die Funktion h nicht unbedingt berechenbar sein muss, aber wie drückt man das mathematisch aus? Oder was stimmt nicht mit dem Beweis?
MfG, freki
Für die Akten: Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt - diese Frage ging also nicht als Mail, als Feed, als Usenet-Beitrag, als ftp-Upload oder in sonst sonstiger Form binärverschlüsselt über meine Leitung  .
Geht noch nicht, also nochmal:
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt .
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:06 Mo 10.12.2007 | | Autor: | Gilga |
Kann es sein, dass du nachgewiesen hast:
Es gibt eine totale Funktion die nicht berechenbar ist?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:23 Mi 26.12.2007 | | Autor: | freki |
> Kann es sein, dass du nachgewiesen hast:
> Es gibt eine totale Funktion die nicht berechenbar ist?
Leider habe ich deine Antwort erst jetzt gesehen (die Eigenheiten der Forensoftware hier muss ich erst noch erlernen). Es ist schon möglich, dass ich etwas Anderes nachgewiesen habe.
Der Schritt:
.... ich definiere eine Funktion h...
zu
... also ist h berechenbar ...
scheint mir jedenfalls problematisch zu sein. Da [mm] \phi [/mm] nur partielle Funktionen enthält, ist [mm] \mu-Rekursion [/mm] ja gar nicht erlaubt... ergo ist h nicht zwingend berechenbar, ergo der Beweis Unsinn.
Danke,
freki!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:15 Do 20.12.2007 | | Autor: | Gilga |
Ich denke meine Mitteilung beantwortet die Frage einigermaßen
|
|
|
|
