Математическая логика и теория алгоритмов: Методические указания к практическим занятиям, страница 10

Машина имеет бесконечную в обе стороны ленту, разбитую на ячейки, в которых записано по одной букве  из 

В каждый момент времени (такт работы) машина находится в одном из состояний из    и  «обозревает»  одну ячейку ленты.

По команде     где     или     или    отсутствует, означающей, что  машина в состоянии     обозревает ячейку, в который записана буква      машина переходит в состояние      в обозреваемой  ячейке    заменяет буквой   Затем машина переходит к обозреванию ячейки  справа  при     или  слева  при     Если же     в команде отсутствует, то машина продолжает  «обозревать»   ту же ячейку, куда записана буква  

На следующем такте работы машины выполняется следующая команда программы и так далее, до выполнения всей программы целиком.

Определение 16.  Словом   в алфавите     или в алфавите     или в алфавите      называется любая последовательность букв соответствующего алфавита. Под  ой  конфигурацией  понимается изображение ленты машины с информацией, сложившейся на ней к началу  го такта (или слово в алфавите    записанное на ленте к началу го такта), и с указанием того, какая ячейка обозревается в этот такт и в каком состоянии  находится машина.

Имеют смысл лишь  конечные конфигурации, когда лишь конечное число ячеек заполнено, остальные пусты.

Определение 17. Говорят, что непустое слово    в алфавите    воспринимается машиной  в стандартном положении, если это слово записано в последовательных ячейках ленты, остальные ячейки пусты, а машина  «обозревает»  самую правую из тех ячеек, где записано слово  Стандартное положение называется  начальным (заключительным),  если  машина находится в состоянии     (в состоянии  ). Говорят, что слово     перерабатывается  машиной в слово    если от слова    в начальном  стандартном положении машина переходит к слову    в заключительном стандартном положении после выполнения всей программы.

Определение 18.  Пусть на множестве слов алфавита        задана  местная функция,  значениями которой  являются  слова в том же алфавите.

Предположим, что имеется машина Тьюринга с алфавитом     где      которая любой набор из      слов, входящий в область определения функции, записанный  на ленту последовательно с промежутками в одну ячейку между словами, перерабатывает в слово, являющееся значением функции на этом наборе, а на любом наборе из       слов, не  входящих в область определения функции, машина работает бесконечно. Тогда говорят, что машина Тьюринга вычисляет данную функцию, а сама функция называется вычислимой по Тьюрингу или, короче, вычислимой.

Основная гипотеза  (тезис Тьюринга-Чёрча, Алонзо Чёрч –  американский математик и логик), связывающая понятие алгоритма и вычислимой функции, формулируется так: всякая функция, для нахождения значения которой имеется некоторый алгоритм, является вычислимой, то есть этот алгоритм  может быть реализован, если должным образом подобрать машину Тьюринга.

Тезис  Тьюринга-Чёрча  является аксиомой, состоятельность которой подтверждена опытом работы  математиков ([3], c. 231).

Упражнения

      1. Применение машины Тьюринга к словам. Имеется машина Тьюринга с внешним алфавитом    алфавитом  внутренних состояний    и программой из двух команд        Определить, в какое слово переработает машина каждое из  следующих слов, если она находится в начальном состоянии    и  «обозревает»  указанную ячейку:

a)     («обозревается»  ячейка 4, считая  слева);

б)     («обозревается»  ячейка 2);

в)     («обозревается»  ячейка 3).

Решение.  а)  Начальная конфигурация выглядит  следующим образом:

После выполнения команды      конфигурация изменится:

После выполнения команды         конфигурация приобретает вид:

и машина останавливается.

Получилось слово: