Частично-рекурсивные функции

Определение частично-рекурсивных функций

Будем рассматривать функции натурального аргумента:

f(x), где x N

 

 

всюду определенная функция частично определенная функция

Определим три базовые функции:

1. Ноль-функция

0(х)=0

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

2. Функция следования

s(x)=x+1

3. Функция взятия аргумента

, где

m –m-местная функция,

n – порядковый номер аргумента, значению которого равно значение функции.

Определим три типа операций:

1. S – суперпозиция:

Пусть нам даны функции: g( и ( … (.

Тогда можно определить новую функцию:

f( =g( ( … ()) S(g, )

2. R - примитивная рекурсия:

Пусть нам даны функции: g( =g() – n-местная функция и h( – (n+2)-местная функция.

Тогда может быть определена новая (n+1)-местная функция:

f( =R(g,h)= = ,

т.е. функция определяется через себя же.

Предположим, что некоторое значение при , тогда для y> значение функции будет не определено (f() – не определено f(y) при y> будет не определено).

Как S, так и R, будучи применимыми ко всюду определенным функциям, дают всюду определенную функцию.

3. M – операция минимизации:

Пусть дана n-местная функция g(. Будем рассматривать уравнение относительно y (y ):

g( =

Решать будем следующим образом: будем перебирать значения y, начиная с 0. Как только получим первое значение, которое удовлетворяет уравнению, мы получим минимальное решение данного уравнения.

=M(g( = )

 

Частично рекурсивные функции (ЧРФ) – это функции полученные с помощью конечного числа использований операций R, M, S к функциям O(x), S(x), (Под x везде понимаем множество

Данное определение можно представить в следующем виде:

1) , где - класс ЧРФ

2)

3)

4)

5) Других ЧРФ нет

Примеры ЧРФ

1.

 

2. Функция является рекурсией от функций

 

3.

4.

 

5. Sg(x) =

6.

 

7.

8.

 

9.

 

 

 

– целая часть от деления

 

- остаток от деления

 

- отлична от нуля в конечном количестве точек

 

- количество простых чисел < x

 

– простое число

 

Фактически любая функция, которую можно вычислить может быть получена путем использования операций S,M,R к функциям O(x), S(x),

Тезис Чёрча

В классе ЧРФ можно выделить 2 подкласса:

- общерекурсивные функции

- примитивно рекурсивные функции - функции, полученные без операции минимизации

Существует ли функция принадлежащая классу которую нельзя было бы получить с помощью операций R и S?

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

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

Тезис Черча: Всякая вычисляемая(рекурсивная) функция является ЧРФ.

Это утверждение принципиально недоказуемо т.к. есть принцип неопределяемый класс вычислимых функций.

 

Соотношение между классами «Т» и «Ч»

Из тезисов Тьюринга и Черча следует что класс функций вычислимых по Тьюрингу совпадает с классом ЧРФ (в том случае если эти тезисы верны)

Т.е. если то тезис Тьюринга или Черча не верен, либо они оба не верны.

Это можно проверить, т.к. оба этих класса являются строго определенными.

Вычислимость по Тьюрингу ЧРФ

Для того чтобы доказать что необходимо доказать что 1) Ч с Т и 2) Т с Ч

Для того чтобы доказать первое утверждение необходимо доказать что:

1) являются функциями вычислимыми по Тьюрингу.

2) Операций S, M, R являются вычислимыми по Тьюрингу.

Докажем второй пункт, а первый это практика?

Построим машину вычисляющую суперпозицию

 

т.е. существуют

 

Вычислимость рекурсии

Существуют

В общем случае после каждого цикла

Да

Нет

 

Вычислимость минимизации

 

 

 

В общем случае после каждого цикла

Да

0

Нет

Существует доказательство что T с Ч Ч = T (данный вывод мы опустим)

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

Нумерации наборов чисел и слов

Нумерация пар чисел

Где - упорядоченная пара

Упорядочиваем пары x+y=n по n, а внутри скобок < > упорядочивание происходит следующим образом:

Например для x+y=n:

Т.е. начало будет выглядеть так:

При таком способе упорядочивания можем ввести функцию - характеризующая номер упорядоченной пары

– канторовский номер

Такая нумерация называется Канторовской.

Также возможно по известному номеру определить x и y

Для

9.2 Наборов из n чисел

Тогда в общем случае

9.3 Нумерация множества M=N&N²&…

Упорядочим элементы множества M которое имеет вид

- все возможные наборы натуральных чисел т.е. произвольный упорядоченный набор чисел

где n – количество чисел в наборе

…

Нумерация слов

Нумеровать можно не только наборы чисел, но и наборы слов.

1. Пусть есть алфавит множество всевозможных слов и символов этого алфавита и хотим упорядочить слова т.е. однозначно поставить каждому слову в соответствие номер. - слово из при этом

Можно интерпретировать каждый символ r-ичным числом, тогда слово будет представлено s-значным числом вида

2. Пусть количество символов в алфавите бесконечно и пусть такое бесконечное множество является счётным. Тогда алфавит называется счётным алфавитом. Можно поставить каждому символу в соответствие номер. Тогда слово может быть интерпретировано как набор чисел .

А как пронумеровать набор чисел было показано выше. Обозначим канторовский номер слова в счетном алфавите следующим образом где - канторовский номер набора чисел.

Для пустого символа канторовский номер будет равен нулю