Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Basic Notions and Applications of the Theory of Decidability
verfasst von : H. Hermes
Erschienen in: Aspects of Mathematical Logic
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Preliminary Remarks
. The first three lectures contain an exposition of the fundamental concepts of some main theorems of the theory of recursive functions. One of the more difficult theorems of the theory of recursive functions is Friedberg-Mučniks theorem which asserts the existence of non-trivial enumerable degrees. In Lectures 4 and 5 we prove this theorem, following the treatment given by Sacks, but stressing somewhat more the combinatorial part of the proof (Lecture 4). Lecture 6 deals with problems in the theory of primitive recursive functions. As a typical example of the application of the theory of recursitivy we give in Lecture 7 in detail a proof for the unsolva-bility of the domino problem in the simplest case of the origin-restricted problem and show in Lecture 8 how the domino problem is connected with the ∧∨∧- case of the Entscheidungsproblem.
Lecture 6 has been given before Lectures 4 and 5. The interchange is due to systematical reasons.