Изменения
Нет описания правки
'''Машина Зенона''' (англ. ''zeno machine'') — это гипотетическая компьютерная модель, связанная с машиной Тьюринга, которая способна совершить счётное количество алгоритмических шагов за конечное время. В большинстве моделей вычислений такие машины не рассматриваются.
}}
Некоторые функции, которые не могут быть вычислены на машине Тьюринга, могут быть вычислены с использованием машины Зенона. Например, на ней может быть решена проблема остановки (что иллюстрируется следующим псевдокодом): Будем использовать двуленточную машину Зенона. На одной ленте будем симулировать машину Тюринга, а на второй записывать результат. '''<tex>P</tex>p(<tex>M</tex>, <tex>x):</tex>)'''
записать 0 в первую ячейку на ленте
'''while''' ''true'':
смоделировать очередной шаг работы данной машины Тьюринга на данном входе
'''if''' машина Тьюринга остановилась:
записать 1 в первую ячейку на ленте
'''break'''
