2011.11.28 Шень А. Теоремы Гёделя о неполноте и слова высокой колмогоровской сложности

Теорема Гёделя в форме Чейтина показывает, что утверждения вида «Колмогоровская сложность x больше C», где x — конкретное слово, а C — конкретное число, недоказуемы в арифметике Пеано для всех...