Нумерация алгоритмов. Невычислимые функции

Нумерация машин Тьюринга

В качестве внешнего алфавита возьмём объединение алфавитов всех возможных машин Тьюринга.

- множество всех возможных внутренних состояний МТ

Внутренний и внешний алфавит являются бесконечными и счётными.

Упорядочим символы в этом алфавите

- перечисление символов объединенного алфавита

Каждому символу можно сопоставить номер

При таком общем алфавите каждая машина Тьюринга будет отличаться только набором команд

Упорядочим команды по левой части в лексикографическом порядке в соответствии с их следованием в перечислении и запишем в одно слово

Слово состоит из пятёрок символов, которые имеют свою структуру

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

Заменим каждый символ соответствующим номером

- код машины Тьюринга

Можно упорядочить все наборы машин Тьюринга в порядке возрастания их канторовских номеров.

Расположены по мере возрастания, но не подряд, т.е. к примеру, такого вида:

Канторовский номер не соответствует номеру машины Тьюринга.

Упорядочивание является эффективным, т.е. можно по коду МТ определить её номер и по номеру восстановить код и программу МТ

Определение номера по коду можно представить в виде следующего алгоритма

 

 

Нет

Да

Р

Ф(р)=1

L t1UKDXHTtVBSKC5JzEtJzMnPS7VVqkwtVrK34+UCAAAA//8DAFBLAwQUAAYACAAAACEAwrSDocQA AADaAAAADwAAAGRycy9kb3ducmV2LnhtbESPQWvCQBSE74X+h+UVeqsbbZEa3QSxVHoRMRX1+Mw+ k2D2bchuNfXXu4LgcZiZb5hJ2planKh1lWUF/V4Egji3uuJCwfr3++0ThPPIGmvLpOCfHKTJ89ME Y23PvKJT5gsRIOxiVFB638RSurwkg65nG+LgHWxr0AfZFlK3eA5wU8tBFA2lwYrDQokNzUrKj9mf UeDyaLhZfmSb7V7O6TLS+ms3Xyj1+tJNxyA8df4Rvrd/tIJ3uF0JN0AmVwAAAP//AwBQSwECLQAU AAYACAAAACEA8PeKu/0AAADiAQAAEwAAAAAAAAAAAAAAAAAAAAAAW0NvbnRlbnRfVHlwZXNdLnht bFBLAQItABQABgAIAAAAIQAx3V9h0gAAAI8BAAALAAAAAAAAAAAAAAAAAC4BAABfcmVscy8ucmVs c1BLAQItABQABgAIAAAAIQAzLwWeQQAAADkAAAAQAAAAAAAAAAAAAAAAACkCAABkcnMvc2hhcGV4 bWwueG1sUEsBAi0AFAAGAAgAAAAhAMK0g6HEAAAA2gAAAA8AAAAAAAAAAAAAAAAAmAIAAGRycy9k b3ducmV2LnhtbFBLBQYAAAAABAAEAPUAAACJAwAAAAA= " strokecolor="white [3212]">

Нет

Да

 

А восстановление кода МТ по номеру можно с помощью следующего алгоритма.

Нет

Да

L t1UKDXHTtVBSKC5JzEtJzMnPS7VVqkwtVrK34+UCAAAA//8DAFBLAwQUAAYACAAAACEAwrSDocQA AADaAAAADwAAAGRycy9kb3ducmV2LnhtbESPQWvCQBSE74X+h+UVeqsbbZEa3QSxVHoRMRX1+Mw+ k2D2bchuNfXXu4LgcZiZb5hJ2planKh1lWUF/V4Egji3uuJCwfr3++0ThPPIGmvLpOCfHKTJ89ME Y23PvKJT5gsRIOxiVFB638RSurwkg65nG+LgHWxr0AfZFlK3eA5wU8tBFA2lwYrDQokNzUrKj9mf UeDyaLhZfmSb7V7O6TLS+ms3Xyj1+tJNxyA8df4Rvrd/tIJ3uF0JN0AmVwAAAP//AwBQSwECLQAU AAYACAAAACEA8PeKu/0AAADiAQAAEwAAAAAAAAAAAAAAAAAAAAAAW0NvbnRlbnRfVHlwZXNdLnht bFBLAQItABQABgAIAAAAIQAx3V9h0gAAAI8BAAALAAAAAAAAAAAAAAAAAC4BAABfcmVscy8ucmVs c1BLAQItABQABgAIAAAAIQAzLwWeQQAAADkAAAAQAAAAAAAAAAAAAAAAACkCAABkcnMvc2hhcGV4 bWwueG1sUEsBAi0AFAAGAAgAAAAhAMK0g6HEAAAA2gAAAA8AAAAAAAAAAAAAAAAAmAIAAGRycy9k b3ducmV2LnhtbFBLBQYAAAAABAAEAPUAAACJAwAAAAA= " strokecolor="white [3212]">

Нет

Да

 

 

Перечисление МТ позволяет построить эффективное перечисление ЧРФ т.к. все ЧРФ могут быть … с помощью МТ

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

1. Рассмотрим функцию

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

Вывод: Существует бесконечное множество невычислимых функций.

2. Существование универсальной функции.

Пусть существует класс

- называется универсальной функцией класса F если:

1)

2)

Т.е. функция, содержащая в себе все функции одного класса.

 

Теорема 1: О существовании универсальной функции класса одноместный ЧРФ

Рассмотрим класс одноместных ЧРФ

И рассмотрим функцию

Докажем, что функция является универсальной функцией для класса одноместных ЧРФ.

1)

Функция является вычислимой т.к. существует алгоритм её вычисления ЧРФ

2) Выберем некоторую функцию из класса ЧРФ

- по определению функции U

Следствие

Для класса n-местных ЧРФ существует - местная универсальная функция

Доказательство:

1. т.к. является суперпозицией ЧРФ

2. Берем произвольную n-местную ЧРФ

И определим новую функцию от канторовского номера

– все переменные выражены только через канторовский номер

т.к. является суперпозицией

– универсальная одноместная функция, тогда

- универсальная ЧРФ

 

Для классов справедливы следующие теоремы:

 

Теорема 2: Не существует универсальной функции для класса общерекурсивных функций

 

Теорема 3: Для класса n-местных примитивно рекурсивных функций существует универсальная -местная общерекурсивная функция т.е. для