dmitgu, давайте договоримся, что вы всё-таки не будете писать тексты длиннее трех абзацев. Пока что я не помню ни одного случая, чтобы вы написали столько и не возникло вопросов - а текст, идущий после места, к которому есть вопрос, всё равно бесполезен.
Мне не пришло уведомление о продолжении Вашей записи или я его прозевал. И я думал про 3 абзаца

Как упростить. Ответ подготовил именно про это. Но сначала отвечу на то, что прозевал:
язык

строится как

, где

состоит из слов вида

, где

- строка из единиц,

- теорема арифметики, для которой существует доказательство не длиннее

(

- некоторая мировая константа)

состоит из слов вида

, где

,

- некоторый алгоритм. От

что-то здесь зависит, или любой алгоритм сойдет?

состоит из слов вида

(что это такое - я пока не понимаю, если с

и

согласны - напишите, пожалуйста, минимальное количество информации про них, необходимое для определения - например, хотя бы что это такое - алгоритмы? утверждения? что-то еще?)
В общем верно, хотя кроме

-прописная есть ещё и

-заглавная – там сразу число и оно короткое (в десятичном виде, например). Но, возможно, для

и

она не особо нужна. А вот для

- принципиально необходима.
От

ничего не зависит для

и

, и любой алгоритм сойдет, но вот для

- зависит принципиально:
Выражение

строится так, чтобы его принадлежность к числу теорем теории Пеано алгоритм

заведомо не смог подтвердить не то что за допустимое количество шагов, полиномиальное от предельного допустимого размера доказательства

, а вообще ни за какое.
При этом данное утверждение всё-таки будет принадлежать языку

если алгоритм

выдаст результат

(«не подтверждаю принадлежность данных слов языку

») достаточно быстро. То есть, утверждение

должно «поступить наоборот» относительно результата

при корректных

,

.
Подобные утверждения хорошо известны в логике из доказательств о неразрешимостях. И из доказательства теоремы о неопределимости - в частности. Нам надо воспользоваться «возражающим алгоритмом»

со следующим свойством:

Это равенство описывает, как работает алгоритм

, лежащий в основе

и «поступающий наоборот». Алгоритм
If(Проверка логического выражения на истинность, Результат при истине, Результат в ином случае)
широко известен в программировании. Обозначение

выше - это проверка, равны ли результаты от

и

между собой. И данное сравнение возвращает «истина», если равны, а если не равны, то возвращает «ложь».
В силу того, что равенство

и есть утверждение

- приходим к тому, что нам и требовалось, а именно, слово:

Не принадлежит языку

. И это отражает тот факт, что именно

не способен подтвердить принадлежность слова

языку

- этот факт «быстрый» и не требует рассмотрения никаких доказательств.
Теперь я отвечу про «три абзаца» и формализую принципиальный момент, который, возможно, витает в воздухе и создаёт непонимание что это за язык

.
Гм… Дело не в количестве абзацев, наверно - часто большая книга читается проще маленькой о том же, потому что в большой изложено более последовательно и понятно. Тем более в математике ужать некоторые мысли в несколько абзацев невозможно.
В моём последнем большом тексте тут я написал громоздкие формулы с большим количеством новых обозначений без аккуратной подготовки. Такие формулы «с потолка» понятны, когда ты сам их придумываешь, но не когда читаешь чужой текст.
Меня «унесло» в собственные мысли, когда по ходу формализации (которая была затеяна благодаря обсуждению тут и Вам в частности) я решил, что можно доказать не только первопричину вопроса о

, но и само это неравенство. Не то, чтобы это сильно принципиальная возможность, но это может помочь донести и сильно принципиальное

. Поэтому много чего пересмотрел, не очень чётко связал новое со старым и не слишком внятно изложил.
К тому же, есть принципиальное отличие языка

от языков класса

из учебников. Это отличие у меня не получалось сформулировать, а тем более трудно спросить про него «со стороны», раз предмет вопроса не формализован. Поэтому это принципиальное отличие я сейчас сформулирую. Я и остальное переписал до конца, но не буду добавлять ещё три страницы, так как в ходе обсуждения порядок и терминология могут измениться.
Итак:
Ставится вопрос о решении (сведении) языка

класса

к классу

. И при этом должен произойти переход от алгоритма проверки

к алгоритму-решению

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

, что для алгоритма-решения

предполагается переданным для рассмотрения о принадлежности языку только одно слово - слово

. Но мы рассмотрим язык

, который содержит и слова вида:

, где

либо совпадает с

, либо содержит только часть информации из

.
И в этом случае алгоритму решению

переданы для рассмотрения 2 слова вида
1.

2.

При этом мы исходим из того, что алгоритм-решение

располагает информацией о своём собственном программном коде

в той же мере, что и о значении переданного ему аргумента

(аксиома рефлексии).
Но поскольку алгоритм-решение может вернуть только один результат, то язык

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

всегда был одним и тем же.
Назовём это свойство «свойством согласованности языка

».
Вот такое у языка

принципиальное отличие от языков класса

из учебников. Обсуждать дальше имеет смысл, если язык

можно признать языком класса

, не смотря на сформулированное только что его отличие от «привычных» языков класса

.