Изменения
Нет описания правки
Такие гипотетические устройства Тьюрингом были рассмотрены еще в 1939 году.
Это машины с [http://neerc[Сложностные классы.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%BD%D1%8B%D0%B5_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D1%8B._%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F_%D1%81_%D0%BE%D1%80%D0%B0%D0%BA%D1%83%D0%BB%D0%BE%D0%BC Вычисления с оракулом | оракулом]]. Под оракулом понимается некая сущность,
способная «вычислять» невычислимые функции или решать алгоритмически неразрешимые проблемы.
Тьюринг показал, что для таких машин проблемы, сформулированные относительно них самих (например, проблема останова машины с оракулом)
{{Определение
|definition =
'''Машина Зенона''' (англ. ''zeno machine'') — это гипотетическая компьютерная модель, связанная с машиной Тьюринга, которая способна совершить счётное количество алгоритмических шагов за конечное время. В большинстве моделей вычислений такие машины не рассматриваются.
}}
Некоторые функции, которые не могут быть вычислены на машине Тьюринга, могут быть вычислены с использованием машины Зенона. Например, на ней может быть решена проблема остановки (что иллюстрируется следующим псевдокодом):
* попытка отказаться от линейности времени: оно замедляется, ускоряется, замыкается. Как известно из физики, такие процессы действительно существуют;
* делаются попытки использовать актуальную бесконечность: имеется в виду, что сумма бесконечного числа членов может иметь вполне определенное значение;
* самые большие надежды возлагаются на [https://ru.wikipedia.org/wiki/%D0%9A%D0%B2%D0%B0%D0%BD%D1%82%D0%BE%D0%B2%D1%8B%D0%B9_%D0%BA%D0%BE%D0%BC%D0%BF%D1%8C%D1%8E%D1%82%D0%B5%D1%80 [Квантовые гейты | квантовые компьютеры]]. Чтобы осуществить вычисление, во-первых, необходимо управлять кубитами, во-вторых, дать реализоваться квантовому алгоритму, в-третьих, измерить состояния кубитов регистра. В принципиальном отношении все три операции осуществимы.
== См. также ==
* [[Вычислимые функции]]
* [[Лямбда-исчисление]]
== Источники информации ==
*[https://en.wikipedia.org/wiki/Hypercomputation Wikipedia {{---}} Hypercomputation]*[https://ru.wikipedia.org/wiki/%D0%A1%D0%B2%D0%B5%D1%80%D1%85%D1%82%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%BE%D0%B2%D1%8B%D0%B5_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F Wikipedia {{---}} Сверхтьюринговые вычисления]* [https://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%97%D0%B5%D0%BD%D0%BE%D0%BD%D0%B0 Wikipedia {{---}} Машина Зенона]* [http://arxiv.org/ftp/math/papers/0209/0209332.pdf Hypercomputation: computing more than the Turing machine]
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Вычислительные формализмы]]
