In the context of a Turing machine, the tape is a component that serves as a place to store information. The tape can be thought of as as paper that is divided into squares, which we will refer to as tape cells. Each tape cell can either
Be left empty
A special thing about the tape, and also one of the reasons why Turing machines are strictly theoretical, is that it spans infinitely. That is, there are infinitely many empty tape cells spanning in both directions.
Since we now have access to the concept of blank tape cells on our tape, we can also use such blank tape cells in our representation conventions. For example, here's a representation convention that allows for representing multiple numbers on the tape:
We use the terms "a blank tape cell" and "a blank" interchangeably in this text.
With Turing machines, a restriction is placed on the initial state of the tape. It must contain at least one tally initially. Therefore, when choosing your representation convention for some domain, ensure that all elements of the domain can be represented using at least one tally.
Contain a tally (i.e., )
We can use the tape as a means of representing numbers. Since tape cells can only contain the symbol if they are not left blank, we will have to use the unary number system to represent numbers. For example, here's a representation of a tape containing the decimal number , assuming the representation convention is to repeat times to represent a number .
As you can see, we represented the decimal number by writing seven s side-by-side. On the left and right of the number are infinite tape cells that are blank.
To represent a multiset of positive integers , write s, followed by a blank, followed by s, followed by a blank, and so on...
Here's a representation of a tape containing the two decimal numbers and :
