Понятие вычислимой функции. Разрешимые и перечислимые множества. Рекурсивные функции. Тезис Черча

Рассмотрим, что такое рекурсивная ф-ия. Пусть x,y – множества. Ф-ия отображения х в у назыв пара <D(f)=X,f>, где D(f) – обл определ, а f – обл значений. Частичная ф-я из Х в У назыв пара <D(f)ÎX,f> N –0 множество нат чисел. (N)ⁿ – n-кратное декарт произвед множ N на себя. <x1,х2…хn> - множество всевозможных n-ок натур чисел. (f)ⁿ (х1,х2…хn) – ф-я n-ок. Частичная ф-я f назыв вычислимой, если существует алгоритм, перерабатывающий любой объект х для к-го определена ф-я f в объект f(x) и не приводящий к результату, если xËD(f)

f(x): (N)^m®(N)ⁿ-вычислима «"хÎ(N)^m®f(x)Î(N)^m

где xÎD(f)

Фундаментальным открытием в теории вычислимости является Тезис Черча, к-й в слабейшей форме имеет след вид:

М явно указать, что 1)семейство простейших вычислимых ф-ий 2) семейство элементарных операций, к-е позволяют строить по одним вычислимым ф-ям др вычислимые ф-ии, с тем св-ом, что любая вычислимая ф-я за конечное число шагов, каждый из которых состоит в применении 1 из элементарных операций к ранее построенным или простейшим вычислимым ф-ям. Простейшие вычислимые ф-ии: succ(x)=x+1; zero(x)=0 – одноместная нулевая ф-я; p_iⁿ(x1,x2…xn)=xi (i-я n местная проекция); p₁¹(x1)=x1 (идентичность).

Элементарные операции: 1. Суперпозиция: (композиция, постановка). Она ставит в соответствие паре ф-ий f и g композицию ф-ий.

Для любых a,b,c: g(f1,f2)=g(f1(a,b),f2(c,b))

Принято обозначать S(g,f1…fn)

2. Примитивная рекурсия Сопоставленияе ф-ям g(x1…xn), h(x1…xn,y,z) определим ф-ю f, такую, что для любых натур чисел (x1,x2…xn,y) выполнялись бы след равенства: 1). f(x1,x2..xn,0)=h(x1,x2…xn), 2).f(x1…xn,y+1)=g(x1…xn,y,h(x1,x2…xn,y)).

Обозначается f=R(g,h)

Равенства 1) и 2) задают схему примитивной рекурсии и говорят, что эта схема индуктивно однозначно специфицирует ф-ию h.

Фии, к-е м получить из простейших фий с помощью операц суперпозиции и примитивных рекурсии назыв примитивно рекурсивными.

Фя сложения 2х фий примитивно рекурсивная

3. Операция минимизации сопоставляет фие f(x1…x(n+1)) фию h(x1…xn), такую что для любых x1,x2…xn,y, выполняется равенство:

f(x1,x2…xn)=y«f(x1…xn,0)

f(x1…xn,1)…

f(x1…xn,y-1), а ф-я f(x1…xn,y)=0 (н найти min значен этого уравн относительно y), y – наименьшее, для к-го выполняется данное равенство: h(x1…xn)=min{yÎN: f(x1…xn,y)=0} Если такого y не существует, то значение фии h счит неопределенным. Операция минимизации позволяет вводить вычисления перебор объектов для отыскания нужного в бесконечном множестве.

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

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

Тезис Черча: Всякую вычислимую фию м представить рекурсивно, т е рекурсивная фия явл универсальной алгоритмической моделью. U – универсальный алгоритм S(A) – код алг-а А

U(S(A),x)=A(x)

В любой универсальной алгоритмической модели существует универсальный алгоритм, т е такой алгоритм, кй м. моделировать работу любого др алгоритма, описанного средствами этой модели.