Машины Тьюринга. Операции с машинами. Тезис Черча

Описание машины Тьюринга:

1. Конечная лента, разбитая на конечное число клеток(ячеек). В процессе работы машины к ленте могут пристраиваться новые ячейки. В каждой ячейке ленты записан один из конечного числа символов, составляющих внешний алфавит . Клетка, в которой записан символ  , обычно обозначаемый 0, называется пустой. Все вновь пристраиваемые клетки являются пустыми.

2. внутренняя память – некоторое устройство, которое в каждый момент находится в одном из конечного числа «состояний», составляющих внутренний алфавит Q={q₀,q₁,…,q_n}. Состояние q₀ называется заключительным.

3. Управляющая головка – некоторое устройство, которое может помещаться вдоль ленты так, что в каждый момент находится в определенной ячейке, или «обозревает» эту ячейку.

4. Механическое устройство, которое в зависимости от содержимого обозреваемой ячейки и состояния внутренней памяти может изменить состояние внутренней памяти и при этом либо изменить содержимое ячейки (обозреваемой), либо сдвинуть управляющую головку в соседнюю ячейку слева или в следующую ячейку справа.

Машинное слово машины Тьюринга (иначе – конфигурация):

a_j, a_j2,…, qa_jk…a_jz

Работа машины состоит в последовательном переходе от одной конфигурации к другой в результате выполнения команды.

Команды машины Тьюринга: q_ja_i→q_sa_r, q_ia_j→q_sR, q_ia_j→q_sL.

Совокупность команд называется программой.

Функции, вычислимые по Тьюрингу.

Композиция машин Тьюринга.

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