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