Хабр оценивает время прочтения в 1 минуту. Но это задачка на ℵ₋₁ минут.
Что за зверь?
Сколько нужно бит, чтобы представить одно число из континуума ℵ₁ чисел?
Ответ: ℵ₀ бит.
Сколько нужно бит, чтобы представить одно число из счётного множества ℵ₀ чисел?
Ответ: ℵ₋₁ бит.
Произвольное число из континуума (почти все они трансцендентные) требует бесконечно бит для представления, а произвольное число из счётного множества (натуральные, целые, рациональные) требует непременно конечно бит.
ℵ₋₁ это достаточно.
Машина Тьюринга (МТ)
Это компьютер с ℵ₀ бит памяти, который не ветшает и инфу не теряет.
Идеальный компьютер. Казалось бы, чего ещё надо? Но говорят, что есть задачи, которые не решить даже на нём. Проблема остановки и всё такое...
Вневременная МТ
Если МТ дать поработать ℵ₀ тактов, получится вневременная МТ мощностью ℵ₀. Чтобы адресовать конкретный бит в её пространстве-времени, нужно ℵ₋₁ бит. Если на ней запустить программу вычисления числа π, то любой его знак (в двоичной системе счисления) можно получить по легко вычисляемому адресу длиной ℵ₋₁ бит.
А теперь внимание, вопросы на засыпку.
Какую программу нужно загрузить во вневременную МТ, чтобы адрес длиной ℵ₋₁ бит мог указывать на:
Любую конкретную конечную программу?
Результат выполнения любого конкретного конечного алгоритма (например, число π со всеми ℵ₀ двоичными знаками)?
Программу, решающую проблему остановки любой конечной программы? Какая будет её длина?
И какие ещё вопросы возникают в свете первого вопроса?