3622
правки
Изменения
м
→Машина Зенона
Будем использовать двуленточную машину Зенона. На одной ленте будем симулировать машину Тюринга, а на второй записывать результат.
'''<tex> p(M,x):</tex>'''
записать 0 в первую ячейку на второй ленте ленте
'''while''' ''true'':
смоделировать очередной шаг работы данной машины Тьюринга на данном входена первой ленте
'''if''' машина Тьюринга остановилась:
записать 1 в первую ячейку на ленте
'''break'''
'''return''' первую ячейку на второй ленте
Такие вычисления, выходящие за рамки возможности машины Тьюринга, называются гипервычислениями.
Стоит заметить, что проблема остановки для самой машины Зенона не может быть решена на машине Зенона.
== Возможность супертьюринговых машин ==
