Suche diesen Artikel in der aktuellen Wikipedia

[Home]Turing Automat

HomePage | RecentChanges | Preferences

Von Alan Turing 1936 eingeführtes mathematisches Konstrukt, um eine Klasse von berechenbaren? Funktionen? zu bilden.

Eine Turing-Maschine besitzt ein lineares, in beide Richtungen unsichtbares Band, das in einzelne Felder eingeteilt ist. Jedes Feld enthält genau ein Zeichen eines vorgegebenes Bandalphabets B, in dem ein Zeichen, das sog. Leerzeichen z, das für das leere Feld steht, ausgezeichnet ist. Es existiert ein Schreib- / Lesekopf, mit dem das Zeichen eines Feldes gelesen bzw. geschrieben werden kann. Die Maschine ist ein [endlicher Automat]? mit der Zustandsmenge Z und dem Anfangszustand z0 aus dieser Zustandsmenge. Alsdann gibt es eine Abbildungsvorschrift, die für jedes Paar aus gelesenem Zeichen und aktuellem Zustand bestimmt, welches Zeichen auf das Band geschrieben werden soll, in welchen Zustand die Maschine übergehen soll und ob sich das Band nach rechts (R) oder links (L) bewegen soll bzw. ob es halten (H) soll und damit "fertig!" signalisieren soll.

Die Turing-Maschine arbeitet als wie folgt: sie liest ein Zeichen vom Band. In Abhängigkeit vom gelesenen Zeichen und dem Zustand, in dem sie sich gerade befindet, schreibt sie ein Zeichen auf das Band, ändert ihren internen Zustand und bewegt den Schreib- / Lesekopf in die vorgegebene Richtung.

Die Menge turing-berechenbaren Funktionen ist die Menge aller Funktionen, die sich mit einer Turing-Maschine berechnen lassen (die Turing-Maschine muss die Aktion (H) ausführen!). Es gibt noch andere Verfahren, über die man Berechenbarkeit? von Funktionen? definieren kann, z.B. über [rekursive Funktionen]?.

Es macht übrigens keinen Unterschied, ob eine Turing-Maschine eine oder mehrere Bänder verwendet. Auch das Bandalphabet kann beliebig gross sein, solange neben dem Leerzeichen ein weiteres Zeichen enthalten ist, ist eine Turing-Maschine zur allgemeinen Turing-Maschine gleichmächtig.


HomePage | RecentChanges | Preferences
This page is read-only | View other revisions
Last edited August 2, 2001 4:21 pm by Epischel (diff)
Search: