69026

Maszyna Turinga

Maszyna Turinga składa sie, z naste, pujących elementów: skonczonegoalfabetu symboli

skoń czonego zbioru stanów, decydujących o działaniu maszyny nieskonczonejtasmypodzielonej na komórki, z których ka zdamo ze zawiera c pojedynczy, zrozumiały dla maszyny symbol ruchomej głowicy odczytują co-zapisującej, która moz ewe, drowac' wzdłuz tas my przesuwaj a, csie, w tylko o jedną komórką diagramu przejś ć' mie,dzy stanami zawieraja,cego instrukcje, które powodują,, z e zmiany naste, puja, przy kaz dym zatrzymaniu si

Mechanizm sterujący na podstawie bież a,cego stanu i symbolu znajdują cego sie, pod głowica, podejmuje decyzje, o:

zmianie zawartoś ci komórki tas'myznajduja,cejsie, pod głowica,, przesum, eciu głowicy w lewo lub prawo, zmianie stanu mechanizmu sterują,cego.

Definicja formalna :

M = (Q;S;G; ];d;qO;F); gdzie:

Q to sko ńczony zbiór stanów maszyny,

S to sko ńczony zbiór symboli wej ściowych,

G to sko ńczony zbiór symboli ta śmowych (S _ G),

] to symbol pusty, d to funkcja przej ścia, q0 to stan pocza, tkowy,

F to zbiór stanów akceptują, cych, be,da,cy podzbiorem Q.

Funkcja przejś cia jest to cze,s'ciowa, funkcja prowadza, ca z Q_G w Q_G_f;!g. Warto's'cd(A:x) = (B;y;K) oznacza, ze maszyna be, da, ca w stanie A i czytaja, c symbol x z taś my przejdzie w stan B, zapisze symbol y na taś mie i przesunie głowice, o jedna, komórkę, w lewo (K =) lub w prawo (K =!).