Теорема Клини о неподвижной точке: квайны

Теорема 2

На любом алгоритмически полном языке программирования можно написать программу, печатающую свой код.
Определение: Алгоритмически полный язык — язык, на котором можно реализовать машину Тьюринга, то есть, любой алгоритм.

Введение.

Все валидные программы на любом языке можно занумеровать. Например, в лексикографическом порядке. Можно написать
алгоритм, который по коду программы будет возвращать ее номер, а можно наоборот. И первое, и второе делается, к примеру, перебором всех строк начиная от коротких и нахождением среди них корректных исходных кодов.
А поэтому я буду отождествлять программы и их номера.

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

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

Теорема 1 (о неподвижной точке)

Для любой всюду определенной вычислимой функции f существует такое число n, что алгоритмы под номерами n и f(n) вычисляют одну и ту же функцию. То есть они будут на одинаковых входах либо давать одинаковый ответ в итоге, либо вместе зацикливаться. Такие алгоритмы называются эквивалентными.
Перефразирую. Если есть программа, получающая на вход исходный код и возвращающая исходный код, то можно подобрать такой исходник, который по смыслу не изменится после данного преобразования. (Время исполнения и так далее запросто может поменяться, но не вычисляемая функция.)

Доказательство

Для начала мы постепенно построим страшный алгоритм.
Пусть программа U будет получать на вход число n и интерпретировать алгоритм под номером n при входе n.
Последний разик сформулирую вторым способом: алгоритм U принимает на вход исходный код некоторой программы и запускает ее, передав ей на вход ее исходный код.
То есть, U(n) := n(n)
Теперь мы эту программу переделаем так, чтобы она никогда не зацикливалась (в самом деле, пока что она запросто может на некоторых входах зависать), но взамен она будет возвращать не совсем то, что сейчас.
Новая программа V будет работать так: если U(n) = m, то V(n) = k, причем k это номер алгоритма, который вычисляет ту же функцию, что и алгоритм под номером m. То есть V, получив на вход число n, вернет номер алгоритма эквивалентного алгоритму с номером n(n). А если n(n) зацикливается, то V(n) возвращает неважно что.
Как построить V:
Сначала составим себе программу W(n, x), которая интерпретирует программу n на входе x. Т.е., W(n,x) := n(x). Похоже на U.
Теперь, пусть V беред программу U, переделывает ее так, что она свой вход игнорирует, а вместо аргумента везде использует жестко заданное число n (параметр программы V), потом V узнает номер полученного алгоритма t, а затем возвращает номер программы W, в которую так же вместо первого аргумента жестко подставлено число t.

Пауза.

Получилось сложно, это самое страшное место. По шагам алгоритм V:

• на вход получаем число n
• берем код программы U и в нем все упоминания аргумента заменяем на обычное число n
• получаем номер t созданного алгоритма
• берем функцию W и вместо первого аргумента подставляем число t, тем самым редуцировав этот аргумент. Имеется в виду, что получится программа Wt(x) от одного аргумента
• получаем и возвращаем номер созданного алгоритма

Давайте запишем, что вышло. Оператор # будет взятием номера. Операция получения кода по номеру будет обозначаться никак (просто скобками).

V(n) := #W(#U(n), x) = h

Давайте возьмем алгоритм c номером h и запустим на входе x.
h(x) = V(n)(x) = W(#U(n), x) = U(n)(x) = n(n)(x)

Такая запись A(x)(y) тут везде значит, что мы в программу A подставляем число x, а затем результат превращаем снова в программу и подставляем в нее число y. Проще понимать, если считать, что программы принимают и возвращают исходные коды.

Как мы видим, алгоритм с номером V(n) делает и вправду то же самое, что и алгоритм с номером n(n). Такую функцию мы и хотели. Также, видно, что программа V ничего не интерпретирует, а только получает номера, а следовательно нигде не может зациклиться.

И последний шаг — предъявим неподвижную точку для произвольной всюду определенной вычислимой функции f.
Возьмем любой алгоритм F, вычисляющий f.
Построим программу G := V -> F, то есть выполняющую для входа программу V, а затем передающую результат на вход F.
Другими словами, для любого x выполняется G(x) = F(V(x)).
Искомое число: V(#G), то есть вывод алгоритма V, которому на вход подали номер только что построенной программы.
Проверим:
Подставим в алгоритм с номером V(#G) аргумент x.
V(#G) (x) =[по определению V]= G(#G) (x) =[по определению G]= F(V(#G)) (x)
Получили то же, что и если бы подставили x в алгоритм с номером F(V(#G)) = f(V(#G))
Это и есть определение неподвижной точки. Программы с номерами V(#G) и f(V(#G)) делают одно и то же.
F не зацикливается по условию всюду-определенности f, V и G не зацикливаются по построению.
Нужное число существует.

Квайны.

Спасибо тем, кто осилил. Очень старался сделать как можно понятнее и проще, но тема довольно сложная.

Теорема 2:
Существует программа, выводящая свой номер.
Доказательство:
Введем фукнцию S(n), которая берет код программы с номером n, и возвращает номер программы, банально печатающей этот код.
Т.е. S(n) := #(print «N»), где N — программа под номером n, «N» ее исходник как текст.
Данная функция вычислима (мы ее задали алгоритмически), всюду определена, а значит у нее есть неподвижная точка.
То есть, такое число, что программы N и (print «N») делают одно и то же. Вывод программы N совпадает с выводом программы (print «N»).

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

Заключение.

Такие дела.
Надеюсь, что было интересно или полезно. Если сообщество интересует подобное, то могу написать про теорему Райса, алгоритмическую полноту арифметики Пеано (да-да, арифметика посильнее машины Тьюринга. Хотя оно и понятно), и другую такую ерунду.
Если есть вопросы и что-то непонятно, пишите — отвечу на всё, на что смогу.

Материалы

Память.
Вот вроде бы неплохая лекция, но я посмотрел только самое начало, о понятности далее не могу судить. Но кажется, что мужик доступно объясняет. Только вот там нужно уже знать основы теории, включая разрешимые\перечислимые множества и нумерации. Ну и плюс видео жутко долгое.
Ничего по теме статьи, но не требующее вводного изучения, я не могу предложить.
А если хочется разобраться, то читайте книжки Верещагина-Шеня — очень качественная литература. Но понадобится проходить теорию множеств, потом математическую логику, а потом только теорию алгоритмов.