Раздел «Образование».SelfApplyAlgorithms:

Про самоприменимые алгоритмы

Рассмотрим множество всех алгоритмов, которые что-то получают на вход, и что-то возвращают на выход. Можно считать, что алгоритмы реализуют натуральнозначные функци натуральнозначного аргумента, а точнее, отображения N -> N*, где N* = Union{N, undef}, undef — это когда алгоритм зацикливается, то есть не заканчивает свою работу. Эта абстракция допустима, так как слова в любом конечном алфавите можно однозначно вычислимо закодировать натуральным числам.

Одним из основных понятий вычислимых функций является понятие универсальной функции, котрую в определеном смысле можно назвать интерпретатором алгоритмов.

U(a,x) — натуральнозначная (точнее N*) вычислимая функция двух натуральных аргументов. Первый аргумент a — программа, а точнее описание алгоритма на некотором языке, второй аргумент x — входные данные для этого алгоритма. U(a,x) по определению есть результат выполнения алгоритма a на входных данных x.

Вычислимая функция U(a,x) двух натуральных аргументов как бы перечисляет вычислимые функции с одним натуральным аргументом. (Предполагается, что натуральными числами a шифруются множество всех алгоритмов. Это отдельный разговор, как написать алгоритм, который по номеру выдает машину Тьюринга и наоборот по машине Тьюринга выдает её номер.)

Предположим, что есть такая функция U(a,x), которая для a=1,2,.... перечисляет ВСЕ вычислимые натуральнозначные функции натурального аргумента.

Посмотрите, что можно тогда сделать: рассмотрим функцию h(x) = U(x,x)+1. Это вычислимая функция, так как она использует результат вычислимой функции U и после прибвляет к нему единицу. Но в то же время она не может быть вычислимой, поскольку она отличается на 1 от вычислимой функции с номером A ( функции U(A,x) ) при x=A. Пусть h(x) имеет номер A, то есть U(A,x)=h(x). Но по определению h(x)=U(x,x)+1. Тогда при x=A имеем U(A,A)=h(A) и h(A)=U(A,A)+1.

Значит ли это, что мы получили противоречие, наше предположение неверно, b универсальной вычислимой функции U(a,x) не существует?

Нет не значит. И противоречия мы не получили. Мы просто забыли, что алгоритмы могут зацикливаться и результатом вычисления может быть не натуральное число, а undef. И тогда может выполнятся как равенство undef = undef, так и undef = undef+1.

Но из этих рассуждений следуют интересные выводы.

Следовательно, нельзя написать программу, котрая по данной на входе программе (по описанию машины Тьюринга) определяет остановится она на входных данных или нет.

То есть получили интересный результат — Определение того, остановится или нет программа, является не вычислимой функцией.

Итак, причем же здесь "самоприменимые алгоритмы"

Когда-то кто-то не подумав выражению U(x,x) дал собственное имя "самоприменимый алгоритм". Потом другие люди, тоже не подумав, стали зачем-то использовать этот термин к месту и не к месту.

Рекомендую не употреблять этот термин, и не замутнять некоторые и без того не очень ясные умы.

Если же уважаемые лектора непременно хотят рассказывать о машине Тьюринга и вычислимых функциях певрвому курсу, то нельзя ли сделать так, чтобы студенты знали ответы на вопросы из первых трех параграфов теории вычилимых функции:

PS: Рассказывать о машине Тьюринга имеет смысл только в контексте вычислимых функций. По-моему, довольно неправильно рассказывать о машине Тьринга в контексте "Алгоритмы и алгоритмические языки".

PSS: То что не существует алгоритма который решает задачу останова — не самый интересный результат. Заметим, что когда по алгоритму мы можем воссоздать математическое утверждение (состоящее из квантороров, переменных, арифметические операции, отношений "следовательно", "равносильно" и т.д.), которое верно тогда, и только тогда когда алгоритм никогда не осттановится.

Если существовал алгоритм, который для любого математического утверждения находил что оно истинно или наоборот, доказывал что оно ложно, то задача останова была бы разрешима.

Значит алгоритма определяющий истинность математических утверждений не существует. Это и есть теорема Геделя: есть утверждения, про которые нельзя сказать истины они или ложны.

Диагональный метод Кантра доказательства несчетности точек отрезка [0,1] и доказательства отсутствия универсальной функции на множестве всегда останавливающихся алгоритмов очень похожи. Таким образом, следовало бы учить студентов (не первого курса) не словосочетанию "самоприменимый алгоритм", а словосочетанию "диагональный метод" и и рассказывать про основные теоремы вычислимых функций — отсутствие алгоритма, решающего задачу останова, и теорема Геделя.

Но это вещи очень абстрактные, и не факт что они нужны студентам Физтеха.

Гораздо полезнее было бы занятся внутренностью множества вычислимых функций, рассмотреть классы сложности и конкретные алгоритмы для решения фундаментальных классических задач.

-- ArtemVoroztsov - 30 Mar 2004