Конспект установочных лекций по комплексному курсу Информатика, Теория информации



Состояние Левое слово Знак Правое слово


 Конфигурация TM:                 si             w1                  a                 w2

Регистры машины М имеют следующее содержимое:

1.      Регистр: <а> о w как зеркально отраженное двоичное число. (½= L,¾  = 0)

2.      Регистр: W1 как двоичное число.

3.      Регистр: i для состояния si.

Последующие регистры могут использоваться для запоминания переходов состояний. Это требует кодирования входных знаков и состояний числами.

Программа R-машины имеет следующую структуру, причем без oгpaничения общности считается, что sw есть единственное заключительное состояние Т-машины:

While3 (вычислим новое состояние и изменения ленты).

При выбранном представлении конфигураций Т-машины через  содержимое   регистров чтение знака под головкой Т-машины соответствует выяснению четности или нечетности содержимого первого регистра, а запись соответствует операции целочисленного деления на два с дальнейшим действием +1, если должен записываться знак L, +0 - в противном случае.

Сдвигу головки вправо соответствуют следующие операции:

·         содержимое второго регистра умножить на два; записать знак L путем прибавления единицы ко второму регистру, если содержимое первого регистра нечетно;

·         содержимое первого регистра разделить на два.

Сдвигу головки влево соответствуют следующие операции:

·         содержимое первого регистра умножить на два; записать знак L путем прибавления единицы к первому регистру, если содержимое второго регистра нечетно;

·         содержимое второго регистра разделить на два.

Теорема. Любая частично рекурсивная функция RM-вычислима.

Идея доказательства. Принципы, по которым строятся частично рекурсивные функции, могут быть смоделированы на R-машинах.

Теорема. Любая RM-вычислимая функция частично рекурсивна.




Содержание  Назад  Вперед