Turingmaschinen

Einen sehr allgemeineren Ansatz machte Alan Turing 1936. Er beschäftigte sich bei der Entwickelte seiner Turingmaschine mit der Berechenbarkeit von Funktionen. Alonso Church fasste das Ergebnis seiner Arbeiten in folgender These zusammen:

Die Menge der Turing-berechenbaren Funktionen ist genau die Menge
der im intuitiven Sinne berechenbaren Funktionen.

R. Baumann präzisierte den Begriff des Algorithmus mit Hilfe einer Turingmaschine :

Ein Algorithmus ist ein Verfahren, das von einer Turingmaschine durchgeführt werden kann.

Vorteile des Turingmaschinenmodells:

• Jeder bis heute bekannte Formalismus kann damit simuliert werden.
• Die Berechnungsschritte sind einfach und können unmittelbar mechanisch umgesetzt werden.
• Die Beschreibung ist sehr einfach und anschaulich.

Nachteile des Turingmaschinenmodells:

• Unendlich langes Band ist nicht realisierbar.
• Programmierung ist kompliziert, da die Sprache sehr primitiv ist.
• Der Ablauf eines Programms wird aus der Struktur nicht ersichtlich.
• Die Laufzeit eines Turingprogramms ist sehr schlecht.

Turingmaschinen wurden tatsächlich nie gebaut; sie stellen ein rein theoretisches Rechnermodell dar, mit dem theoretische Betrachtungen wie die Berechenbarkeit von Funktionen einfacher untersucht werden können.
Registermaschinen stellen ein Bindeglied zwischen Turingmaschinen und realem Rechner dar. Diese erlauben eine deutlich komfortablere Programmierung, da sie direkten Zugriff auf alle Register haben. Ihre Handhabung ist aber noch wesentlich mühseliger als die realer Rechner.