Предполагается, что универсальный исполнитель должен уметь доказывать существование или отсутствие алгоритма для той или иной задачи.

Тезис Чёрча-Тьюринга:

Любой алгоритм может быть представлен как программа для машины Тьюринга. Алгоритм - это программа для машины Тьюринга

 

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

Примеры работы машины Тьюринга

Задача 1. ¹

На ленте записано число в двоичной системе счисления. Каретка находится где-то над числом. Требуется увеличить число на единицу.

Чтобы решить задачу, нам нужно:

-определить алфавит машины Тьюринга А,

- определить набор состояний Q,

- составить программу (т.е. для каждой пары (аi,qi) определить команду автомата.)

Алфавит машины Тьюринга, работающей с двоичными цифрами будет включать цифры 0, 1 и пробел a0. Т.е. А={1,0,a0}.

Определим возможные состояния:

1. q1 - автомат ищет правый конец слова (числа) на ленте

2. q2 - автомат увеличивает число на 1, проходя его слева направо и останавливается, закончив работу.

Напишем программу:

1 часть. q1 - автомат ищет правый конец слова (числа на ленте)

1)если в рабочей ячейке записано 0 - переместиться вправо

2)если в рабочей ячейке записано 1 - переместиться вправо

3) если в рабочей ячейке пробел, переместить каретку влево и перейти в состояние q2

Составим таблицу переходов для q1 т.о.:

	q1
	0 → q1
	1 → q1
a0	a0 ← q2

2 часть. q2 - автомат увеличивает число на 1, проходя его слева направо и останавливается, закончив работу.

1) если в рабочей ячейке записана цифра 0, записать в нее 1 и стоп

2) если в рабочей ячейке записана цифра 1, выполнить перенос в старший разряд — записать в ячейку 0 и переместиться влево.

3) если в рабочей ячейке пробел, записать в нее 1 и стоп.

Добавим в нашу таблицу состояние q2:

алф\состояния	q1	q2
	0 → q1	1. q0
	1 → q1	0 ←
a0	a0 ← q2	1. q0

Построенная таблица и есть программа для машины Тьюринга.