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

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

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

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

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

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

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

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

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

См. также

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

Ссылки

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