1.2. Maszyna Turinga
Maszyna Turinga to stworzony przez Alana Turinga w 1937 roku abstrakcyjny model komputera służący do wykonywania algorytmów. Była to w zasadzie prosta maszyna logiczna. Pomimo swej prostoty ma ona obecnie duże znaczenie teoretyczne, ponieważ wszystkie współczesne komputery dają się do niej sprowadzić. Problem jest rozwiązalny na komputerze, jeśli da się zdefiniować rozwiązującą go maszynę Turinga.
Maszyna Turinga zbudowana jest z trzech głównych elementów:
- nieskończonej taśmy zawierającej komórki z przetwarzanymi symbolami,
- ruchomej głowicy zapisująco-odczytującej,
- układu sterowania głowicą.
Nieskończona taśma jest odpowiednikiem współczesnej pamięci komputera. Taśma może być nieskończona jednostronnie lub obustronnie. Taśma dzieli się na komórki, w których umieszczone zostały symbole, czyli po prostu znaki przetwarzane przez maszynę Turinga. Symbole te stanowią odpowiednik danych wejściowych. Maszyna Turinga odczytuje te dane z kolejnych komórek i przetwarza na inne symbole, czyli dane wyjściowe. Wyniki obliczeń również są zapisywane w komórkach taśmy. Aby przetwarzać dane, maszyna Turinga musi je odczytywać i zapisywać na taśmę. Do tego celu przeznaczona jest głowica zapisująco-odczytująca, która odpowiada funkcjonalnie urządzeniom wejścia/wyjścia współczesnych komputerów lub układom odczytu i zapisu pamięci. Głowica zawsze znajduje się nad jedną z komórek taśmy. Może ona odczytywać zawartość komórki oraz zapisywać do niej inny symbol – na tej zasadzie odbywa się przetwarzanie danych. Przetwarzaniem informacji zarządza układ sterowania głowicą. Jego współczesnym odpowiednikiem jest procesor komputera. Układ ten odczytuje za pomocą głowicy symbole z komórek taśmy oraz przesyła do głowicy symbole do zapisu w komórkach. Dodatkowo nakazuje on głowicy przemieścić się do sąsiedniej komórki w lewo lub w prawo. Podstawą działania maszyny Turinga są stany układu sterowania. Stan układu sterowania określa jednoznacznie jaką operację wykona maszyna Turinga, gdy odczyta z taśmy określony symbol. W przeciwieństwie do współczesnych komputerów, których program składa się z ciągu kolejno wykonywanych instrukcji, program dla maszyny Turinga jest tablicą instrukcji. Dla każdej pary symbolu wejściowego i stanu wewnętrznego określamy symbol wyjściowy, przejście do nowego stanu i ruch głowicy. Jeśli program nie definiuje działania dla bieżącego symbolu wejściowego i stanu wewnętrznego, to maszyna Turinga kończy wykonywanie programu.
Maszyna posiadająca zdolność wykonywania dowolnego programu jest nazywana uniwersalną maszyną Turinga. Praktyczną realizacją uniwersalnej maszyny Turinga jest właśnie komputer. Maszyna Turinga jest często brana pod uwagę jako odniesienie. Każde zadanie obliczeniowe, może zostać wykonane przez komputer zgodny z maszyną Turinga (zakładając brak ograniczeń sprzętowych i pamięciowych).