Tape

From Esolang
Jump to: navigation, search

A tape is the traditional data storage unit of a Turing machine. A tape is divided into cells (Turing originally called these squares). Each cell may contain one symbol drawn from a finite alphabet (which generally includes a blank symbol).

A tape is typically accessed by means of a single read/write head, but variations may have multiple heads, each of which may be restricted to either read- or write-only. The cell which the head is over at any given time is called the current cell.

A standard tape can be thought of as an abstract data structure which supports the following operations:

  • Left(t): move the head one cell to the left
  • Right(t): move the head one cell to the right
  • s ← Read(t): return the symbol in the current cell
  • Write(t, s): write the given symbol into the current cell, destroying whatever symbol was previously written there

The original tape of Turing's machine was infinite in both directions. Subsequent formulations of the Turing machine have often restricted it to being infinite towards the right only (implying that the Left() operation can sometimes fail - this is considered to be the same as a hang) and starting at the leftmost position.

The tape is generally considered to be initially filled with blanks. However, it can also be considered to contain initial input, as there is no other way to specify input for a traditional Turing machine.

The tape need not be considered "really infinite," only unbounded in the sense that if the head ever exceeds the bound, a new blank cell is added to the tape at that position.

See Category:Cell-based for more tape-based esolangs.