Berechenbarkeit: Berechnungsmodelle und Unentscheidbarkeit

Von Karl-Heinz Zimmermann

In diesem essential werden wesentliche Konzepte der Berechenbarkeitstheorie erörtert. Zunächst werden unterschiedliche Modelle der Berechenbarkeit eingeführt und ihre semantische Gleichwertigkeit gezeigt. Dieses Resultat steht in Einklang mit der Church-Turing-These, nach der jede intuitiv berechenbare Funktion partiell-rekursiv ist. Neben zentralen Instrumenten der Berechenbarkeit, wie etwa der Gödelisierung von berechenbaren Funktionen und der Existenz universeller berechenbarer Funktionen, stehen unentscheidbare Probleme im Fokus, wie etwa das Halteproblem sowie das Wortproblem für die Term-Ersetzung. Semi-entscheidbare Mengen werden beleuchtet und die zentralen Sätze von Rice und Rice-Shapiro werden skizziert. 

• Sprache: Deutsch
• Herausgeber: Springer Spektrum
• Erscheinungsdatum: 28. Okt. 2020
• ISBN: 9783658317393

Buchvorschau

© Der/die Herausgeber bzw. der/die Autor(en), exklusiv lizenziert durch Springer Fachmedien Wiesbaden GmbH, ein Teil von Springer Nature 2020

K.-H. ZimmermannBerechenbarkeitessentialshttps://doi.org/10.1007/978-3-658-31739-3_1

1. Berechnungsmodelle

Karl-Heinz Zimmermann¹  

(1)

Institut für Eingebettete Systeme, TU Hamburg, Hamburg, Deutschland

Karl-Heinz Zimmermann

Email: [e-mail]

Das Ziel dieses Kapitels ist die Präzisierung des Begriffs der berechenbaren Funktion. Unter einer berechenbaren Funktion stelle man sich eine Funktion vor, die durch eine Rechenvorschrift berechnet werden kann. Es werden drei ganz unterschiedliche Modelle der Berechenbarkeitstheorie vorgestellt: die auf unbeschränkten Registermaschine berechenbaren Funktionen, die partiell-rekursiven Funktionen und die durch GOTO-Programme berechenbaren Funktionen. Es wird gezeigt, dass diese Klassen¹ von berechenbaren Funktionen übereinstimmen. Zudem wird kurz auf die Ackermannfunktion eingegangen, die als rekursive Funktion eine Abgrenzung zwischen den partiell-rekursiven und den primitiv-rekursiven Funktionen erlaubt. Abschließend wird die zentrale These der Berechenbarkeitstheorie, die sogenannte Church-Turing-These, erläutern, die den Begriff der berechenbaren Funktionen abstützt.

1.1 Unbeschränkte