By Hans Hermes
Read or Download Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit: Einführung in die Theorie der Rekursiven Funktionen PDF
Similar foreign language study & reference books
The Emergence of Semantics in Four Linguistic Traditions: Hebrew, Sanskrit, Greek, Arabic
This examine goals to supply a comparative research of the function of semantics within the linguistic concept of 4 grammatical traditions - Sanskrit, Hebrew, Greek, and Arabic.
A Word or Two Before You Go . . . . Brief essays on language
Engl. Language and reviews
Fremde Welten: Die Oper des italienischen Verismo
Mit diesem Buch erfährt der Opernverismo erstmals eine umfassende Gesamtdarstellung. Die Rahmenbedingungen für seine Durchsetzung im internationalen Opernbetrieb werden ebenso in den Blick genommen wie die Entstehung, Verbreitung und Rezeption der veristischen Oper.
Extra info for Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit: Einführung in die Theorie der Rekursiven Funktionen
Sample text
Sei etwa ll(o={al, ... ,aN}, 1l(={~, ... ,aL}' L>N. Es liege ein Problem vor, welches nur Worte über Il(o betrifft, und ein das Problem lösender Algorithmus, der Symbole aus Il( verwendet. B. as in alalal . B. a 4 aOa 2 aa übersetze man mit Hilfe der Symbolübersetzung in alal~~aOaOao~~aO~~al' So übersetze man zunächst das Problem. Sodann wende man darauf eine Art "übersetzten Algorithmus" an, der schließlich zur übersetzten Lösung führt, welche man wieder rückzuübersetzen hat. Es ist plausibel, daß man damit einen Algorithmus erhält, der nur mit den Symbolen von Il(o arbeitet.
2. Turing-Aufzählbarkeit. Wir benutzen hier eine normierte Darstellung der natürlichen Zahlen. Dazu verabreden wir, die natürliche Zahl n durch n + 1 Striche darzustellen (vgl. 4), also z. B. die Zahl Drei durch 1111. Dabei wollen wir den Strich 1 mit a1 identifizieren. Eine Menge M von Worten heiße Turing-aufzählbar, wenn M leer ist, oder wenn M übereinstimmt mit dem \;Vertebereich einer Turing-berechenbaren Funktion, deren Argumentbereich die Menge der natürlichen Zahlen ist. 4 die Erzeugbarkeit mit der Aufzählbarkeit gleichbedeutend ist, können wir uns eine besondere Definition für die Turing-Erzeugbarkeit ersparen.
G. FREGE (1848-1925) hat sich insbesondere um eine exakte Fassung der logischen Regeln bemüht. Einen vorläufigen Abschluß fanden diese Bestrebungen in dem monumentalen Werk "Principia Mathematica" (3 Bde, 1910-1913) von A. N. WHlTEHEAD und B. RUSSELL. Hierin wurde nachgewiesen, daß sich große Teile der Mathematik mit Hilfe eines Logikkalküls deduzieren lassen. Krönender Abschluß der durch Boole eingeleiteten Entwicklung war der sog. GÖDELsche Vollständigkeitssatz (1930), welcher besagt, daß die angegebenen logischen Regeln ausreichen, um alle Folgerungen aus einem beliebigen Axiomensystem zu ziehen, vorausgesetzt, daß man sich auf die Sprache der sog.