В каждый из последующих моментов времени машина М недетерминированным образом выбирает подходящую команду (1.19) и ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Марченков С.С. Элементарные рекурсивные функции


В каждый из последующих моментов времени машина М недетерминированным образом выбирает подходящую команду (1.19) и в соответствии с этой командой изменяет положение головок на лентах и содержимое рабочей ленты. Работа машины завершается, когда она достигает заключительного состояния qs либо когда в программе машины нет необходимой команды. Более формально понятие вычисления на машине Тьюринга М можно ввести на основе понятия конфигурации.

(cкачать страницу)

Смотреть книгу на libgen

В каждый из последующих моментов времени машина М недетерминированным образом выбирает подходящую команду (1.19) и в соответствии с этой командой изменяет положение головок на лентах и содержимое рабочей ленты.  Работа машины завершается,  когда она достигает заключительного состояния qs либо когда в программе машины нет необходимой команды.  Более формально понятие вычисления на машине Тьюринга М можно ввести на основе понятия конфигурации.