Maszyna Turinga, hipotetyczne urządzenie obliczeniowe wprowadzone w 1936 roku przez angielskiego matematyka i logika Alana M. Turinga. Turing pierwotnie pomyślał maszynę jako narzędzie matematyczne, które mogłoby nieomylnie rozpoznawać niedeterministyczne propozycje – tj. te twierdzenia matematyczne, które w ramach danego formalnego systemu aksjomatów nie mogą być wykazane jako prawdziwe lub fałszywe. (Matematyk Kurt Gödel wykazał, że takie nierozstrzygalne twierdzenia istnieją w każdym systemie wystarczająco potężnym, by zawierać arytmetykę). Turing natomiast udowodnił, że nigdy nie może istnieć żadna uniwersalna algorytmiczna metoda określania, czy dana propozycja jest niedecydowalna.
Maszyna Turinga nie jest maszyną w zwykłym sensie, ale raczej wyidealizowanym modelem matematycznym, który redukuje logiczną strukturę dowolnego urządzenia obliczeniowego do jego esencji. Zgodnie z założeniami Turinga, maszyna wykonuje swoje funkcje w sekwencji dyskretnych kroków i przyjmuje tylko jeden ze skończonej listy stanów wewnętrznych w danym momencie. Sama maszyna składa się z nieskończenie rozciągliwej taśmy, głowicy taśmowej zdolnej do wykonywania różnych operacji na taśmie oraz modyfikowalnego mechanizmu sterującego w głowicy, który może przechowywać wskazówki ze skończonego zbioru instrukcji. Taśma podzielona jest na kwadraty, z których każdy jest albo pusty, albo ma nadrukowany jeden ze skończonej liczby symboli. Głowica taśmy ma możliwość przechodzenia do, odczytu, zapisu i kasowania każdego pojedynczego kwadratu, a także może w każdej chwili zmienić stan wewnętrzny na inny. Każda taka czynność jest zdeterminowana stanem wewnętrznym maszyny i stanem skanowanego kwadratu w danej chwili. Wynik działania maszyny – tzn. rozwiązanie zapytania matematycznego – może być odczytany z systemu po zatrzymaniu maszyny. (Jednak w przypadku nierozstrzygalnych twierdzeń Gödla, maszyna nigdy się nie zatrzyma, co stało się znane jako „problem zatrzymania”).