Podstawowe informacje
Maszyna Turinga składa się z trzech elementów: taśmy, głowicy i programu. Przyjmujemy, że stan głowicy kodowany jest małymi literami alfabetu łacińskiego „a” – „z”, taśma jest nieskończonym zbiorem wartości kodowanych dużymi literami „A” – „Z” poza „R” i „L”, które będą zarezerwowane dla oznaczenia komend, oraz znaku pustego (np. kodowanego spacją). Głowica wskazuje na jedną wartość zapisaną na taśmie nazywaną wartością bieżącą. Program składać się powinien z uporządkowanych „czwórek”: {obecny stan głowicy, bieżąca wartość taśmy, komenda/nowa wartość taśmy, nowy stan głowicy}. Właściwa linia programu rozpoznawana jest po dwóch pierwszych elementach czwórki – wykonywana jest ta linia, w której pierwszy element jest równy obecnemu stanowi głowicy, a drugi bieżącej wartości taśmy. Poprawny program nie może zawierać dwóch linii o tych samych dwóch pierwszych elementach – inaczej byłby niejednoznaczny.
Możliwe są trzy komendy umieszczone w trzecim elemencie czwórki/linii programu:
1) przesuń głowicę w lewo kodowane przez zarezerwowaną wartość „L”
2) przesuń głowicę w prawo kodowane przez zarezerwowaną wartość „R”
3) zamień wartość w bieżącej pozycji głowicy na taśmie kodowane przez wartość inną niż „R” lub „L”
Ostatni element „czwórki” zawiera nową wartość rejestru.
Przykład prostej maszyny Turinga
Początkowa taśma: AAAABAA (pozostałe wartości są puste, znak pusty również należy do alfabetu)
Początkowy stan głowicy: q
Położenie głowicy: 2
Program: qASs –zamień wartość z A na S i ustaw głowicę na s
sSRq – przesuń w prawo i zmień stan głowicy na q
qBRb – przesuń w prawo i zmień stan głowicy na b
Wówczas można spójnie zapisać stan taśmy i głowicy przez stan maszyny Turinga: AqAAABAA.
Stan głowicy odpowiada pierwszej linii programu. Po jej wykonaniu otrzymamy AsSAABAA. Następnie wykonywana jest druga linia (nie dlatego, że następuje po pierwszej, a dlatego, że odpowiada jej stan głowicy i bieżąca wartość taśmy). W efekcie uzyskamy ASqAABAA. Stan głowicy i bieżąca wartość taśmy odpowiada znów pierwszej linii kodu. Kolejne stany maszyny Turinga są następujące:
ASsSABAA
ASSqABAA
ASSsSBAA
ASSSqBAA
ASSSBbAA
Na tej linii wykonywanie programu się kończy, ponieważ nie ma linii programu odpowiadającej stanowi głowicy b przy bieżącej wartości taśmy A.
Maszyny Turinga są interesujące z kilku względów. W informatyce gdyż z udowodniono, że zwykłe komputery są równoważne maszynom Turinga. W filozofii i psychologii poznawczej gdyż maszyna Turinga jest wygodnym narzędziem przy precyzowaniu pojęć i problemów procesu poznawania i sztucznej inteligencji.