Turinga maszyna
Encyklopedia PWN
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).
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); istnieją funkcje niereprezentowalne przez żadną maszynę Turinga (tzw. funkcje nieobliczalne), ale tzw. hipoteza Turinga głosi, że każda funkcja, dla której istnieje efektywna metoda (algorytm) obliczania wartości, jest reprezentowalna przez pewną maszynę Turinga; są to tzw. funkcje (częściowo) obliczalne. Ponieważ rozstrzyganie problemów sprowadza się najczęściej do obliczania wartości funkcji, maszyna Turinga stała się w matematyce ważnym narzędziem formalnym dla zagadnień efektywnej rozstrzygalności, a także dla zagadnień złożoności obliczeniowej. Pojęcie maszyny Turinga wprowadził 1936 A.M. Turing.
