Тезис Чёрча. Класс алгоритмически (машинно) вычислимых частичных функций совпадает с классом всех частично рекурсивных функций.

4.3. машина тьюринга-поста

Машины Тьюринга-Поста - это пример алгоритма. Придуман этот алгоритм независимо Аланом Тьюрингом и Эмилем Постом. Машина Тьюринга-Поста X состоит из следующих «частей»:

1. Ленты, разбитой на конечное число ячеек.

2. Внешней памяти, принимающей одно из состояний, входящих в множество А = {оо, oi,От}- Ячейки ленты находятся в одном и только в одном из состояний из множества А. Состояние оо называется пустым.

3. Внутренней памяти, принимающей одно из состояний, входящих в множество Q = {qo,qi, •••,?«}• Состояние qo называется «стоп».

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

5. Механического устройства, передвигающего головку и меняющего состояния внешней и внутренней памяти. Если головка в состоянии q стоит напротив ячейки с номером к, то изменения состояния внутренней памяти и состояния ячейки происходят одновременно.

Рис. 4.1: Машина Тьюринга-Поста.

Работа машины Тьюринга-Поста X осуществляется посредством команд, которые выполняет механическое устройство. Команда имеет один из следуюш;их трех возможных видов:

Qsai - qtaj, Qsai - qtL, qsai - qtR,

где L - это движение головки влево на одну ячейку, а Д - вправо. При этом всегда самое левое в записи команды qs ф qo-

Смысл команд таков: если головка в состоянии qs обозревает ячейку в состоянии Oi, то в первом случае она меняет свое состояние пг. qt, а ячейки на Oj, во втором случае - свое состояние на qt и сдвигается влево и, наконец, в третьем - вправо.

Конечный набор команд образует программу.

Состояние машины X - это последовательность состояний aji,...,Oj ячеек ленты, состояние внутренней памяти gs головки и номер fe воспринимаемой (читаемой) ячейки в состоянии ajj,.

Состояние машины X записываем в виде

Oii...ai i?Oi,...Oi, (4.4)

и называем машинным словом т в алфавите AU Q. Символ да может быть самым левым, но не может быть самым правым в машинном слове, так как справа от него должно быть считываемое состояние ячейки.

Под воздействием программы происходит изменение состояния машины, сопровождающееся переделкой исходного машинного слова

nn-m ... •т

4.3.1. Вычисления функций на машине Тьюринга-Поста

Пусть m машинное слово в алфавите Аи Q машины X. Вычеркнем из слова m букву ао и буквы из Q. Получаем редуцированное слово [тп].

Редуцированное слово [т] перерабатывается машинной X в (редуцированное) слово Ь, если для некоторой программы ф и некоторого р

qiao[m] (?iOo[m]) ... (lOoN)" go е (giaofmD"), b = [(giaoN)"].

Символически факт переработки слова [т] записываем в виде

Ь = Щт)\).

Если ни для какого натурального р не выполняется условие

то говорят, что машина неприменилм к слову [т]. В этом случае выражение ф([т)] является неопределенным.

Пусть /(г) функция, определенная на словах редуцированного алфавита [А] = {ai,am}- Если для каждого слова Г в этом алфавите

/(t)=?(t),

то говорим, что машина X вычисляет функцию /. Машинное предложение - это выражение вида

aotiaot2ao...aott,

где ti слова в словаре [А].

Программа ф перерабатывает машинное предложение в редуцированное слово Ь, если

дюоГюоГзоо.-.аоГг (qiaotiaot2ao...aott)- ...

... -i- (дюоГюоГзоо-.ооГг)"

до е iqiaotiaot2ao...aott)\ Ь = [(дюоГюоГгоо.-.ооГг])"]. Символически

Ь = ф(г1,Г2,...,г*). Если /(Г1,...,Г() - частично словарная функция, т.е. функция, определенная на словах некоторого редуцированного алфавита [А] = {ai,От}, обладает свойством

/(ri,...,rt) =ф(Г1,Г2,...,Г(), то говорим, что она вычислима на машине X.

Теорема 4.1. Все частично словарные функции, вычислимые на машине Тьюринга-Поста, являются частично рекурсивными.

Доказательство. См. [26, с.228].

Теорема 4.2. Для любой частично рекурсивной функции существует вычисляющая ее машина Тьюринга-Поста.

Доказательство. См. [26, с.230].