Лекция 9. Тезис Черча: Все вычислимые функции вычислимы по Тьюрингу

Тезис Черча

Тезис Черча: Все вычислимые функции вычислимы по Тьюрингу.

Следовательно, существуют невычислимые функции.

Тезис Черча: Все вычислимые функции вычислимы по Тьюрингу.

На прошлой лекции показали, что существуют невычислимые функции.

Функция наз. частичной, если она определена на некотором множестве .

Всюду определенная функция тоже является частичной .

Частичная функция называется вычислимой, если существует некоторая машина (алгоритм, устройство), которая для каждого за конечное число шагов получает результат , а для результата не получает (либо никогда не остановится, либо остановится не штатно, то есть «сломается»).

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

Функция называется рекурсивной, если она всюду определена и частично рекурсивна.

Замечание: Обычно в теории алгоритмов рекурсивные функции определяются иначе:

Обозначим ЧРФ - множество частично-рекурсивных функций, ВФ - множество вычислимых функций. Очевидно .

Тезис Черча: Функция вычислима тогда и только тогда, когда она частично рекурсивна, то есть .

Дата добавления: 2013-12-13