Изменения
Нет описания правки
Такие гипотетические устройства Тьюрингом были рассмотрены еще в 1939 году.
Это машины с [[Сложностные классы. Вычисления с оракулом | оракулом]]. Под оракулом понимается некая сущность,
способная «вычислять» [[Вычислимые функции | невычислимые функции]] или решать алгоритмически [[Примеры неразрешимых задач: проблема соответствий Поста | неразрешимые проблемы]].
Тьюринг показал, что для таких машин проблемы, сформулированные относительно них самих (например, проблема останова машины с оракулом)
ими же являются неразрешимыми. Это напоминает древний парадокс: может ли всемогущий бог создать камень,
}}
Некоторые функции, которые не могут быть вычислены на машине Тьюринга, могут быть вычислены с использованием машины Зенона. Например, на ней может быть решена проблема остановки (что иллюстрируется следующим псевдокодом):
'''zeno machinezenoMachine(TuringMachine, input )'''
записать 0 в первую ячейку на ленте в TuringMachine;
'''начало цикла'''
