Philosophie Lexikon der Argumente

Home Screenshot Tabelle Begriffe

 
Berechenbarkeit: Hier geht es um die Frage, ob bestimmte Operationen prinzipiell durch ein Verfahren geleistet werden können bzw. ob Fragestellungen durch ein Verfahren beantwortet werden können. Insbesondere geht es um die Berechnung von mathematischen Funktionen in endlicher Zeit. Die Frage ob ein Problem berechenbar ist, ist nur relativ zu einem Modell sinnvoll. Siehe auch Komplex/Komplexität, Turing-Maschine, Entscheidbarkeit, Entscheidungstheorie, Entscheidungsproblem, Halteproblem, Modelle, Algorithmen, Vollständigkeit, Unvollständigkeit, Church-Turing-These, Turing-Maschine.

_____________
Anmerkung: Die obigen Begriffscharakterisierungen verstehen sich weder als Definitionen noch als erschöpfende Problemdarstellungen. Sie sollen lediglich den Zugang zu den unten angefügten Quellen erleichtern. - Lexikon der Argumente.

 
Autor Begriff Zusammenfassung/Zitate Quellen

Alonzo Church über Berechenbarkeit – Lexikon der Argumente

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.

_____________
Zeichenerklärung: Römische Ziffern geben die Quelle an, arabische Ziffern die Seitenzahl. Die entsprechenden Titel sind rechts unter Metadaten angegeben. ((s)…): Kommentar des Einsenders. Übersetzungen: Lexikon der Argumente
Der Hinweis [Begriff/Autor], [Autor1]Vs[Autor2] bzw. [Autor]Vs[Begriff] bzw. "Problem:"/"Lösung", "alt:"/"neu:" und "These:" ist eine Hinzufügung des Lexikons der Argumente.

Chur I
A. Church
The Calculi of Lambda Conversion. (Am-6)(Annals of Mathematics Studies) Princeton 1985

T I
Chr. Thiel
Philosophie und Mathematik Darmstadt 1995

Send Link

Autoren A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   Y   Z  


Begriffe A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   Z