Thiel I 249
Berechenbarkeit/Church/Thiel: Wie nahe ist man (...) einem Begriff der "allgemeinen Berechenbarkeit" gekommen? Es gibt den Begriff der "Turing Berechenbarkeit" der "l-Definierbarkeit bei Church, der "kanonischen Systeme" bei E. Post.
Jede Funktion, die in einer dieser Klassen liegt, liegt nachweislich auch in den anderen.
Church: Church hat daraufhin die Vermutung ausgesprochen, dass damit eine adäquate Präzisierung des allgemeinen Berechenbarkeitsbegriffs erreicht sei.
>
"Church-These".
Es meint aber, dass das eine "außermathematische" Vermutung sei, und keines mathematischen Beweises fähig. Ein intuitiver Begriff. Ob eine derartige Präzisierung "adäquat" sei, sei mit mathematischen Mitteln nicht zu beantworten.
>
Adäquatheit.
I 250
Es bleiben außer Finitheit und Konstruktivität noch andere Fragen: keine der Definitionen für die angebotenen Funktionenklassen ist nämlich finit: (z.B. µ-rekursive Funktionen).
>
Rekursion, >
Finitheit, >
Definitionen, >
Definierbarkeit.
Der Versuch, mit klassischen Mitteln effektive Ausführbarkeit zu beschreiben bleibt fragwürdig, deuten wir den Existenzquantor aber konstruktiv, so haben wir den Begriff der Konstruktivität bereits vorausgesetzt.
>
Existenzquantifikation, >
Quantoren, >
Effektivität.
Thiel I 251
Berechenbarkeit/Herbrand/Thiel: Aufgrund der Herbrandschen Forderungen verlieren manche der klassischen Gesetze der Logik ihre Gültigkeit
Bsp der Schluss von ~(x)A(x) auf (Ex)~A(x) ist nicht zulässig:
Bsp dass nicht alle reellen Zahlen algebraisch sind, verhilft uns noch nicht zu einer transfiniten reellen Zahl.
>
J. Herbrand.
Bsp Daraus, dass die Aussagen: "Die Dezimalbruchentwicklung von π enthält eine ununterbrochene Folge von 1000 Einsen" und "Die Dezimalbruchentwicklung von π enthält nirgends eine ununterbrochene Folge von 100 Einsen" nicht beide wahr sein können, (da aus der ersten Aussage die zweite folgt) kann man nicht darauf schließen, dass das Negat der ersten Aussage oder die zuletzt in der Klammer genannte Aussage wahr sei.
Thiel I 252
Dieses Gegenbeispiel aber zeigt, dass der klassische Schluss von
~(a u b) auf ~a v ~b
nicht zulässig ist, wenn das Adjunktionszeichen dabei zum Ausdruck einer entscheidbaren Alternative benutzt werden soll. Insbesondere darf man, wie bei der Ersetzung von b durch ~a sichtbar wird, nicht von ~(a u ~a) auf ~a v ~~a schließen, obwohl dies doch ein Spezialfall des klassisch unbeschränkt gültigen tertium non datur ist.
>
Satz vom ausgeschlossenes Dritten, >
Logische Konstanten, >
Ersetzbarkeit.
