Maszyny Turinga

Maszyna Turinga to stworzony w 1936 roku przez Alana Turinga model abstrakcyjnej maszyny obliczeniowej. Pomimo swojej prostoty posiada ona olbrzymie znaczenie teoretyczne, bowiem 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.