1. Maszyna Turinga {image#}^{Indeks górny Żródło: CC BY-SA 3.0, zdjęcie: QuentinUK, Wikimedia Commons. Przykład szuki krytycznej: Banksy, Shop Until You Drop}

W roku 1937 Alan Turing pracując nad koncepcją obliczalności funkcji matematycznych opisał prostą maszynę logiczną, która nosi nazwę maszyny Turinga. Posiada ona olbrzymie znaczenie teoretyczne, ponieważ w prosty sposób przedstawia podstawy działania komputerów.
, 2. Taśma opis^{Indeks górny Żródło: licencja: CC BY-SA 3.0, zdjęcie: Muzeum Sztuki Współczesnej, Wikimedia Commons. Zbigniew Libera, Wyjście ludzi z miast}

Nieskończona taśma maszyny jest odpowiednikiem współczesnej pamięci komputera. Taśma dzieli się na komórki, w których umieszczone są symbole będące znakami przetwarzanymi przez maszynę. Symbole te są odpowiednikiem 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., 3. Symbole opis^{Indeks górny Zbigniew Libera, Obóz koncentracyjny, licencja: CC BY-ND 2.0, zdjęcie: Ministerstwo Spraw Zagranicznych, Flickr.}

Można definiować różne symbole dla maszyny Turinga. Najczęściej przedstawiane są jednak jako symbole 0, 1 oraz tzw. znak pusty.
, 4. Głowica <opis^{Indeks górny Licencja CC 0.}

Aby przetwarzać dane, maszyna Turinga musi je odczytywać i zapisywać na taśmie. Do tego celu przeznaczona jest głowica zapisująco-odczytująca.
Głowica zawsze znajduje się nad jedną z komórek taśmy. Może odczytywać zawartość tej komórki i wpisać do niej inny symbol - na tej zasadzie odbywa się przetwarzanie danych. Głowica wykonuje ruchy w prawo i w lewo do sąsiednich komórek na taśmie.
Przed rozpoczęciem pracy maszyny, głowica jest zawsze ustawiana nad komórką taśmy zawierającą pierwszy symbol do przetworzenia., 5. Układ sterowania opis^{Indeks górny Muzeum Sztuki w Łodzi, sala neoplastyczna, licencja: CC BY-SA 4.0, zdjęcie: Muzeum Sztuki w Łodzi, Wikimedia Commons.}


Przetwarzaniem informacji zarządza układ sterowania. Jego 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 jaką operację wykona maszyna Turinga, gdy odczyta z taśmy symbol., 6. Stany układu sterowania
opis^{Indeks górny Muzeum Sztuki Nowoczesnej w Warszawie, licencja CC BY 4.0, zdjęcie: Patryk Korzeniecki, Wikimedia Commons}

Operacje wykonywane przez układ sterowania zależą od :
Symbolu odczytanego z komórki na taśmie.
Bieżącego stanu układu sterującego.
Stany określamy kolejnymi nazwami: q0, q1, q2, ... ,qn, gdzie q0 jest stanem początkowym, w którym znajduje się maszyna Turinga przed rozpoczęciem przetwarzania symboli na taśmie., 7. Znaczenie symboli {image#}^{Indeks górny Umberto Eco widział w świadomym i celowym tworzeniu dzieł otwartych metaforę współczesności. Brak ciągłości i nieokreśloność uważał za wyraz możliwości wyborów, które otwierają się przed współczesnym człowiekiem.
Źródło: Peter Bruegel, Wieża Babel, domena publiczna.}
Znaczenia symboli maszyny Turinga
So – symbol odczytany przez głowicę z bieżącej komórki na taśmie
Sz – symbol, jaki zostanie zapisany w bieżącej komórce na taśmie
qi – bieżący stan układu sterowania
qj – nowy stan, w który przejdzie układ sterowania po wykonaniu tej operacji
L/R – ruch głowicy o jedną komórkę w lewo (L) lub w prawo (R), 8. Instrukcje {image#}<sup>licencja: CC 0
S0 i qi są częścią identyfikacyjną instrukcji.
Maszyna Turinga wykona tyle instrukcji, ile zdefiniujemy części identyfikacyjnych - w programie nie może być dwóch różnych instrukcji o identycznej części identyfikacyjnej. Powód jest oczywisty - którą instrukcję należałoby w takim wypadku wykonać?
Sz, qj i L/P są tzw. częścią operacyjną, która określa jakie działanie podejmuje dana instrukcja.
Części operacyjne różnych instrukcji mogą być takie same - oznacza to jedynie, iż instrukcje te wykonują dokładnie to samo działanie., 9. Przykład działania opis_{Indeks dolny licencja: domena publiczna}
Roberto Benigni wystąpił w wielokrotnie nagrodzonym filmie Życie jest piękne. Jego dzieło jest przedstawiane jako komedia o Holokauście.

instrukcja maszyny Turinga brzmi: (1, q0, 0, q0, P)
1. Odczytanym przez głowicę symbolem z taśmy jest 1,
2. układ sterowania znajduje się w stanie q0,
3. głowica zamieni symbol 1 na 0,
4. Stan wewnętrzny nie zmieni się (pozostanie q0)
5. Głowica przesuwa się (P) do sąsiedniej komórki po prawej stronie.
Pierwsze dwa elementy określają jednoznacznie instrukcję. Pozostałe trzy określają, co w ramach tej instrukcji należy zrobić, czyli jaki symbol umieścić w bieżącej komórce taśmy, w jaki nowy stan przejść i w którą stronę przesunąć głowicę., 10. Tablica opis_{Indeks dolny Źródło: Flickr; CC BY-NC-ND 2.0. Część popularnego zestawu Lego – Piraci}

Programem dla maszyny Turinga jest tablica, w której określamy wszystkie wykonywalne przez nią instrukcje. Maszyna Turinga rozpoznaje instrukcje po symbolu z taśmy i swoim stanie wewnętrznym. 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. Maszyna Turinga napotykając na taśmie określony symbol i będąc w danym stanie wewnętrznym szuka w tablicy programu takiej właśnie pary i po znalezieniu wykonuje część operacyjną instrukcji. Jeśli w tablicy zabraknie dla tej kombinacji odpowiedniej instrukcji, to program zatrzymuje się.</sup>