3
$\begingroup$

Do additonal symbols on a turing machine actually change what is computationally possible on a machine, or do they just make them easier to work with? For example is there anything a 3 symbol turing machine could compute that a 2 symbol turing machine could not? (Assuming each machine can have any number of states).

$\endgroup$
  • $\begingroup$ Sorry if the question doesn't make sense or is stupid, I'm very new to the concept of TMs. $\endgroup$ – user57862 Sep 4 '16 at 14:56
  • $\begingroup$ Possible duplicate. $\endgroup$ – Raphael Sep 4 '16 at 21:03
2
$\begingroup$

Hint: can you express more integers by writing them in a bigger base?

I'll go with the definition where the blank is counted as a symbol. A Turing machine must have at least one non-blank symbol, i.e. at least two symbols. With 0 symbols there's no way to build a tape, and with only the blank symbol there's a single possible tape so the machine is effectively a finite automaton.

Any $n$-symbol Turing machine can be translated to a Turing machine with the symbols $\{0,1\}$ where $0$ is the blank symbol. Let $k$ be an integer such as $2^k \ge n$, and number the symbols from $0$ to $n-1$, with the blank symbol numbered $0$. Translate the tape by mapping each symbol to the sequence of $k$ symbols that is the representation of its number in base $2$.

The state set increases. For each original state $q$, we define several types of states in the new machine:

  • Forward read states $(\mathsf{R},q,i,x)$ where $0 \le i \le k-2$ and $x \le 2^i$: read the bits that represent one original input symbol, remembering the position $i$ and the partial accumulated number. These states have a right transition to either $(\mathsf{R},q,i+1,2x)$ or $(\mathsf{R},q,i+1,2x+1)$ depending on the symbol read from the new tape.
  • Decision states $(\mathsf{R},q,k-1,x)$: if there is a transition $\delta(q,x) = (q',x',d)$ in the original machine, then transition to a write state $(\mathsf{W},q',d,k-1,x')$. If the state $q$ is final in the original machine, this state is final in the new machine.
  • Write states $(\mathsf{W},q',d,i,x')$ where $1 \le i \le k-1$ and $x' \le 2^i$: write the low-order bit of $x'$ to the tape and move left to $(\mathsf{W},q',d,i-1,\lfloor x'/2 \rfloor)$.
  • Last-bit write states $(\mathsf{W},q',d,0,x')$ where $x' \in \{0,1\}$: write $x'$ to the tape, and move to a fast-forward state or a fast-backward state depending on $d$.
  • Fast-forward and fast-backward states $(\mathsf{F},q',d,i)$ where $0 \le i \le k-1$: keep moving in the same direction and decrement $i$ until it reaches $0$, at which point, switch to the corresponding forward read state. These states are used to either skip forward to the beginning of the part of the tape that represents the next original symbol after a right transition in the original tape, or to skip backward to the beginning of the part of the tape that represents the previous original symbol after a left transition in the original tape.

In summary, we make three passes over each symbol: one to read it, one to write the new symbol, and one to reposition the tape.

The details are tedious but not difficult.

$\endgroup$
  • $\begingroup$ Is this question resp. its answer very different? $\endgroup$ – Raphael Sep 4 '16 at 21:03
  • $\begingroup$ @Raphael Closely related, but not enough that I'd consider it a duplicate. The earlier question puts a lot of emphasis on cardinality arguments that turn out to be wrong or irrelevant, which obscures the core point. $\endgroup$ – Gilles 'SO- stop being evil' Sep 5 '16 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.