Interested Article - Машина Зенона

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

Более строго, машиной Зенона называется такая машина Тьюринга, которой требуется 2 ^{−

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

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

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

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

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

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

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