Машина Зенона

В математике и информатике Машина Зенона (иногда сокращаемая до ЗМ, также называемая ускоренной машиной Тьюринга) — это гипотетическая компьютерная модель, связанная с машиной Тьюринга, которая способна совершить счётное количество алгоритмических шагов за конечное время. В большинстве моделей вычислений такие машины не рассматриваются.

Более строго, машиной Зенона называется такая машина Тьюринга, которой требуется 2⁻ⁿ единиц времени для совершения n-го шага. Таким образом, первый шаг требует 0,5 единицы времени, второй — 0,25, третий — 0,125 и так далее, так что за единицу времени совершается бесконечное количество шагов.

Идея машины Зенона впервые обсуждалась

Германом Вейлем в 1927 году. Своё название она получила в честь апорий древнегреческого философа Зенона Элейского. Такие машины играют ключевую роль в некоторых теориях. К примеру, теория точки Омега, разработанная Франком Типплером

, верна, только если машина Зенона может существовать.

Машина Зенона и вычислимость

Некоторые функции, которые не могут быть вычислены на машине Тьюринга, могут быть вычислены с использованием машины Зенона. Например, на ней может быть решена проблема остановки (что иллюстрируется следующим псевдокодом):

начало программы 
  записать 0 в первую ячейку на ленте;
  начало цикла
    смоделировать очередной шаг работы данной машины Тьюринга на данном входе;
    если машина Тьюринга остановилась, то записать 1 в первую ячейку на ленте и прервать цикл;
  конец цикла
конец программы

Такие вычисления, выходящие за рамки возможности машины Тьюринга, называются

гипервычислениями

.

Стоит заметить, что проблема остановки для самой машины Зенона не может быть решена на машине Зенона (Potgieter, 2006).

См. также

Парадокс Зенона
Гипервычисления
Лампа Топсона
Проблема мячей и вазы
Точка Омега

Ссылки

Petrus H. Potgieter, Zeno machines and hypercomputation, 2006.