Ключ к вычислимости ℵ₋₁

Что за зверь?

Сколько нужно бит, чтобы представить одно число из континуума ℵ₁ чисел?

Ответ: ℵ₀ бит.

Сколько нужно бит, чтобы представить одно число из счётного множества ℵ₀ чисел?

Ответ: ℵ₋₁ бит.

Произвольное число из континуума (почти все они трансцендентные) требует бесконечно бит для представления, а произвольное число из счётного множества (натуральные, целые, рациональные) требует непременно конечно бит.

Коротко говоря, ℵ₋₁ это достаточно.

Машина Тьюринга (МТ)

Это компьютер с ℵ₀ бит памяти, который не ветшает и инфу не теряет.

Идеальный компьютер. Казалось бы, чего ещё надо? Но говорят, что есть задачи, которые не решить даже на нём. Проблема остановки и всё такое…

Вневременная МТ

Если МТ дать поработать ℵ₀ тактов, получится вневременная МТ мощностью ℵ₀. Чтобы адресовать конкретный бит в её пространстве-времени, нужно ℵ₋₁ бит. Если на ней запустить программу вычисления числа π, то любой его знак (в двоичной системе счисления) можно получить по легко вычисляемому адресу длиной ℵ₋₁ бит.

А теперь внимание, вопросы на засыпку.

Какую программу нужно загрузить во вневременную МТ, чтобы адрес длиной ℵ₋₁ бит мог указывать на:

1. Любую конкретную конечную программу?

2. Результат выполнения любого конкретного конечного алгоритма (например, число π со всеми ℵ₀ двоичными знаками)?

3. Программу, решающую проблему остановки любой конечной программы? Какая будет её длина?

И какие ещё вопросы возникают в свете первого вопроса?