Информатика -продвинутый курс



     витамин е |     

РЕКУРСИВНЫЕ ФУНКЦИИ - часть 2


Частичная функция из (N)" в (N)" полувычислима, если можно указать такой алгоритм (программу), который для входного набора х с (N)" дает на выходе х е D(f),

или алгоритм работает неопределенно долго, если х е D(f). Очевидно, что вычислимые функции полувычислимы, а всюду определенные полувычислимые функции вычислимы.

Частичная функция f называется невычислимой, если она не является ни вычислимой, ни полувычислимой.

Из вновь введенных понятий основным является полувычислимость, так как вычислимость сводится к нему. Существуют как невычислимые функции, так и функции, являющиеся полувычислимыми, но не вычислимые. Пример такой функции:

Можно показать, что существует такой многочлен с целыми коэффициентами P(t, x1,...,xn), что g(t) - невычислима. Однако, легко видеть, что g(t) - полувычислима.

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

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

suc: N ® N; suc(x) = x+1 - определение следующего за х

числа;

l(n): (N)n ®

N; l(n) (x1,..., хn) = 1, п ³ 0 - определение «размерности» области определения функции;

рr

: (N)n®

N; pr

(x1,..., хn) = хi, х ³

1 - «проекция» области определения на одну из переменных.

Элементарные операции над частичными функциями:

а) композиция

(или подстановка) ставит в соответствие паре функций f из (N)m в (N)n и g из (N)n

в (N)p функцию h = gof из (N)m в (N)p , которая определяется как

б) соединение

ставит в соответствие частичным функциям fi из (N)ni, i = 1, ..., k функцию (fi, ..., fk) из (N)m в (N)n1




Содержание  Назад  Вперед