Частичные функции

ПРИМЕР f(x)-рекурсивная фун-ция (n+1)местная т. к. n=0, h-const=a,

(1): f(0)=a

(2): f(y+1)=

1ой и 2ой операторы из всюдуопределённых фук-ций могут получать всюду опред-ные фун-ции. т.е. операторы порождают всюдуопред-ные. Но это не значит что они порождают всё полное прост-во всюдуопред-ных фун-ций т. е. порождают замкнутый класс всюдуопред-ных фун-ций

ЗАМ. Недостающее множество всюду опред-нфх фун-ций порождается сл. оператором.

3)Оператор минимизации

Частичные фун-ции

которые опред-ся сл образом :

А)область определения

,

Б) равна наим. знач. для кот выполнено условие

=

ЗАМ. чобы построить полной пространство частич опред фун-ций с помощью опрета-ра минимизации необходимо брать более широкое мн-во одноместных фун-ций f, но не каждая фун-ция может обращаться в ноль, при каком-то значении n+1 аргумент фун-ции h может не СУщ-ать минимал значения y.

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

ЗАМ. Если мы не оговариваем конкретно с помощью каких операторов построена конкретная ф-ций, то в общем мы предпологаем, что исп опер. прим. рек. Поэтому общее название частич. опред. ф-ций=ЧАСТИЧНО_РЕКУРСИВНЫЕ Ф_ЦИИ. Если же конкретная ф-ция явл-ся всюдуопред-ной, то её будем наз-вать ОБЩАЯ рек-ная ф-ций. Если же ф-ций построена без помощи опре. минимизации, то назовем её ПРИМИТИВНО рекурсивной.

Идея Г-К состоит в том что все вычисляемый фун-ции явл-ся частично рекурс.,как и подходы других авторов с аналогичным тезисом(ток назв ф-ций другие)до сих пор нет строгого док-ва, но и не опровергнуто, а практически подтверждается. СУЩ-ют критерии кот-ый позваляют установить св-во ЧАСТИЧНОЙ рекурсив-ти сразу для общирных классов. ВЫВОД:сущ-ют обще рекурсивные ф-ции которые не могут быть постороенны без применения третьего оператора.

28.Примеры рекурсивности (примитивно-рекурсивных и общерекурсивных функций)

1, сложение двух чисел

SUM: ( X, Y )

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

1)SUM(X,0)=x — prпроекция

2)SUM(X, Y+1)=(X+Y)+1=S(SUM(X, Y)) ф-ция следования

1)и5)образуют оператор ПРИМЕТИВНОЙ рекурсии, а т. к. всюдуопределена, то она ОБЩЕРЕКУРСИВНА

2,Ф-ция перемножения

Prod: (x, y)=x*y

всюдуопределена

1)prod(x.0)=0 нулевая ф-ция

2)prod(x, y+1)=x*y+x=SUM(prod(y. x),x)

1)и2)-ПРИМЕТИВНОрекурсивнаяОБЩЕРЕКУРСИВНАЯ

3,Усечённое вычитание единицы

1)

ф-ция проэкции т. е. ОБЩЕРЕКУРСИВНАЯ

4,Усеченная разность

общерекурсивная

5,Модуль разности

6,Факториальная n!=1*2//(n-1)*n=

Ф-ла 1ого разряда

1)0!=1

7,Минимум от(x, y)

8,Знак числа

9,Остаток от целочисленного деления

2) (x, y+1)=prod(s( (x, y)),sg( | x — s( (x, y))| )

(29)исчисление – это безтиповая теория, которая рассматривает функции, как правила, а не как графики. В традиционном подходе: два представления выражают одну и ту же функцию, а с точки зрения исчисления они выражают разные функции, так как правила вычисления различны. исчисление – это прикладное исчисление предикатов 1-го порядка (ПИП 1-го порядка).