Maszyna Turinga: Różnice pomiędzy wersjami

{{Dopracować|źródła=2017-08}}

'''Maszyna Turinga''' – stworzony przez [[Alan Turing|Alana Turinga]] matematyczny model obliczeń, który definiuje [[abstrakcja|abstrakcyjną]] maszynę służącą do wykonywania [[algorytm]]ów. Maszyna składa się z bloku sterowania, głowicy odczytującej i zapisującej oraz nieskończenie długiej taśmy. W każdej komórce taśmy może mieścić się jeden [[symbol]]. Maszyna zawsze jest ustawiona nad jednym z pól i znajduje się w jednym z Q stanów. Zależnie od kombinacji stanu maszyny i symbolu 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. 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]].