Изменения
Нет описания правки
== Сверхтьюринговые вычисления ==
'''Сверхтьюринговыми вычислениями''' (или '''гипервычислениями''' (англ. <tex>\it ''hypercomputation</tex>'')) называются такие вычисления, которые не могут быть проделаны на машине Тьюринга
, а следовательно не исчислимы в рамках тезисов Черча-Тьюринга.
{{Определение
|definition =
'''Машина Зенона''' <tex>\it (''zeno </tex> <tex>\it machine'') </tex> — — это гипотетическая компьютерная модель, связанная с машиной Тьюринга, которая способна совершить счётное количество алгоритмических шагов за конечное время. В большинстве моделей вычислений такие машины не рассматриваются.
}}
Некоторые функции, которые не могут быть вычислены на машине Тьюринга, могут быть вычислены с использованием машины Зенона. Например, на ней может быть решена проблема остановки (что иллюстрируется следующим псевдокодом):
