DJVU-STUDENT.NAROD.RU - информационный сайт для студентов и школьников

7. АЛГОРИТМЫ И РЕКУРСИВНЫЕ ФУНКЦИИ

Каждый алгоритм имеет входные и выходные данные и состоит из конечного числа инструкций. Например, алгоритм Евклида имеет на входе два положительных числа a и b, на выходе – их наибольший общий делитель. В качестве инструкций можно рассмотреть следующие команды:

1)сравнить a и b;

2)если a равно b, то установить наибольший общий делитель, равным a, и закончить работу;

3)если a > b, то установить a = a – b и перейти к 1;

если b > a, то установить b = b – a и перейти к 1.

Развитие математики требовало уточнения понятия алгоритма в связи с вопросами алгоритмической разрешимости проблем. Следующие свойства алгоритма были признаны характеризующими его среди методов построения математических объектов:

а) алгоритм состоит из шагов, на каждом из которых формируется система объектов, построенных в предшествующие моменты (дискретность алгоритма);

б) эта система объектов однозначно определяется системой в предшествующие моменты (детерминированность);

в) закон получения последующей системы объектов из предшествующих должен быть простым (элементарность шагов);

г) способ получения объектов на каждом шаге должен давать результаты (направленность);

д) начальная система объектов может выбираться из бесконечного множества (массовость).

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

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

7.1. ЧАСТИЧНО РЕКУРСИВНЫЕ ФУНКЦИИ

Под числовыми функциями мы понимаем функции f: Nn ® N, где N = w – множество всех натуральных чисел x ³ 0, Nn = {(x1,…,xn): x1ÎN,…,xnÎN} – его декартова степень. Частичной (числовой) n-местной функцией называется функция f: D ® N,

определенная на некотором подмножестве D Í Nn декартовой степени. Обозначим D через Dom(f) и будем называть её областью определения частичной функции f. Для

частичной n-местной функции f будем применять обозначения f: Nn ® N.

Простейшие функции

Функции s: N ® N, o: N ® N и Inm: Nn ® N, принимающие значения s(x) = x + 1,

o(x) = 0 и Inm(x1,…,xn) = xm, для всех x, x1,…,xn Î N и n ³ m ³ 1, называются простейшими. Операции над функциями будут называться операторами.

Выделим операторы, с помощью которых будут строиться вычислимые функции. Применяя эти операторы к простейшим функциям, мы получим частично рекурсивные функции.

Композиция частичных функций

DJVU-STUDENT.NAROD.RU - информационный сайт для студентов и школьников

Частичные функции f: A ® B можно определить как функции, заданные на неко-

торых подмножествах Dom(f) Í A и принимающие значения в B. Если Dom(f) = A, то f называется определенной всюду. В некоторых случаях частичные функции удобно рассматривать как определенные всюду. С этой целью к каждому множеству добавляется бесконечно удаленная (или отмеченная) точка *. Произвольная частичная

функция f: A ® B расширяется до функции f : A È {*} ® B È {*} по формулам f (x) = f(x) для x Î Dom(f) и по формулам f (x) = * для всех остальных x, включая *. С другой стороны, каждая функция g : A È {*} ® B È {*} определяет частичную функцию g: A ® B, принимающую значения g(x) = g (x) для x Î g -1(B). Ясно, что область Dom(g) = g -1(B) состоит из точек, не отображающихся в бесконечно удаленную. Соответствие, сопоставляющее частичным функциям f функции f является взаимно однозначным. Рассматривая частичные функций f как их расширения f , легко определить композицию частичных функций f: A ® B и g: B ® C. Если f и g определены всюду, то

композиция совпадает с обычной. В общем случае область определения композиции g×f состоит из точек x Î A, таких, что g(f(x)) ¹ *.

Пусть f1,…,fn: Nm ® N – частичные функции. Определим частичную функцию (f1,

…,fn): Nm ® Nn, полагая

(f1,…,fn) (x) = (f1(x),…,fn(x)) для всех x Î Dom(f1) Ç… Ç Dom(fn) ÍNm.

Пусть f1,…,fn: Nm ® N и g: Nn®N – частичные функции. Оператор суперпозиции (или композиции) Sn+1 сопоставляет им частичную функцию:

Sn+1(g, f1,…,fn) = g ° (f1,…,fn).

Областью определения частичной функции g ° (f1,…,fn) является подмножество точек x = (x1,…,xm) Î Dom(f1) Ç…Ç Dom(fn), для которых (f1(x),…,fn(x)) Î Dom(g).

Пример 1

Рассмотрим частичные функции g: N2® N, f1: N® N, f2: N® N, принимающие значения g(x1,x2) = x1 – x2, f1(x) = x/2, f2(x) = x/3. Функция f1 определена для четных x; f2

