Одне з уточнень понять алгоритму було дано Постом і А. Тьюрінг незалежно один від одного в 1936-1937гг. Основна думка їх полягала в тому, що алгоритмічні процеси - це процеси, які може здійснити відповідним чином влаштована "машина". Ними були описані гіпотетичні (умовні) пристрої, які отримали назву «Машина Поста» (МП) і «Машина Тьюринга» (МТ). Так як в них багато спільного, то згодом їх стали називати машинами Тьюринга.
Машина Тьюринга складається з наступних частин:
1. Інформаційної стрічки, що представляє нескінченну пам'ять машини. Це магнітна або паперова нескінченна стрічка, розділена на осередки. У кожному осередку можна помістити лише один символ, в тому числі нуль.
2. Голівки, що зчитує - чутливого спеціального елемента, здатного оглядати вміст комірок. Стрічка може переміщатися уздовж головки так, що в кожен момент часу головка оглядає одну клітинку.
3. Керуючого пристрою (УУ), яке в кожен момент часу знаходиться в деякому стані. Число станів звичайно. Одне з станів називається заключним.
Безліч символів, які записуються в інформаційній стрічці 1, S2, ...., Sm>, складають зовнішній алфавіт МТ.
При цьому S1 відповідає порожньому символу.
Безліч станів, в яких може перебувати УУ, позначимо 1, q2, ..., qn>. Серед станів одне відповідатиме значному, при якому МТ зупиняється.
Крім того, УУ виробляє три команди на переміщення стрічки: П, Л, Н, де
П - оглядати сусідню праворуч осередок;
Л - оглядати сусідню зліва осередок;
Н - продовжувати оглядати ту ж комірку.
Робота машини відбувається в дискретному часі. У кожен момент часу МТ, перебуваючи в стані qi. оглядає на стрічці символ Sk. потім переходить в стан qj. замінює Sk на символ Sl і пересуває стрічку (або ні) на одну клітинку.
Голівки, що зчитує і керуючий пристрій утворюють логічний блок. який представляє з собою (2,3) - полюсник.
qi Sk qj Sl П (Л, Н)
Таким чином, команда МТ задається п'ятіркою символів: qi. Sk. qj, Sl. П, а сам ЛБ є по своїй суті кінцевим автоматом.
Структура МТ має наступний вигляд:
Q - осередок зберігає символ стану, а Р - осередок - символ зсуву. У них відбувається затримка даних символів до початку наступного такту.
В якості початкової інформації на стрічку можна подати будь-яку кінцеву послідовність символів зовнішнього алфавіту U. Якщо після кінцевого числа тактів МТ зупиняється, подаючи сигнал про зупинку, а на стрічці виявляється інформація B, то кажуть, що машина може бути застосована до послідовності U і переробляє її в послідовність B.
Якщо зупинка і сигнал про зупинку ніколи не надходять, то кажуть, що МТне застосовна до послідовності U.
Розглянемо функціонування МТ на прикладі складання двох чисел, які будемо зображати у вигляді набору одиниць.
Зовнішній алфавіт буде складатися з символів:, де Ù - порожній символ.
Внутрішній алфавіт буде складатися з чотирьох символів 1. q2. q3.>, де символ q1 означає початковий стан, а. - заключне стан.
Нехай на стрічці записана початкова інформація: