Машина Тьюринга складається з нескінченної стрічки, розбитою на клітини (осередки) рівної величини. У кожному осередку може бути записана в точності одна буква. Порожня клітинка означає наявність в ній порожній літери. Для пересування стрічки машина забезпечена простим стрічкопротяжним механізмом, який дозволяє пересувати стрічку на одну клітинку вліво або вправо. Для того щоб вважати написаний на стрічці символ і записати його на стрічку, машина Тьюринга забезпечена головкою читання - записи. При цьому головка за один прийом може прочитати тільки одну букву, написану на тій комірці стрічки, яка розташована під головкою. Читання літери не замінює того, що написано в осередку
Основною частиною машини Тьюринга є логічний блок, на якому є кнопка запуску. При її натисканні логічний блок приймає початковий стан і починає працювати:
1. він змушує головку прочитати букву, яка знаходиться на стрічці під головкою;
a записати на стрічці в тій клітці, що знаходиться під головкою, деяку букву;
b пересунути стрічку вліво, вправо або залишити на місці;
c змінити свій власний стан;
3. якщо в результаті дій, зазначених у пункті 2, літера, розташована під головкою, положення стрічки і стан логічного блоку машини залишаться такіміже, якими вони були безпосередньо перед виконанням цих дій, тоді машина зупиняється. У всіх інших випадках логічний блок повертається до виконання пункту 1.
- якийсь алфавіт Р = о, ..., pi. рn>, що містить букви, які можуть бути записані на стрічці. Цей алфавіт називається алфавітом машини Тьюринга;
- алфавіт А = 1. a2. ..., am>, що містить стану, в яких може перебувати логічний блок;
- алфавіт D = -1. d0. d1>, призначений для позначення руху стрічки вліво або вправо і зупинки стрічки.
Пам'ятаємо, що алфавітом ми називаємо сукупність упорядкованих в певному сенсі символів в даній мові або системі. Ці символи називаються буквами. Тільки символи, що належать даному алфавітом, можуть використовуватися для побудови слів.
Опишемо поведінку машини Тьюринга при виконанні логічним блоком пункту 2, відповідно до наведених позначеннями.
Якщо головка читає букву pi. і блок знаходиться в стані ai. то поведінка машини визначається записом px dy az. яка відповідає командам:
записати на стрічці замість букви pi букву рх;
здійснити переміщення стрічки dy;
перейти логічного блоку в стан az.
Очевидно, що від реакції на поєднання pi. aj для i ≠ j буде залежати робота машини Тьюринга. Реакцію машини на поєднання pi. aj можна представити у вигляді таблиці, в клітинах якої стоять трійки символів виду px dy az.
Якщо записати на стрічці деякий слово в алфавіті Р і натиснути кнопку запуску, то в результаті роботи машини можливі два результати:
робота машини після кінцевого числа кроків припиниться. При цьому слово, записане на стрічці, будемо називати результатом її роботи, тобто машина може бути застосована до вихідних даних;
машина ніколи не зупиниться, тобто результат: машина ніколи не видасть і не може бути застосована до вихідних даних.
Відповідність, яке встановлюється машиною Тьюринга між тими вихідними даними, до яких вона може бути застосована, і результатами її роботи, представляє деяку целочисленную неотрицательную функцію f (x).
Нехай задана функція f (x) = х +1, при х≥ 0. Побудувати машину Тьюринга, що реалізує цю функцію.
1) введемо умовні позначення і визначимо початковий стан стрічки:
a) значення х будемо записувати на стрічці у вигляді рядка, що складається з одиниць, а порожні клітини будемо позначати нулями;
b) розташуємо стрічку так, щоб найлівіша одиниця перебувала під головкою;
c) переведемо логічний блок в початковий стан ai;
2) проаналізуємо роботу логічного блоку:
a) якщо в стані ai головка вважає символ 1, то потрібно, щоб логічний блок знову записав в цей осередок 1, стрічку просунув на одну позицію вліво і сам залишився в колишньому стані ai;
b) якщо в стані ai головка вважає символ 0, то геологіч-ський блок повинен записати в цей осередок 1, стрічку залишити в цій же позиції і сам перейти в стан а2;
c) перебуваючи в стані a2 і при зчитуванні головкою символу 1, логічний блок повинен знову записати в цю клітку 1, стрічку не переміщувати і залишатися в стані А2. При цьому машина зупиниться;
3) побудуємо функціональну таблицю машини Тьюринга, що обчислює значення функції f (х) = х + 1, при х≥0:
e) після четвертого кроку відбудеться зупинка машини, і на стрічці буде записано значення функції у вигляді відповідного числа клітин, заповнених символами 1.
Якщо для обчислення функції f (x) існує алгоритм, за яким можна побудувати машину Тьюринга, то таку функцію будемо називати обчислюваною по Тьюрингу.
Основна теза Тьюринга можна сформулювати наступним чином: «Для будь-якої обчислюваної функції можна побудувати машину Тьюринга, що реалізує цю функцію».