Hi,
habe ich richtig verstanden, dass die Churchsche These besagt, dass man für alle berechenbaren Funktionen auch eine Turingmaschine, ein While-Programm, ein Goto-Programm oder eine µ-rekursive Funktion angeben kann, die die Funktion berechnet ?
Grüße,
Tris
Hallo,
das ist nicht unpräzise genug *g*. „Berechenbar“ ist ja in den verschiedenen Formalismen definiert und die Gleichheit läßt sich untereinander zeigen. Die Churchsche These ist „jede im natürlichen/intuitiven Sinne berechenbare Funktion ist auch Turing, while, etc. berechenbar.“.
Gruss
Enno
Hallo,
Du meinst, dass der Zusatz „im intuitiven Sinne“ noch wichtig wäre.
Was ist damit gemeint ? Welche anderen Formalismen gibt es noch ?
Danke und Gruß,
Tris
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hallo,
z.B. Registermaschinen und natürlich sind auch alle berechenbaren Funktionen in Prädikatenlogik darstellbar. Welche anderen Formalismen es gibt, ist aber an sich nicht wichtig, die Churchsche These ist eine Aussage die ein „offenes Ende“ hat, durch den Begriff „natürlich“ resp. „intuitiv“. Sie verknüpft keine Formalismen sondern das menschlische Verständnis von Berechenbarkeit mit im einfachsten Fall der Turing-Berechenbarkeit. Sie ist daher per se unbeweisbar.
Gruss
Enno