Formal Definition and Examples of Turing Machines

Subroutines

We have included many practical examples of Turing machines to give the impression that using a $\text{TM}$ is like using a programming language on a computer. Indeed, $\text{TM}$s are the conceptual basis for the design of computer algorithms as well as for computers themselves. We’ll now show how to use $\text{TM}$s as subroutines. As with assembly language, it’s mostly a matter of putting results in a format and location that supports use by other $\text{TM}$s. The call-and-return mechanism consists of joining components with transitions.

Copying tape contents

A useful subroutine copies tape contents from one place to another. We’ll design a $\text{TM}$ that copies strings of $a$’s and $b$’s by appending its input to the right of the populated part of the tape. We’ll delimit the original input with a trailing # symbol. The plan is to mark each $a$ with $X$ and $b$ with $Y$. We then traverse each marked symbol left-to-right, appending what it stands for to the right end of the used part of the tape, and “unmark” each $X$ or $Y$ by reverting to its respective original $a$ or $b$. The following trace shows our plan with input $abbab\#$: