I. Programming Tricks

1. Multiple Tracks

Think of tape symbols as vectors with $k$ components, each chosen from a finite alphabet.

Makes the tape appear to have $k$ tracks.

2. Marking

A common use for an extra track is to mark certain positions.

e.g. Almost all tape squares hold B (blank) in this track, but several hold special symbols (marks) that allow the TM to find particular places on the tape.

3. Caching in the State

Turing Machine with Storage

The state can also be a vector.

• First component is the “control state.”
• Other components hold data from a finite alphabet.
• An example

II. Restrictions

1. Semi-infinite Tape

We can assume the TM never moves left from the initial position of the head.

Let this position be 0

• positions to the right are 1, 2, …