Машина Тьюринга - це математична модель ідеалізованого обчислювального пристрою.
Машина Тьюринга T повністю визначається:
- програмою, тобто послідовністю команд.
Складовими частинами машини Тьюринга є:
- стрічка досить великої довжини, що складається з осередків;
- покажчик, який позначає поточну комірку на стрічці; покажчик може змінювати символ в поточному осередку і переміщатися відповідно до заданої командою;
- внутрішня пам'ять, яка містить поточний внутрішній стан машини qi.
Команда машини Тьюринга має загальний вигляд:
де qi - внутрішній стан машини в даний момент; ai - символ в поточному осередку стрічки; qj - внутрішній стан в наступний момент; aj - символ, на який змінюється символ ai; D = - напрямок руху покажчика, де R - вправо, L - вліво, S - залишитися на місці (зазвичай S опускають).
Частина команди до символу «®» називається лівою частиною команди, а після символу «®» - правою.
Кінцевий набір команд утворює програму.
Внутрішній стан q1 вважається початковим, а стан q0 вважається заключним. Як тільки машина Тьюринга переходить в стан q0. виконання команд припиняється.
Машина Тьюринга працює в часі, яке вважається дискретним, і його моменти пронумеровані 1, 2, 3, .... У кожен момент часу виконується тільки одна команда.
Зазвичай, алфавіт A складається з двох символів:
де 0 - порожній символ. Осередок, в якій записаний порожній символ, вважається порожньою.
Машинним словом називається послідовність непустих символів на стрічці. Слова, розділені одним або декількома пустими символами, утворюють пропозицію.
У наступному прикладі на стрічці записано слово, що складається з чотирьох символів алфавіту A = 1; a2; a3>. Машина знаходиться в стані q1. а поточної є перша осередок (за матеріальним становищем покажчика).
Стан машини Тьюринга m (k) включає вміст комірок стрічки, положення покажчика і значення внутрішнього стану qi. Під впливом програми відбувається зміна стану машини:
m (0) ® m (1) ® ... ® m (p).
Визначимо обчислення числових функцій на машині Тьюринга. Під числовими функціями будемо розуміти функції, значеннями яких і значеннями їх аргументів є невід'ємні цілі числа, які кодуються так. Число M будемо ставити набором з M + 1 одиниць, який будемо позначати 1 M + 1. наприклад:
0 будемо задавати 1
Машина Тьюринга називається універсальною, якщо вона може при певних початкових вхідних даних обчислити будь-яку функцію, яка обчислюваних на будь-якої машині Тьюринга.
Якщо машина, почавши роботу з деяким словом (словами), прийде в заключне стан q0. то вона називається застосовної до цього слова (словами), і результатом її роботи вважається слово (слова), яке записано на стрічці в заключному стані. Якщо машина ніколи не переходить в завершальний стан, то вона називається непридатною до даного слова (словами) і результат її роботи не визначений.
Приклад 2.4. Побудувати машину Тьюринга для алфавіту A =, яка перетворює слово x1 x2 ... xn в слово x2 x3 ... xn x1. де xi =, а решта осередки на стрічці залишаться порожніми.
Рішення. Програма завдання включає наступні команди: