Изменения
Нет описания правки
== Машина Зенона ==
{{Определение
|definition =
'''Машина Зенона''' — это гипотетическая компьютерная модель, связанная с машиной Тьюринга, которая способна совершить счётное количество алгоритмических шагов за конечное время. В большинстве моделей вычислений такие машины не рассматриваются.
}}
Теория точки Омега, разработанная Франком Типплером, верна, только если машина Зенона может существовать.
Некоторые функции, которые не могут быть вычислены на машине Тьюринга, могут быть вычислены с использованием машины Зенона. Например, на ней может быть решена проблема остановки (что иллюстрируется следующим псевдокодом):
'''начало программы'''
записать 0 в первую ячейку на ленте;
'''начало цикла'''
смоделировать очередной шаг работы данной машины Тьюринга на данном входе;
'''если''' машина Тьюринга остановилась, '''то''' записать 1 в первую ячейку на ленте и '''прервать цикл''';
'''конец цикла'''
'''конец программы'''
Такие вычисления, выходящие за рамки возможности машины Тьюринга, называются гипервычислениями.
Стоит заметить, что проблема остановки для самой машины Зенона не может быть решена на машине Зенона.
== Возможность супертьюринговых машин ==
== Источники информации ==
*[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| Сверхтьюринговые вычисления]
* [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| Машина Зенона]
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Вычислительные формализмы]]
