Computer Science – Are These Definitions of Oblivious Turing Machines Equivalent?

computabilitycomputer scienceturing-machines

I'm confused about the definition of an oblivious Turing machine. According to this answer (and the comments below it), it can be defined as follows.

  1. A type-1 oblivious Turing machine is a new kind of machine (not an ordinary Turing machine), which is similar to an ordinary Turing machine, except:
  • The transition function does not specify the head movement;
  • In addition to the transition function, the definition of each machine includes a head movement function $s(i, |x|)$, which tells the tape head how to move on step $i$, given an input $x$ of length $|x|$.

However, there is another possible definition, which I think is actually a more natural interpretation of the quote from Arora & Barak in the answer cited above:

  1. A type-2 oblivious Turing machine is an ordinary Turing machine, which happens to satisfy the following property:
  • There exists a function $s(i, |x|)$ that happens to give the head movement (which is determined by the transition function) on step $i$ for any input $x$ of length $|x|$.

Are these two notions equivalent, in the sense that they can compute the same functions? If so, how can we simulate each one using the other?

Also, if these definitions are not equivalent, which one is actually meant by the standard usage of "oblivious Turing machine"?

Every type-2 OTM is easily seen to be a type-1 OTM, since we can simply remove the head movement specification from the transition function and define $s$ based on the type-2 OTM's movement. So the question boils down to showing the reverse direction.

Best Answer

The definitions are not equivalent, and type 1 is much too strong.

Take a uncomputable function $f \colon \mathbb{N} \to \mathbb{N}$ such that $f(n) \geq n$. Take the movement function $$s(i, n) = \begin{cases}\rightarrow, &\text{if $i \leq f(n)$} \\ \downarrow, &\text{otherwise} \end{cases}$$ And the transition function which writes $b$ if it sees $a$ or blank, and stops if it sees $b$. The resulting type 1 machine transforms $a^n$ to $b^{f(n)}$, thus computing an uncomputable function.

This definition is in fact more similar to Turing machine with advice (used for example to define the class $\mathrm{P/poly}$). The usual definition of the oblivious TM is the second one, as in Arora&Barak.

Related Question