[[Plik:Turing Machine.png|thumb|Artystyczna wizja maszyny Turinga]]
[[Plik:Turing machine 2b.svg|thumb|Grafika przedstawiająca maszynę Turinga w stanie q<sub>1</sub> nad zerem na taśmie]]
'''Maszyna Turinga''' – stworzony przez [[Alan Turing|Alana Turinga]] abstrakcyjnymatematyczny model [[komputer]]aobliczeń, służącegoktóry definiuje abstrakcyjną maszynę służącą do wykonywania [[algorytm]]ów,. wMaszyna którymskłada nasię nieskończeniez długiejbloku taśmiesterowania, podzielonejgłowicy naodczytującej polai zapisujezapisującej sięoraz dane.nieskończenie Taśmadługiej możetaśmy. byćW nieskończonakażdej jednostronniekomórce lub obustronnie. Każde poletaśmy może znajdowaćmieścić się wjeden jednym z N stanówsymbol. Maszyna zawsze jest ustawiona nad jednym z pól i znajduje się w jednym z MQ stanów. Zależnie od kombinacji stanu maszyny i polasymbolu napotkanego na taśmie maszyna zapisuje nową wartość w polu, zmienia stan, a następnie może przesunąć się o jedno pole w prawo lub w lewo. Taka operacja nazywana jest [[Rozkaz (informatyka)|rozkazem]]. Maszyna Turinga jest sterowana listą zawierającą dowolną liczbę takich rozkazów. Liczby N i M mogą być dowolne, byle skończone. Czasem dopuszcza się też stan M+1, który oznacza zakończenie pracy maszyny. Lista rozkazów dla maszyny Turinga może być traktowana jako jej [[Oprogramowanie|program]].
