Formal Definition and Examples of Turing Machines
Learn how to use Turing machines as subroutines.
We'll cover the following
Subroutines
We have included many practical examples of Turing machines to give the impression that using a is like using a programming language on a computer. Indeed, s are the conceptual basis for the design of computer algorithms as well as for computers themselves. We’ll now show how to use 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 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 that copies strings of ’s and ’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 with and with . 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 or by reverting to its respective original or . The following trace shows our plan with input :
Get hands-on with 1200+ tech skills courses.