Я читал о стремлении Чайтина к совершенному языку.
Интересные мелочи:
- Теорема Гёделя о неполноте сродни рассуждениям о высказывании, объявляющем себя недоказуемым (примечание: неверным). например «Это предложение недоказуемо».
Чтобы рассуждать об идее, нам нужны две вещи. Нам нужен синтаксис/язык для кодирования этих утверждений в логические предложения, а также нам нужна система правил для получения математических истин из этих предложений. Итак, здесь английская система рассуждений дает довольно стандартный способ кодирования предложений на своем языке. Однако не так просто получить правдивость/доказательство предложения. Святой Грааль — это аксиоматическая система, которая кодирует все возможные утверждения и выводит значения истинности для всех из них. Такова полная аксиоматическая система, совершенный математический язык.
Гедель показывает, что не существует пары систем кодирования и вывода, которая была бы одновременно непротиворечивой (не противоречащей самой себе) и полной (может кодировать + доказывать каждое суждение). идея). Одно направление этого аргумента начинается с утверждения: «Это предложение недоказуемо».
Теперь у нас есть два пути для рассмотрения: оно либо доказуемо, либо нет. Если это доказуемо, то оно противоречит само себе, и мы доказываем что-то ложное. Если мы позволим нашему математическому языку доказывать ложные вещи, то, по сути, мы получим мусор. Так что давайте исключим этот случай. Наш единственный оставшийся вариант — рассмотреть возможность того, что это предложение недоказуемо. Однако если бы это было правдой, то в нашем математическом языке есть предложение, которое мы не можем доказать. Это неполное! - С точки зрения алгоритмической информации самая маленькая программа с саморазграничением для вычисления числа N требует около H(N) + H(H(N)) + … бит. Думайте об этом как о русской кукле, чтобы разграничить N, вам понадобится программа для его вычисления. Колмогоров ограничивает это до log(N). Однако вам понадобится другая программа, чтобы разграничить конец программы O(log(N)) для вычисления N и так далее. Это означает, что вам потребуется n log(n) битов для вычисления программы размера n. Тем не менее, вы получаете из этого некоторые приятные свойства: ваши программы являются саморазграничивающими. То есть универсальная машина Тьюринга завершит работу после того, как поймет, что программа ограничила себя, и отклонит программу, если после реализации ограничителя появятся дополнительные биты. С этой точки зрения набор допустимых программ образует набор без префиксов, где допустимая программа не может быть префиксом другой допустимой программы.
