HSG

Aktuelle Seite: HSG/Fächer/Informatik/Theorie/Berechenbarkeit/Maschinen-Modelle/Turing-Maschinen

Turing-Simulator in Python

Der Simulator benutzt Dictionaries um das Band und die Turingtafel darzustellen. Hier ist besonders bequem, dass die get-Methode es zulässt, eine Default-Rückgabe vorzusehen für den Fall, dass der Key nicht im Dictionary ist. Auf diese Weise kann man problemlos ein leeres Band darstellen oder in einen Fehlerzustand wechseln, wenn eine Transition nicht gefunden wird.

band = {0:' '}
pos = 0
n = 0
zustand = 'z0'
kopfbewegung = None
tt = {('z0',' '):('z1','I','R'),
      ('z0','I'):('z1','I','L'),
      ('z1',' '):('z0','I','L'),
      ('z1','I'):('z2',' ','L'),
      ('z2',' '):('z0','I','S'),
      ('z2','I'):('z3','I','L'),
      ('z3',' '):('z3','I','R'),
      ('z3','I'):('z0',' ','R')}

# print(n,band,pos,zustand) # DEBUG
while kopfbewegung != 'S':
    n = n + 1
    gelesen = band.get(pos,' ')
    (zustand,zuschreiben,kopfbewegung) = tt.get((zustand,gelesen),('F','F','S'))
    band.update({pos:zuschreiben})
    if kopfbewegung == 'L':
        pos = pos - 1
    elif kopfbewegung == 'R':
        pos = pos + 1
    # print(n,band,pos,zustand) # DEBUG

Folgende Zeilen ermöglichen eine komfortablere Darstellung des Ergebnisses bei fleißigen Bibern.

Bandinhalt = ''.join([band.get(x) for x in sorted(band)])
anz = len(Bandinhalt.replace(' ',''))
print(Bandinhalt,anz,n)
PosInhalt = pos - min(sorted(band))
Position = ' '*PosInhalt+'^'+' '*(len(Bandinhalt)-PosInhalt-1)
print(Position,pos)

bb1.py, bb2.py, bb3.py, bb4.py, bb5_schult.py, bb5_uhing.py, bb5_MarxenBuntrock.py (ca. 2 min)

Links