Задачи о нахождении алгоритмов для тех или иных вычислений.
Задачи о нахождении алгоритмов для тех или иных вычислений, обычно называют алгоритмическими проблемами.
Если алгоритма для вычисления той или иной функции не существует, то говорят, что соответствующая алгоритмическая проблема
неразрешима.
1)Неразрешимость проблемы распознавания в математической логике.
Теорема Черга: проблема распознавания выводимости алгоритмически неразрешима.
Т. е. для любых двух формул А и В в логическом исчислении нельзя узнать, существует ли дедуктивная цепочка, ведущая от А к В.
2)Неразрешимость проблемы распознавания самоприменимости.
МТ самоприменима, если она применима к своему коду. Иначе она несамоприменима.
Теорема: Не существует алгоритма, который по любой МТ определял, является ли она самоприменимой.
3)Проблема эквивалентности слов для ассоциативных исчислений неразрешима. (Марков – 1946, Пост - 1947).
Ассоциативным исчислением называется совокупность всех слов в некотором алфавите вместе с какой-нибудь конечной системой
допустимых подстановок.
4)Эквивалентность машины Тьюринга неразрешима.
Гедель и Чёрг описали класс всех рекурсивных функций, как класс всех числовых функций, определяемых в некоторой формальной
системе, и он оказался равномощен всем вычислимым по Тьюрингу функциям.
Выберем следующие простейшие функции:
• S(x) = x+1 – функция сдвига;
• O(x) = 0 – функция аннулирования;
• Inm(x1, x2, ...xn) = xm; 1 <*> m <*> n – функция проектирования или выделения аргумента.
И два оператора – т. е. операции над функциями: подстановка (суперпозиция) и рекурсия.
Оператор подстановки:
f1(x1, x2, ..., xn), f2(x1, ..., xn), ...fm(x1,..., xn) и<*>(x1, ..., xm).
<*>(x1, ..., xn) =<*>(f1(x1, ..., xn), ...fm(x1, ..., xn)).
И тогда говорят, что <*> получена из<*>и f1, ...fn – суперпозицией.
Замечание: если ?, f1, ..., fn – всюду определены, то и <*> будет всюду определённой функцией.
Замечание: не обязательна зависимость от всех аргументов, можно использовать фиктивные аргументы и функции Inm.
<*>(x,y,z) =<*>(f1(x), f2(x,y,z), z); F1(x,y,z) = f1(x); F2(x,y,z) = f2(x,y,z); F3(x,y,z) = I33(x,y,z).
И тогда <*>(x,y,z) =<*>(F1(x,y,z), F2(x,y,z), F3(x,y,z)).
Оператор рекурсии применяется либо к натуральному числу и функции h вместимости 2, либо к функциям g и h размерности n-1 и
n+1 и задаётся следующими рекурсивными равенствами:
(R1) {f(0) = c; f(x+1) = h(x,f(x))}
(R2) f(x1, ..., xn-1, 0) = g(x1, ..., xn-1); f(x1, ..., xn-1, xn+1) = h(x1, ..., xn-1, xn, f(x1, ..., xn-1, xn)).
Итак, в случае (R2) f – n-местная; h – n+1-местная; g – n-1-местная.
Говорят, что f получается из h и g по схеме примитивной рекурсии.
Замечание 1: очевидно, что, если h и g всюду определены, то и f всюду определена.
Замечание 2: вычисление ведётся по следующей схеме:
Для вычисления f(a1, ..., an) f(a1, a2, ..., an-1, 0) = g(a1, a2, ..., an-1) = b0;
f(a1, a2, ..., an-1, 1) = h(a1, a2, ..., an-1, 0, b0) = b1;
f(a1, a2, ..., an-1, 2) = h(a1, a2, ..., an-1, 1, b1) = b2.
Примитивно рекурсивной функцией называется функция, которая принадлежит к числу простейших: O, S, Inm, либо может быть
получена из них с помощью операторов подстановки и рекурсии.