Вычислимость по Тьюрингу примитивно рекурсивных функций

Теорема 7.5. Функция f, полученная при помощи схемы примитивной рекурсии из правильно вычислимых по Тьюрингу функций g и h, является правильно вычислимой по Тьюрингу.

Доказательство. Не теряя общности, проведем доказательство для простейшей схемы примитивной рекурсии:

(7.3)

Для схемы (7.1) общего вида операция примитивной рекурсии реализуется аналогично. Опишем выполнение операции в виде композиции машины Тьюринга, осуществляющих циклические вычисления значения , а именно: необходимо вычислить значение . На каждом шаге описываемого цикла на ленте машины Тьюринга будем записывать три блока

 

где . Согласно (7.3) имеем , поэтому при завершении каждого шага цикла производится следующая проверка. Если , то есть , то . Если , то есть , то блоки и затираются и на ленте остаётся . В начале на работы на ленте записано:

 

Очевидно, что реализуемы следующие машины Тьюринга:

инициализация цикла, занесение на ленту значений ;

реализует ;

реализует ;

вычисление , где примитивная рекурсивная функция;

реализует разветвление по условию ;

стирает блоки после завершения цикла.

Совместная работа этих МТ осуществляется согласно схеме, представленной на рис. 7.2 ¡.

Следствие. Всякая примитивно – рекурсивная функция вычислима по Тьюрингу.

 

Функции Аккермана

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

 

Теорема 7.6. Существует функции, не являющиеся примитивно рекурсивными.

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

 

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

Эти функции связаны между собой рекурсивными соотношениями:

Продолжим эту последовательность, положим по определению для :

(7.4)

Первое из равенств (7.4) предназначено для того, что функции были всюду определены. Схема (7.4) имеет вид примитивной рекурсии и, следовательно, все функции примитивно рекурсивны. Растут они крайне быстро. Так,

Значение получается в результате возведения числа в степень раз.

Зафиксируем значение . Получим последовательность функций от одного аргумента: ,… Рассмотрим функции:

, .

Функция перечисляет последовательность ,… Функция называется функцией Аккермана [2]; диагональной функцией Аккермана.

На основании введенных обозначений и соотношений (7.4) для справедливо:

(7.5)

Схема (7.5) похожа на схему примитивной рекурсии, но примитивная рекурсия ведется по одному аргументу, а в схеме (7.5) – сразу по двум переменным (такая рекурсия называется двойной или рекурсией второй степени). При этом усложняется характер упорядочения точек, а следовательно, и понятие предшествующей точки. Это упорядочение не определено заранее, так как в схеме примитивной рекурсии, где число всегда предшествует числу , а выясняется в ходе вычислений и для каждой схемы (7.5), вообще говоря, различно. Так, , а так как , то вычислению по схеме (7.5) должно предшествовать вычисление значения : . Аналогично, вычислению значения должно предшествовать вычисление значения и так далее. Таким образом, и вычислимы по схеме (7.5), следовательно, вычислимы по Тьюрингу. Покажем, что и не является примитивно рекурсивными.

Рассмотри свойства функции :

Введем понятие мажорируемой функции. Функция называется мажорируемой, если

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

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

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