Berechnungsmodell

Wir geben kurz die zugrunde liegenden Definitionen des Berechnungsmodells Turingmaschine an. Außerdem weisen wir auf einige Beschränkungen der vorhandenen Implementierung hin.

Alle anzeigen / Alle verbergen

Antwort auf/zuklappen

k-Band-Turingmaschine

Eine k-Band-Turingmaschine M ist ein 6-Tupel M=(Σ,Γ,Z,f,z0,z1) mit

  • Alphabet Σ (Ein-/Ausgabealphabet) mit ∗,_ ∉Σ,
  • Alphabet Γ (Bandalphabet) mit ∗,_∈Γ und Σ⊆Γ,
  • endlicher Menge Z (Zustandsmenge),
  • totaler Funktion f: (Z\{z1})×Γk → Z×Γk×{0,L,R}k (Überführungsfunktion),
  • z0∈Z (Startzustand), sowie
  • z1∈Z (Stoppzustand).

Die Symbole ∗ und _ heißen Trennsymbol bzw. Leersymbol.

Antwort auf/zuklappen

Startkonfiguration

Seien M=(Σ,Γ,Z,f,z0,z1) eine k-Band-Turingmaschine und w=a0…an-1∈Γ\{_}. Die Startkonfiguration S(w) von M bezeichnet folgende Situation:

  • die Steuereinheit ist in Zustand z0,
  • auf Band 0 steht a0…an-1 mit Kopf 0 auf a0 (falls n=0 steht der Kopf auf irgendeinem _),
  • die Bänder 1,…,k-1 enthalten nur _.
Antwort auf/zuklappen

Berechnungsergebnis bei Stopp

Seien M=(Σ,Γ,Z,f,z0,z1) eine k-Band-Turingmaschine in Zustand z1 und sei u∈Γ der Inhalt von Band 0 ohne führende und ohne nachfolgende Leerzeichen _. Dann ist das Berechnungsergebnis v von M das maximale Präfix v∈∑ von u.

Antwort auf/zuklappen

Berechnete Funktionen

Sei m≥0 und sei M=(Σ,Γ,Z,f,z0,z1) eine k-Band-Turingmaschine. Die von M berechnete m-stellige Funktion φM:(∑)m→∑ ist für alle x0,…,xm-1 definiert als

  • φM(x0,…,xm-1) = v, falls M in S(x0∗x1∗…∗xm-1) startet und mit Ergebnis v anhält,
  • φM(x0,…,xm-1) = n.d., falls M in S(x0∗x1∗…∗xm-1) startet und nicht anhält.

 

Aus diesen Definitionen ergibt sich, dass φM(x0,…,xm-1) genau dann definiert ist, wenn M beginnend in S(x0∗x1∗…∗xm-1) anhält.

Antwort auf/zuklappen

Turin-Syntax von Turingmaschinen-Programmen

Zustände werden in Turin stets mit zi bezeichnet, wobei i eine nichtleere Folge aus den Ziffern 0,...,9 ist. Start- und Stoppzustand sind als z0 bzw. z1 festgelegt.

Für das Bandalphabet Γ stehen höchstens die Symbole 0,…,9,a,…,z,A,…,Z zur Verfügung. Insofern ergibt sich im Unterschied zum Berechnungsmodell eine Maximalgröße für Γ.

Ein Übergang f(z,a0,…,ak-1) = (z',a'0,…,a'k-10,…,σk-1) der Überführungsfunktion f mit z,z'∈Z, ai∈Γ und σj∈{0,L,R} wird in Turin als Programmzeile

(z,a0,…,ak-1)->(z',a'0,…,a'k-10,…,σk-1)

dargestellt. Beispiel für einen Befehl einer 2-Band-Turingmaschine:

(z0,2,1)->(z3,1,2,R,0)

Kommentare beginnen mit // und werden durch das Zeilenende begrenzt.

Antwort auf/zuklappen

Unvollständige Programme

In Programmen dürfen unnötige Befehle der Einfachheit halber weggelassen werden, z.B. solche, die nie erreicht werden. Fehlt im Programm ein Befehl

(z,a0,…,ak-1)->

so verhält sich die Maschine entsprechend des gedachten Befehls

(z,a0,…,ak-1)->(z1,_,…,_,0,…,0).

Damit beschreiben auch unvollständige Programme immer totale Überführungsfunktionen.

WebRedaktion-inf,  1. April 2015