Turing Machine with Two-Dimensional Tape



Step     of


Final Decision:

Path-local Decision:




A two-way deterministic counter Turing machine with a two-dimensional tape (2DTM‑2D‑Counter) is equivalent in power to a two-way deterministic free-tape Turing machine with a one-dimensional tape (Ordinary‑TM).

  • MOrdinary‑TM = (QOrdinary‑TM, TOrdinary‑TM, SOrdinary‑TM, POrdinary‑TM, qIOrdinary‑TM)
  • M2DTM‑2D‑Counter = (Q2DTM‑2D‑Counter, T2DTM‑2D‑Counter, S2DTM‑2D‑Counter, P2DTM‑2D‑Counter, qI2DTM‑2D‑Counter)
  • Counter = 𝜏
  • The convention follows Denning et al. (1978) but adds the input alphabet S ⊆ T to the definition.
  • We impose the restriction that T2DTM‑2D‑Counter = S2DTM‑2D‑Counter ∪ {𝜏}.
  • We define P2DTM‑2D‑Counter such that it includes four (4) forms:
    • q ] L(t/t', q'), q ] R(t/t', q'), q ] U(t/t', q'), and q ] D(t/t', q')
    • t ∈ T2DTM‑2D‑Counter ∪ {#}
    • However, we impose the restriction that t' ∈ {t, 𝜏}.

  • Our key idea is to map each symbol in TOrdinary‑TM to a unique "vertical" unary encoding terminated by #.
  • Albeit appealing, it is incorrect to simply map the ith symbol in TOrdinary‑TM (which we denote as ti) to a vertical string of i 𝜏's.
    • Reason: This does not allow us to simulate the instruction q ] 𝛘(tk/tj, q') if j < k.
    • The unary encoding of the replacement is shorter than that of the existing symbol, but M2DTM‑2D‑Counter is not capable of changing 𝜏's to #'s.
  • To account for this, we perform a fixed-length "vertical" unary mapping for each symbol in TOrdinary‑TM, as well as for #, Boundary and Void.
  • More formally:
    • We set the length of each unary mapping to N = |TOrdinary‑TM| + 3.
    • We map the ith symbol in TOrdinary‑TM to i 𝜏's followed by (N - i) #'s.
    • We map # to (N - 2) 𝜏's followed by two #'s. This accounts for instructions where the replacement symbol is #.
    • We map Void to (N - 1) 𝜏's followed by one #.
    • We map Boundary to N 𝜏's.
  • We can, thus, simulate the instruction q ] 𝛘(tk/tj) by changing the unary encoding of tk to that of Void, then writing the unary encoding of tj.
  • Note that the machine can encounter several Void's before the unary encoding of the symbol of interest. As a result, rewinding back to the top row of M2DTM‑2D‑Counter's tape is not straightforward. To address this, we pad the top row of the tape with Boundary.
  • Consequently, the first step in converting MOrdinary‑TM to to M2DTM‑2D‑Counter is to translate each symbol in the input string to the unary encoding of Boundary followed by the unary encoding of the symbol.
  • To illustrate, suppose 𝜏 = 1 and TOrdinary‑TM = {a, b}.

    Suppose the initial snapshot of MOrdinary‑TM's tape is as follows:

    # a b # ...
    The equivalent snapshot of M2DTM‑2D‑Counter's tape is shown below. The unary encodings of Boundary are highlighted in light blue, while the unary encodings of the symbols in the input string are highlighted in yellow.

    # 1 1 # ...
    # 1 1 # ...
    # 1 1 # ...
    # 1 1 # ...
    # 1 1 # ...
    # 1 1 # ...
    # # 1 # ...
    # # # # ...
    # # # # ...
    # # # # ...
    Suppose we want to perform the instruction q ] R(a/b, q'). The equivalent snapshot of M2DTM‑2D‑Counter's tape is shown below. The unary encoding of the newly written b is highlighted in yellow.

    # 1 1 # ...
    # 1 1 # ...
    # 1 1 # ...
    # 1 1 # ...
    # 1 1 # ...
    # 1 1 # ...
    # 1 1 # ...
    # # # # ...
    # # # # ...
    # # # # ...
    ... ... ... ... ...
    Suppose we want to perform the instruction q' ] R(b/a, q''). The equivalent snapshot of M2DTM‑2D‑Counter's tape is shown below. The unary encoding of Void is highlighted in light blue, while the unary encoding of the newly written a is highlighted in yellow.

    # 1 1 # ...
    # 1 1 # ...
    # 1 1 # ...
    # 1 1 # ...
    # 1 1 # ...
    # 1 1 # ...
    # 1 1 # ...
    # # 1 # ...
    # # 1 # ...
    # # # # ...
    # # 1 # ...
    # # # # ...
    # # # # ...
    # # # # ...
    # # # # ...
    ... ... ... ... ...

  • Our key idea is to establish a bijection between the one-dimensional tape of MOrdinary‑TM and the two-dimensional tape of M2DTM‑2D‑Counter. This can be done by placing the rows of M2DTM‑2D‑Counter next to each other and using a marker ⬤ ∉ T2DTM-2D-Counter to demarcate them.
  • To illustrate, suppose we have the following snapshot of M2DTM‑2D‑Counter's tape:

    # 1 1 1 1 # ...
    # 1 # 1 1 # ...
    # 1 # 1 # # ...
    # # # 1 # # ...
    ... ... ... ... ... ...
  • The equivalent snapshot of MOrdinary‑TM's tape is as follows:

    # 1 1 1 1 ⬤ # 1 # 1 1 ⬤ # 1 # 1 ⬤ # # # 1 ⬤ # ⬤ ...
  • Simulating the left and right movements of M2DTM‑2D‑Counter is straightforward, except for two cases:
    • If the tape head attempts to move (right) to a cell that has not yet been previously visited, MOrdinary‑TM has to make room for it by shifting all the contents starting from the nearest ⬤ up to the rightmost ⬤, one unit to the right.
    • The tape head attempts to move past the leftmost cell in a row. This is illegal.
  • Simulating the up and down movements of M2DTM‑2D‑Counter requires moving the tape head of MOrdinary‑TM to the left (for up) or to the right (for down) until the demarcator ⬤ is reached, signaling that the tape head is already "entering" the target row. From there, we continue moving the tape head in the same direction until the target column is reached.
    • This simulation entails keeping track of how many times the tape head has already moved. This information can be written on a separate tape. A two-tape (or, in general, a multi-tape) Turing machine is equivalent in power to a single-tape Turing machine (a sketch of the conversion is provided as an addendum).
    • If the target cell has not yet been previously visited, MOrdinary‑TM has to make room for it by shifting all the contents starting from the right of the newly vacated cell up to the rightmost ⬤, one unit to the right.
    • Attempting to move past the topmost row is illegal.

  • Let MMulti‑Tape‑TM be a multi-tape Turing machine and MOrdinary‑TM be an ordinary (single-tape) Turing machine.
  • Our key idea is to place the rows of the multi-tape machine next to each other and using a marker ⬤ that is not in the tape alphabet of MMulti‑Tape‑TM to demarcate them.
  • Meanwhile, to keep track of the position of the tape heads, we introduce an accented version of each symbol in the tape alphabet of MMulti‑Tape‑TM. This accented version is used to indicate that a tape head is pointing to that cell.
    • In this regard, the tape alphabet of MOrdinary‑TM is the union of the tape alphabet of MMulti‑Tape‑TM and their accented versions.
  • To illustrate, suppose we have the following snapshot of MMulti‑Tape‑TM's tapes:

    # a a e e # ...
    # a # e e # ...
    # a # a # # ...
  • The equivalent snapshot of MOrdinary‑TM's tape is as follows:

    # a a e ê ⬤ # â # e e ⬤ # a # â ⬤ # ⬤ ...
  • Simulating the left and right movements of MMulti‑Tape‑TM is analogous to the simulation presented in the conversion of M2DTM‑2D‑Counter to MOrdinary‑TM.

A two-way nondeterministic counter Turing machine with a two-dimensional tape (2NTM-2D-Counter) is equivalent in power to a two-way deterministic free-tape Turing machine with a one-dimensional tape (Ordinary-TM).

  • Let M2NTM‑2D‑Free‑Tape be a two-way nondeterministic free-tape Turing machine with a two-dimensional tape.
  • Let M2DTM‑Multi-2D‑Free‑Tape be a two-way deterministic free-tape Turing machine with multiple two-dimensional tapes.

  • We follow this line of thought:
    • Clearly, M2NTM‑2D‑Counter ⊆ M2NTM‑2D‑Free‑Tape.
    • We attempt to show that M2NTM‑2D‑Free‑Tape ⊆ M2DTM‑Multi-2D‑Free‑Tape by simulating the former using three (two-dimensional) tapes.
    • Each (two-dimensional) tape of M2DTM‑Multi-2D‑Free‑Tape can be converted to a (one-dimensional) tape of MOrdinary‑TM.
    • A multi-tape Turing machine is equivalent in power to an ordinary (single-tape) Turing machine; a sketch of the conversion is provided as an addendum.
  • Therefore, it suffices to prove that M2NTM‑2D‑Free‑Tape can be converted to M2DTM‑Multi-2D‑Free‑Tape using three tapes:
    • The first tape serves as an immutable storage for the input string.
    • The second tape carries out the actual simulation.
    • The third tape marks the address of the configuration executed by MMulti‑Tape‑TM in the computational tree of M2NTM‑2D‑Free‑Tape.
    • The nodes of the computational tree of M2NTM‑2D‑Free‑Tape should be visited in a breadth-first fashion. Visiting them in a depth-first fashion risks trapping the machine in a nonterminating branch.

  • Since M2DTM‑2D‑Counter ⊆ M2NTM‑2D‑Counter and we have already established that M2DTM‑2D‑Counter = MOrdinary‑TM, it follows that MOrdinary‑TM ⊆ M2NTM‑2D‑Counter.

  • Let MMulti‑Tape‑TM be a multi-tape Turing machine and MOrdinary‑TM be an ordinary (single-tape) Turing machine.
  • Our key idea is to place the rows of the multi-tape machine next to each other and using a marker ⬤ that is not in the tape alphabet of MMulti‑Tape‑TM to demarcate them.
  • Meanwhile, to keep track of the position of the tape heads, we introduce an accented version of each symbol in the tape alphabet of MMulti‑Tape‑TM. This accented version is used to indicate that a tape head is pointing to that cell.
    • In this regard, the tape alphabet of MOrdinary‑TM is the union of the tape alphabet of MMulti‑Tape‑TM and their accented versions.
  • To illustrate, suppose we have the following snapshot of MMulti‑Tape‑TM's tapes:

    # a a e e # ...
    # a # e e # ...
    # a # a # # ...
  • The equivalent snapshot of MOrdinary‑TM's tape is as follows:

    # a a e ê ⬤ # â # e e ⬤ # a # â ⬤ # ⬤ ...
  • Simulating the left and right movements of MMulti‑Tape‑TM is analogous to the simulation presented in the conversion of M2DTM‑2D‑Counter to MOrdinary‑TM.