Как именно работают макросы в машине Тьюринга?

У меня есть скриншот из моего учебника здесь (Sudkamp, ​​3e), и я пытаюсь понять, как макросы используются с машиной Тьюринга. Мне трудно понять это, тем более что я никогда раньше не изучал макросы. Если кто-то может помочь с объяснением здесь, я был бы очень признателен.

Единственное, что я действительно понимаю, это то, что CPY просто копирует ввод, и в итоге получается 3 n. В противном случае я действительно не понимаю, как прийти к такому выводу. Я могу попытаться быть более конкретным, если я слишком расплывчат, дайте мне знать.

Макросы в машинах Тьюринга


macros computation-theory turing-machines
person shmob    schedule 13.11.2017    source источник
comment
В учебнике сказано: Машины Тьюринга, предназначенные для вычисления функций, можно использовать как макросы при проектировании составных машин.   -  person shmob    schedule 14.11.2017

Ответы (1)


arrow_upward
1
arrow_downward

Для конкретной проблемы: да, через CPY вы получаете три раза n. Для вычисления f(n) = 3n машина затем вычисляет n+n+n = 3n посредством сложения A.

О макросах в целом: они действительно не работают так, как предлагает схема. Нельзя просто поставить машину для копирования на «место» в вычислении другой машины. Необходимы адаптации для алфавита, начального состояния и т.д. Проблема в том, что с ТМ программы становятся очень большими, многие состояния переходят и т. д. и нечитаемы. Итак, мы полагаем, что эти небольшие приспособления в принципе можно осуществить. Теперь мы больше не описываем сложные машины в деталях, а используем такие макросы для задач, которые, как было показано, могут быть вычислены с помощью TM (например, копирование и добавление). Полученное описание более понятно. Немного похоже на язык программирования более высокого уровня, где вы можете использовать сложные конструкции и структуры данных, не заботясь об их реализации на ассемблере.

person Peter Leupold    schedule 14.11.2017