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