Dom(g ° (f1,f2)) состоит из z Î 6N, удовлетворяющих неравенству z/2 ³ z/3. Поскольку это неравенство выполнено для всех z, то область равна 6N. Если поменять местами f1 и

f2, то область определения суперпозиции изменится. Она будет состоять из z Î 6N, удовлетворяющих z/3 ³ z/2. Следовательно, Dom(S3(g, f2, f1)) = {0}.

Оператор примитивной рекурсии

Пусть заданы частичные функции g: Nn ® N и h: Nn+2 ® N. Оператором примитивной рекурсии называется оператор, сопоставляющий паре (g, h) такую частичную

функцию f: Nn+1 ® N, что для всех x1,…,xn,у Î N имеют место равенства: f(x1,…,xn,0) = g(x1,…,xn);

f(x1,…,xn,y+1) = h(x1,…,xn,y, f(x1,…,xn,y)).

Поскольку область определения и значения дополняются отмеченной точкой, то равенство частичных функций означает, что для каждого значения аргумента либо левая, либо правая части равенства определены и равны между собой, либо обе его части не определены. Значение оператора примитивной рекурсии обозначается: f = R(g,h). Если g и h определены всюду, то f = R(g,h) определена всюду.

Если n = 0, то для любых числа g Î N и частичной функции h: N2 ® N частичная функция f = R(g,h) определяется с помощью равенств:

DJVU-STUDENT.NAROD.RU - информационный сайт для студентов и школьников

f(0) = g, f(y + 1) = h(y,f(y)).

Функция f называется примитивно рекурсивной, если ее можно получить из простейших функций s, o и Inm с помощью операторов суперпозиции и примитивной рекурсии (таким образом, примитивно рекурсивная функция всюду определена.)

Пример 2

Функция оn: Nn ® N, все значения которой равны нулю, примитивно рекурсивна, ибо она является композицией о ° In1 простейших функций In1: Nn ® N и о: N ® N. Рассмотрим при k ³ 1 функцию ck: Nn ® N, все значения которой равны k. Функция ck равна композиции функций оn: Nn ® N и k функций N ® N ®…® N, каждая из кото-

рых равна s, ck = sk °on. Стало быть, ck примитивно рекурсивна.

Пример 3

Функция f: N2 ® N, заданная как f(x,y) = x + y, удовлетворяет соотношениям:

f(x,y + 1) = h(x,y,f(x,y)), то f = R(g,h) = R(I11,s ° I33). Значит, f – примитивно рекурсивна.

Пример 4

Рассмотрим функцию: f(x,y) = xy. Поскольку f(x,0) = 1, и

f(x,y + 1) = x×f(x,y) = g(x,y,f(x,y)), где g(x,y,z) = x×z – примитивно рекурсивная функ-

ция (как композиция операции умножения и функции (I31, I33): N3 ® N2), то f(x,y) примитивно рекурсивна.

Пример 5

Пусть d(x) = max(0,x – 1). Имеют место равенства d(0) = 0 и d(y + 1) = y = g(y,d(y)), где g(y,z) = I21(y,z) = y. Следовательно, d(x) – примитивно рекурсивна.

Пример 6

Пусть r(x,y) = max(0,x – y). Верны соотношения r(x,0) = x и r(x,y + 1) = d(r(z,y)) = g(x,y,r(x,y)), где g(x,y,z) = d(z) – функция из примера 5. Значит, r(x,y) – примитивно рекурсивна.

Пример 6 показывает, что функция f(x,y) =ôx-yô= r(x,y) + r(y,x) примитивно рекурсивна, как суперпозиция функций x1 + x2 и пары функций (r(x,y),r(y,x)): N2 ® N2 (примитивная рекурсивность функции r(y,x) получается из разложимости r(y,x) = S3(r, I22, I21)).

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

Пусть g: Nn+1 ® N – частичная функция. Будем говорить, что частичная функция f: Nn ® N получается из неё с помощью оператора минимизации, и писать:

f(x1,…,xn) = m y [g(x1,…,xn,y) = 0],

если выполнено следующее условие: f(x1,…,xn) определено и равно y Î N тогда и только тогда, когда значение g(x1,…,xn,0),…,g(x1,…,xn,y -1) определены и не равны 0, а g(x1, …,xn,y) = 0.

Частичная функция f: Nn ® N называется частично рекурсивной, если она может быть получена из простейших функций o, s, Inm за конечное число применений операторов суперпозиции, примитивной рекурсии и минимизации.

Пример 7

Рассмотрим примитивно рекурсивную функцию: g(x,y) = x – Sg(y), где Sg(y) = 0, при y = 0, и Sg(y) = 1, для y > 0. Тогда значения:

f(x) = m y[ôx-Sg(y)ô= 0]