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!
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.