Turing-Maschine und Turing-Vollständigkeit

Marie-Christine Jones 2017

Alan Turing

• 1912 - 1954; England
• Schrieb 1936 "On Computable Numbers, with an Application to the Entscheidungsproblem"
• Ein Begründer der Computertheorie

Turing-Maschine

Kann alles berechnen, was von Menschen berechnet werden kann

Funktionsweise

• Zellen enthalten Zeichen
• Maschine hat Zustand
• Schreib-/Lesekopf bewegt sich max. 1 Feld


• 1. Ein Zeichen wird geschrieben
• 2. Der Zustand wird geändert
• 3. Der Schreib-/Lesekopf bewegt sich

Beispielprogramm

Turing-Vollständigkeit

Die Turingmaschine definiert, was Berechenbarkeit ist

Turing-Vollständig ist etwas, das alles berechnen kann, was die Turingmaschine berechnen kann

Programmiersprachen sind Turing-Vollständig

Die kleinste Turing-vollständige Sprache ist "Brainfuck":
++++++++++[>+++++++>++++++++++>+++<<<-]>++.>+.+++++++ ..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.

Quellen

Bilder