Maszyna Turinga

Jest abstrakcyjnym modelem urządzenia przekształcającego ciągi symboli, tj. słowa w alfabecie A; ponieważ słowa mogą przedstawiać rozmaite obiekty (np. liczby naturalne w zapisie dziesiętnym są przedstawiane słowami złożonymi z symboli 0, 1, 2,... , 9), maszynę Turinga mogą reprezentować funkcje o argumentach i wartościach rozmaitych typów (np. funkcje arytmetyczne).

Maszyną Turinga określa się zwykle opisowo jako urządzenie składające się z:
1) nieskończonej taśmy podzielonej na klatki w taki sposób, że każda klatka może pomieścić 1 symbol z ustalonego, skończonego alfabetu A tej maszyny Turinga;
2) głowicy czytającej i piszącej w klatkach taśmy symbole z alfabetu A;
3) pamięci stanów — pojedynczej klatki mogącej pomieścić 1 symbol z ustalonego, skończonego alfabetu stanów A tej maszyny Turinga;
4) urządzenia sterującego wraz z programem tej maszyny Turinga, które powoduje działanie głowicy (tj. czytanie i pisanie), przesuwanie taśmy (w obydwu kierunkach) i zmianę zawartości pamięci stanów; programem jest skończony zbiór tych czynności. Można przyjąć, że pamięć stanów jest częścią urządzenia sterującego (automat abstrakcyjny).

Źródła:

⠀ Internetowa encyklopedia PWN. Retrieved from https://encyklopedia.pwn.pl/haslo/Turinga-maszyna;3990108.html