И кстати все такие спичи про Геделя мне сильно не нравятся. Канторовский диагональный аргумент, геделевская теорема о неполноте, проблема остановки - это просто частные случаи теоремы Ловера о неподвижной точке. https://ncatlab.org/nlab/show/Lawvere's+fixed+point+theorem читайте, просвещайтесь и не примазывайте иррациональный мистицизм к точной науке.
Популярное изложение идеи именно этой теоремы, как я понял, есть у Грега Игана в "3-адике":
> – Думаю, я нашел способ обобщить один из любимых приемов Курта! – восторженно заявил Карнап, когда официантка принесла Сагреде кофе и кусочек торта. – Предположим, что у нас есть формальный язык с набором аксиом и правил вывода, которые описывают основные свойства натуральных чисел. Используя метод Курта, любому высказыванию в таком языке можно сопоставить некое число – «число Гёделя», если хотите. Моя цель – доказать, что у любой формулы F с одной свободной переменной есть нечто вроде неподвижной точки, а именно высказывание G, гёделевское число которого при подстановке в F дает в результате высказывание, эквивалентное G!
> Он взглянул на Сагреду, как если бы она была последней инстанцией, призванной решить, заслуживает ли эта тема внимания их группы. – Звучит интригующе, – произнесла она в теле кукловода, после чего губы марионетки синхронно воспроизвели ее слова в переводе на немецкий.
> Большей моральной поддержки Карнапу и не требовалось. – Представьте такую функцию Q, которая на вход получает гёделево число произвольной формулы A с единственной свободной переменной, а в качестве результата выдает гёделево число формулы, которая получается из A заменой ее свободной переменной на гёделево число самой A. Если выразительная мощь системы достаточно велика, чтобы в ней можно было представить подобную функцию, то обязательно найдется формула B с двумя свободными переменными, которая будет доказуемо эквивалентна утверждению о том, что ее вторая переменная совпадает со значением функции Q в применении к первой. Вы следите за моей мыслью?
> Сагреде не хотелось, чтобы он смотрел в ее сторону, пока она отчаянно пыталась совладать с этой до странности витиеватой формулировкой. Зачем вводить новую формулу B, когда можно ограничиться Q? А… все дело в том, что даже если сама функция Q определена корректно, ограничения формального языка могут помешать нам воспользоваться записью «Q(x)» в качестве краткого обозначения величины, которую Q принимает в точке x. В исходном допущении имелось лишь одно ограничение насчет выразительной мощи языка: ее должно хватать для формулировки утверждения о том, что некое число-кандидат y прошло серию испытанию, подтверждающих его равенство Q(x). B(x, y) не сможет выдать ответ, т. е. Q(x), напрямую, но может подтвердить или опровергнуть правильность конкретной догадки, y.
> – Следим, не сомневайтесь, – нетерпеливо заметил Тарский.
> – Помните формулу F, ради которой все и затевалось? С ее помощью мы можем ввести новую формулу C, которая также содержит одну свободную переменную и, по определению, будет утверждать, что для любого y истинность B(x, y) влечет за собой истинность F(y).
> Менгер достал из жилетного кармана карандаш и стал делать на салфетке аккуратные записи, разделяя символы крупными промежутками. – Допустим, так на языке логиков выглядит утверждение, которое недотепы вроде меня записали бы в виде «C(x) равносильно F(Q(x))»…, даже если язык не позволит мне выразить Q(x) в явном виде, – подумала Сагреда.
> – Попробуем теперь подставить в формулу C ее собственное гёделевское число и посмотрим, что нам это даст. – Карнап своим видом напомнил фокусника, который вот-вот должен был извлечь из одного цилиндра другой – куда большего размера. – Учитывая доказательную силу, которую наша система имеет в отношении B и Q, она также способна доказать и тот факт, что при замене свободной переменной на гёделево число, соответствующее C, формула C становится эквивалентной F, где вместо свободной переменной подставлен результат применения Q к гёделеву числу C – который, в свою очередь, равен гёделеву числу формулы, получаемой из C подстановкой ее собственного гёделев