 | В этой статье не процитировать какие - либо источники . ( январь 2020 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон ) |
В математике и информатике , машины Зенона (сокращенно ZM , а также под названием ускоряется машин Тьюринга , ATM ) представляют собой гипотетические вычислительные модели , связанные с машинами Тьюринга , что позволяет бесконечное счетное число алгоритмических шагов , которые будет выполняться за конечное время. Эти машины исключены в большинстве моделей вычислений.
Более формально машина Зенона - это машина Тьюринга, которой требуется 2 - n единиц времени для выполнения своего n -го шага; Таким образом, первый шаг занимает 0,5 единицы времени, второй берет 0,25, третий 0.125 и так далее, так что после того, как одну единицу времени, A счетное (т.е. ℵ 0 ) будет было выполнено число шагов.
Идея машин Zeno впервые была обсуждена Германом Вейлем в 1927 году; название относится к парадоксам Зенона , приписываемым древнегреческому философу Зенону Элейскому . Машины Zeno играют решающую роль в некоторых теориях. Например, теория точки Омега, разработанная физиком Фрэнком Дж. Типлером , может быть верной только в том случае, если возможны машины Зенона.
Вычислимость [ править ]
Машины Зенона позволили бы вычислить некоторые функции, которые не вычислимы по Тьюрингу. Например, проблема остановки машин Тьюринга может быть решена машиной Зенона (с использованием следующего алгоритма псевдокода ):
начать программу напишите 0 в первой позиции выходной ленты; начать цикл смоделировать 1 последовательный шаг данной машины Тьюринга на заданном входе; если машина Тьюринга остановилась, то записать 1 в первую позицию выходной ленты и выйти из цикла; конец цикла конец программы
Вычисления такого типа, которые выходят за пределы предела Тьюринга, называются гипервычислениями , в данном случае гипервычислениями через сверхзадачу - см. Там дальнейшее обсуждение и литературу.
См. Также [ править ]
