Доказательство. 4 страница

)

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

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

Пример. Найдем шифр машины Тьюринга, вычисляющую функцию .

Программа вычислений имеет такой вид ()

и машина имеет такой шифр

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

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

Пример. Программа машины , не содержит состояния , поэтому машина не может попасть в это состояние и, следовательно, является несамоприменимой.

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

Проблема самоприменимости. Пусть арифметическая функция определена следующим образом

Существует ли машина Тьюринга в алфавите , которая правильно вычисляет функцию ?

Будем считать, что машина будет оставлять на ленте одну единицу в случае, если слово на ленте в начальной конфигурации было шифром некоторой самоприменимой машины, и будет оставлять 0, если слово на ленте в начальной конфигурации было шифром некоторой несамоприменимой машины.

Теорема. Проблема самоприменимости алгоритмически неразрешима

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

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

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

Очевидно, что каждая из машин Тьюринга в алфавите является либо самоприменимой, либо несамоприменимой. Определим к какому классу относится машина . Для этого на ленте запишем шифр этой машины и запустим её. Если машина самоприменимая. то ее шифр является шифром самоприменимой машины, и машина будет действовать так, как описано выше, т.е. машина никогда не попадет в заключительное состояние и, следовательно, самоприменимой быть не может.

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

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

2.5 Примитивно рекурсивные функции

Часто решение поставленной задачи можно свести к вычислению некоторой целочисленной функции, определенной на множестве натуральных чисел. Этот раздел посвящен уточнению понятия алгоритма – классу частично рекурсивных функций. Этот подход к формализации алгоритма был разработан в 30-х годах прошлого столетия математиками К. Гёделем, С.К. Клини, А. Черчем

Будем рассматривать n- арные функции на множестве наборов натуральных чисел . Такие функции назовем арифметическими функциями. Если функция определена не для каждого набора натуральных чисел, то такие функции будем называть частично определенными арифметическими функциями (ЧАФ).

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

Определим класс функций, следующим образом. Выделим конечное множество базовых функций и операции над ними для получения новых функций. В качестве базовых функций берут следующие функции:

· функция следования: ;

· функция проекции: , где n – кол-во переменных, а , , – номер переменной, по которой берется проекция. Функция проекции – функция, равная одному из своих аргументов. Например, .

· функция нуля: , для всех

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

Определим операции над функциями. Пусть имеются n - арная функция f и m -арные функции . Говорят, что m -арная функция получена в результате операции суперпозиции или подстановки из функций и , если для любых

Пусть заданы произвольные функции: n - арная функция g и n+2 - арная функция h. Говорят, что n+1 - арная функция f получена операцией примитивной рекурсии из функций g и h, если для любых выполнены соотношения

,

.

В случае если , то определение имеет такой вид. Говорят, что функция получена операцией примитивной рекурсии из функции и константы С, если для любого выполнены соотношения