Maszyna Turinga

Maszyna Turinga

Maszyna Turinga, opracowana przez Alana Turinga, to abstrakcyjny model urządzenia do wykonywania algorytmów. Składa się z bloku sterowania, głowicy oraz nieskończonej taśmy, gdzie każda komórka taśmy może zawierać jeden symbol. Maszyna operuje na podstawie określonych rozkazów, które definiują, jak reagować na symbole i stany.

Wstęp

Każdy algorytm realizowalny na maszynie Turinga można również wyrazić w rachunku lambda i odwrotnie. Jednak z uwagi na trudności w rozszerzaniu maszyn Turinga, są one rzadziej stosowane w praktyce. Uniwersalna maszyna Turinga potrafi symulować działanie każdej innej maszyny Turinga, ale w przeciwieństwie do komputerów, które mają ograniczoną pamięć, maszyna Turinga jest teoretycznie nieograniczona. Istnieją jednak problemy, takie jak problem stopu, które są nierozwiązywalne przez maszyny Turinga.

Warianty maszyny Turinga

W literaturze istnieje wiele wariantów maszyny Turinga, takich jak:

• Maszyny wielotaśmowe
• Maszyny niedeterministyczne
• Maszyny wielowymiarowe (np. mrówka Langtona)

Wszystkie te warianty są równoważne klasycznej maszynie Turinga pod względem mocy obliczeniowej.

Zapis formalny

Maszyna Turinga opisana jest przez krotkę:

Gdzie:

• $Q$ – zbiór stanów
• $q\_0\; \backslash in\; Q$ – stan początkowy
• $F$ – zbiór stanów końcowych
• $\backslash Gamma$ – zbiór symboli
• $B$ – symbol pusty
• $\backslash Sigma$ – zbiór symboli wejściowych
• $\backslash delta$ – funkcja określająca działanie maszyny

Inne ujęcie

W modelu Rogera Penrose’a zakłada się, że maszyna obsługuje jedynie dwa znaki (0 i 1), a stany wewnętrzne są oznaczone liczbami dwójkowymi. Maszyna może zmieniać stan, zapis na taśmie lub się zatrzymywać. Przykłady maszyn to:

• UN+1 – zwiększająca liczbę w systemie jedynkowym o 1
• EUC – znajdująca największy wspólny dzielnik

Maszyny Turinga mogą być bardziej złożone, ale oferują większą szybkość.

Podsumowanie

Maszyna Turinga jest kluczowym modelem w teorii obliczeń, mimo że nie rozwiązuje wszystkich problemów. Badania nad potężniejszymi modelami, takimi jak hiperkomputery, są w toku. Teoretyczne rozważania dotyczące maszyn Turinga są podstawą wielu zagadnień w informatyce, w tym problemu „P versus NP”.