Конспект установочных лекций по комплексному курсу Информатика, Теория информации
Эквивалентность понятий вычислимости - часть 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-машины М:
