Интернет магазин китайских планшетных компьютеров

Компьютеры - Машина Зенона - Машина Зенона и вычислимость

Некоторые функции, которые не могут быть вычислены на машине Тьюринга, могут быть вычислены с использованием машины Зенона. Например, на ней может быть решена проблема остановки:

начало программы 
  записать 0 в первую ячейку на ленте;
  начало цикла
    смоделировать очередной шаг работы данной машины Тьюринга на данном входе;
    если машина Тьюринга остановилась, то записать 1 в первую ячейку на ленте и прервать цикл;
  конец цикла
конец программы

Такие вычисления, выходящие за рамки возможности машины Тьюринга, называются гипервычислениями.

Стоит заметить, что проблема остановки для самой машины Зенона не может быть решена на машине Зенона..