How exactly do macros in a Turing Machine work?
I have a screenshot from my textbook here (Sudkamp, 3e), and I am trying to understand how macros are used with the Turing Machine. I am having a hard time grasping it, especially since I have never learned about macros before. If anyone can help with an explanation here, I would really appreciate it.
The only thing I really understand is that the CPY just copies the input, and then there ends up being 3 n’s. Otherwise, I don't really get how to come to that conclusion. I can try to be more specific if I am being too vague, let me know.
For the specific problem: yes, via CPY you get three times n. For computing f(n) = 3n the machine then computes n+n+n = 3n via the addition A.
About macros in general: they do not really work in the way suggested by the diagram. You cannot just put a machine for copying in a "place" in the computation of another machine. Adaptions for alphabet, start state etc. are necessary. The problem is that with TMs programs become very big, many states transition etc. and unreadable. So we suppose that these little adaptions can be done in principle. Now we do not specify complex machines in detail anymore, but use such macros for tasks that have been shown to be computable by a TM (like copying and adding). The resulting description is more understandable. A bit like a higher-level programming language, where you can use complex constructs and data structures without caring about their assembler implementation.