A quick definition: we say a Turing Machine $A$ is mapping reducible to an another Turing Machine $B$ if $w \in A \Leftrightarrow c(w) \in B$, for some computatble function $c : \Sigma^* \to \Sigma^*$.

I'm working on the following problem: is the language $\{\langle M \rangle : \text{ $\langle M \rangle$ is a description of a TM that on every input $w$ eventually leaves start state}\}$ decidable or not. Let's call it language $X$. I will argue by contradiction to show that $X$ is not decidable.

One way of tackling this I figured is to reduce $E_{\text{TM}}$ (language of those descriptions of TMs $\langle M \rangle$ that have empty languages themselves) to it, by noting that if we could show that arbitrary TMs are mapping reducible to some special two-state TM with a possibly extended alphabet (arbitrary large, though of course not infinite), we would be done. This special Turing Machine is assumed to be such that one state is accepting and the other is just the start state. All logic is then handled by the start state, which is thus always the next state of execution until acceptance (if acceptance indeed occurs).

Indeed if such construction is possible from an arbitrary TM it could easily be used then to solve $E_{\text{TM}}$ if we assume $X$ is decidable, which we know is not decidable: 1) on input $\langle M \rangle$, convert this description to the description of the two-state mapping reduced equivalent, say $\langle M_\text{2-state}\rangle$; 2) test whether $M_\text{2-state}$ has inputs leaving the start state (using our assumed decider for $X$); if not, the language of $M$ is empty, so we accept; otherwise, that is if $M_\text{2-state}$ has inputs leaving the start state, the language of $M$ is not empty, and we reject.

But now I doubt whether we can actually convert a TM to a two-state TM like I proposed... even if allowed any size of alphabet. Maybe one cannot put all the state logic on the tape... Any thoughts on the problem? Your help is greatly appreciated!

  • $\begingroup$ Do your Turing machines have tapes that are infinite in both directions, or just infinite in one direction? Here is why I ask. If there is any instruction which says that, when in the start state, there is a tape symbol which causes the machine to move the head right and stay in the start state, then by just repeating that symbol in every cell we have an input from which the machine never leaves the start state. But what happens if the machine tries to move left when in the start state and on the first symbol of the input? That seems to depend on the formalization of Turing machines used. $\endgroup$ – Carl Mummert Dec 3 '16 at 1:48
  • $\begingroup$ @CarlMummert Many thanks for your comment! Your time and effort is greatly appreciated (especially being as busy as a professor)! That could work, but only if one is allowed to input strings of infinite length. The Turing machine is assumed to behave such that when it goes off the tape at the left hand side, it just remains there for that step. I guess your suggestion is to prove that $X = \emptyset$? Is my own attempt clear? Can we emulate Turing Machines using only a 2-state machine but with a possibly very large alphabet? $\endgroup$ – Jori Dec 3 '16 at 4:10
  • $\begingroup$ We assume of course thus that the tape only extends infinitely long in the right hand direction. $\endgroup$ – Jori Dec 3 '16 at 4:11
  • $\begingroup$ I don't see any easy way to reduce the number of states to 2 by using a larger language. As long as the tape doesn't move, the machine can use that tape cell to remember which state it is in. But as soon as the machine moves to a new tape cell, that will have one of the original input symbols, and the 2-state machine will not have any internal state information to know what to do next. $\endgroup$ – Carl Mummert Dec 3 '16 at 13:58
  • $\begingroup$ As a test case, I don't see an easy way to make a 2-state Turing machine that accepts exactly the strings that start with $110$, $101$, or $011$. If every machine is equivalent to a 2-state machine, there should be one. $\endgroup$ – Carl Mummert Dec 3 '16 at 14:37

This depends on what definition of Turing machine you are using. If a Turing machine is defined to have only 2 symbols blank and 1, then X is decidable. If you mean to define a set that includes all Turing machines over all alphabets, then X is not decidable.

First, we should get some tools in hand, namely a Turing machine H' that halts iff another Turing machine H leaves the start state. We can construct H' from H by using a Turing machine that takes Turing machines as input, identifies the start state, deletes all the other states and replaces any instruction in the start state that transitions to another state with an instruction that is the same except that it transitions to the halting state. Now the output is H' because if H leaves the start state on any input, then H' will halt on that input. If H does not leave the start state on any input, then H' will not halt on that input. Now to decide whether H is in X, we necessarily must determine if H' halts on every input.

Let's start with the strict definition of Turing machine that only allows 2-symbols. This definition is simple and Turing-complete (i.e. anything provable with a large alphabet can be proved with a 2 symbol alphabet). Now, the machine takes numbers represented by tally marks as input. There are not that many 2-state 2-symbol Turing machines and it is easy to analyze them to determine how far they can move left or right and still halt. Indeed, it would not be hard to determine the maximum number of shifts possible for all halting 2-state, 2-symbol machines. If you run all the machines that many shifts, any machine that has not yet halted will never halt. This decides whether H', and therefore H is in X.

Now, moving on to the case where we are letting the machines have any size alphabet. In this case, you can still define H'. Now consider all H' with m-symbol alphabets. There are finitely many. Supposing X is decidable, we could list them, and then test whether they are in X. If not in X, they do not halt. Delete them from the list. Now run all the halting 2-state, m-symbol machines in the usual diagonal way, until all machines halt. The last machine to halt has determined s(m), the maximal shifts function. The selection of m was arbitrary, so we determine s(m) for all m. But s(m) is uncomputable, a contradiction. Therefore, our supposition that X is decidable must be false.

| cite | improve this answer | |

I'm a few years late on this, I just wanted to add some thoughts.

A single state, single tape Turing machine is decidable. Basically, as stated in comments, once you move from the start, you have no idea whether you are still on the start or not. You can't encode that in the symbols since you have not yet visited these locations yet.

However, a TWO state Turing machine, ignoring the accepting state, IS possible. A proof is in Claude Shannon's "A Universal Turing machine with Two Internal States." He shows how to translate a Turing machine with m symbols and n states into another with 4mn + m symbols and 2 states.

In addition, a Turing machine with one state and 2 tapes can also be universal. This SE post shows that, but it's almost trivial. Just encode state on one tape and use the other for actual computation.

One last way to allow only one state is to put two (or more) heads on the same tape, next to one another, so that you can read two adjacent symbols at once. You can encode state in this system by writing it to the location that will be read again by the next step.

I don't have formal proofs for these, but it shouldn't be too difficult to put them together.

| cite | improve this answer | |

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.