Formal Definition and Examples of Turing Machines

Learn how to use Turing machines as subroutines.


We have included many practical examples of Turing machines to give the impression that using a TM\text{TM} is like using a programming language on a computer. Indeed, TM\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 TM\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 TM\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 TM\text{TM} that copies strings of aa’s and bb’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 aa with XX and bb with YY. 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 XX or YY by reverting to its respective original aa or bb. The following trace shows our plan with input abbab#abbab\#:

Get hands-on with 1200+ tech skills courses.