| Alan Turing |
Stworzony przez Alana Turinga - angielskiego matematyka, kryptologa, jednego z twórców informatyki - abstrakcyjny model komputera służącego do wykonywania algorytmów, składającego się z nieskończenie długiej taśmy podzielonej na pola to maszyna Turinga. Taśma może być nieskończona jednostronnie lub obustronnie. Każde pole może znajdować się w jednym z N stanów. Maszyna zawsze jest ustawiona nad jednym z pól i znajduje się w jednym z M stanów.
Zależnie od kombinacji stanu maszyny i pola 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 rozkazem. Maszyna Turinga jest sterowana listą zawierającą
dowolną liczbę takich rozkazów. Lista rozkazów dla maszyny
Turinga może być traktowana jako jej program.
Zależnie od kombinacji stanu maszyny i pola 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 rozkazem. Maszyna Turinga jest sterowana listą zawierającą
dowolną liczbę takich rozkazów. Lista rozkazów dla maszyny
Turinga może być traktowana jako jej program.
