Эквивалентность понятий вычислимости - часть 3

Теорема: Для каждой программы Р для k—R—машины можно задать Т-машину М с алфавитом ленты {¾, ½}, которая моделирует данную R-машину.

Доказательство. Структурная индукция по структуре программы Р:

Р =e         М читает входное слово, не изменяя его;

Р = sucCi      М продвигается до i-го входного значения, добавляет один штрих ½ и возвращается в исходную позицию;

Р = predj М продвигается до i-го входного значения, вычитает один штрих и возвращается в исходную позицию;

Р = P1;P2 последовательная композиция Т-машин для P1 и Р2;

Р = whilei(Po) М продвигается до i-го входного значения; если там стоит штриховое представление для числа 0, следует остановка; в противном случае М возвращается к началу, запускает программу Р0 для М0, причем все состояния останова М0 заменяются на начальное состояние М.

Можно говорить также о моделировании Т-машины на k-R-машине, кодируя ленту в регистрах.

Теорема. Для каждой детерминированной машины Тьюринга TM, которая вычисляет функцию f: Ni -> Nj  в обычном кодировании через {¾, ½}, существует k-регистровая машина (причем число регистров k зависит от машины Тьюринга TM), моделирующая машину TM.

Идея доказательства. Можно выбрать примерно следующую кодировку конфигурации Т-машины TM через состояния регистров R-машины М: