машина Зенона

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

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

Определение

Машина Зенона — это машина Тьюринга, которая может делать бесконечное количество шагов, а затем продолжать делать еще больше шагов. Это можно рассматривать как сверхзадачу , в которой ${\frac {1}{2^{n}}}$ единицы времени тратятся на выполнение $n$-й шаг; таким образом, первый шаг занимает 0,5 единицы времени, второй — 0,25, третий — 0,125 и так далее, так что за одну единицу времени счетное бесконечное будет выполнено число шагов.

Бесконечные

Анимация машины Тьюринга с бесконечным временем, основанная на мысленном эксперименте с лампой Томсона . Ячейка чередуется между $0$ и $1$ за шаги до $\omega$. Клетка становится $1$ в $\omega$ так как последовательность не сходится.

Более формальная модель машины Зенона — это машина Тьюринга с бесконечным временем . Впервые определен в неопубликованной работе Джеффри Киддера и расширен Джоэлом Хэмкинсом и Энди Льюисом в книге « Бесконечные машины Тьюринга» . машина Тьюринга с бесконечным временем является расширением классической модели машины Тьюринга и включает трансфинитное время; это время за пределами всего конечного времени. Классическая машина Тьюринга имеет статус на шаге $0$ (в стартовом состоянии, при пустой ленте, читаем головку в ячейке 0) и процедуру перехода из одного статуса в последующий статус. Таким образом, состояние машины Тьюринга определяется для всех шагов, соответствующих натуральному числу. ITTM ни поддерживает эти свойства, но также определяет состояние машины при предельных ординалах , то есть порядковых числах, которые не являются $0$ ни преемник какого-либо ординала. Статус машины Тьюринга состоит из 3 частей:

1. Государство
2. Расположение головки чтения-записи
3. Содержание ленты

Точно так же, как классическая машина Тьюринга имеет помеченное начальное состояние, которое является состоянием в начале программы, ITTM имеет помеченное предельное состояние, которое является состоянием машины при любом предельном порядковом номере. Это так, даже если у машины нет другого способа получить доступ к этому состоянию, например, ни один узел не переходит в него. Местоположение головки чтения-записи устанавливается на ноль на любом предельном шаге. Наконец, состояние ленты определяется предельной супремумом предыдущих состояний ленты. Для какой-то машины $T$, клетка $k$ и предельный порядковый номер $\lambda$ затем

$T(\lambda )_{k}=\limsup _{n\rightarrow \lambda }T(n)_{k}$

Это $k$ячейка во времени $\lambda$ - это предельная верхняя граница той же ячейки, когда машина приближается $\lambda$. Это можно рассматривать как предел, если он сходится или $1$ в противном случае.

Вычислимость

Машины Зенона были предложены в качестве модели вычислений, более мощной, чем классические машины Тьюринга, на основе их способности решать проблему остановки классических машин Тьюринга. Кристиан Калуде и Людвиг Штайгер представляют следующий алгоритм псевдокода как решение проблемы остановки при запуске на машине Zeno.

begin program
    write 0 on the first position of the output tape;
    begin loop
        simulate 1 successive step of the given Turing machine on the given input;
        if the Turing machine has halted then
            write 1 on the first position of the output tape and break out of loop;
    end loop
end program

Проверив первую позицию выходной ленты после $1$ По прошествии единицы времени мы можем определить, остановится ли данная машина Тьюринга. Напротив, Орон Шагрир утверждает, что состояние машины Зенона определяется только на интервале $[0,1)$, а так невозможно вовремя осмотреть ленту $1$. Более того, поскольку классические машины Тьюринга не имеют никакой информации о времени, добавление информации о времени, независимо от того, ускоряется оно или нет, само по себе не добавляет никакой вычислительной мощности.

Однако машины Тьюринга с бесконечным временем способны реализовать данный алгоритм, останавливаясь во времени. $\omega$ с правильным решением, поскольку они определяют свое состояние для трансфинитных шагов. Все $\Pi _{1}^{1}$ множества разрешимы с помощью машин Тьюринга с бесконечным временем, и $\Delta _{2}^{1}$ множества полуразрешимы .

Машины Зенона не могут решить собственную проблему остановки.

См. также

• Вычисление в пределе
• Последовательность Спекера
• Парадокс Росса – Литтлвуда