Свойства вычислимых функций

1. Суперпозиция вычислимых функций вычислима.

2. Любая вычислимая функция вычислима на машине Тьюринга с правой полулентой.

3. Если функции вычислимы и P (x) – предикат, то разветвление также вычислимо.

Выше мы каждому алгоритму поставили в соответствие функцию. Является ли верным обратное утверждение: можно ли для произвольной функции построить алгоритм её вычисляющий? Ответ на этот вопрос отрицательный, т.е. произвольная функция не является вычислимой. Выделим класс функций, для которых вычисляющий их алгоритм существует, таким образом, мы дадим другое определение алгоритма в терминах функций.

Дата добавления: 2014-01-20