Машина Тьюринга

Машина Тьюринга складається з необмеженої в обидва боки стрічки, розділеної на гнізда, послідовно пронумеровані цілими числами, як позитивними, так і негативними.

У кожнім гнізді стрічки може стояти будь-який символ із заданого алфавіту, у якім виділений «порожній» символ — ознака того, що гніздо порожнє.

Машина має кінцеву безліч внутрішніх станів, початкове (з нього починається робота машини) і кінцевий стан, потрапивши в яке машина припиняє роботу.

Крім стрічки є головка читання/запису, який уміє рухатися вперед, назад і стояти на місці; уміє читати вміст, стирати й записувати символи з даного алфавіту; управляється програмою.

Програма — це таблиця, у якій у кожній клітці записана команда. Кожна клітка визначається двома параметрами — символом алфавіту й станом машини. Команда — ця вказівка, куди пересунути головку читання/запису з поточного стану, який символ записати в поточне гніздо й у який стан перейде машина.

Машина Тьюринга — це модель комп’ютера.

Машина одержала ім’я математика А. Тьюринга (Англія) і вирішує наступну проблему: якщо для рішення завдання можна побудувати машину Тьюринга, вона алгоритмічно розв’язна.

І машина Тьюринга, і машина Поста еквівалентні по своїх можливостях.

Розроблені практично в те саме час (в 1936 р.) незалежно друг від друга.

чи Можна будь-який алгоритм представити у формі машини Тьюринга? Відповідь на це питання дається у вигляді так званого тези Тьюринга: усякий алгоритм представимо у формі машини Тьюринга. Це теза тому, що його неможливо довести, тому що в ньому фігурують, з одного боку, інтуїтивне поняття «усякий алгоритм», а з іншого сторони — точне поняття «машина Тьюринга».

Клас нормальних алгоритмів Маркова й клас алгоритмів, представлених у формі машин Тьюринга, збігаються.