Информатика -продвинутый курс
если можно указать такой алгоритм
Частичная функция из (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; pr
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
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий