Given a TM T , is there an input string that causes T to enter every one of its nonhalting states?

Question

Given a TM T , is there an input string that causes T to enter every one of its nonhalting states?

I think it is undecideable and want to use reduction to prove it, but can't think of an undecideable problem to reduce it to. Any hint helps.

Answer 1

It seems to me that this can shown to be undecidable via reduction involving listing of a finite number of machines.

First lets write $\mathrm{EMPTY} \subset \mathbb{N}$ to denote the indexes of all those TM's that halt on empty input (which is known to be undecidable). Now consider $\mathrm{ONE} \subset \mathbb{N}$ which is used to denote all those TM's that halt on at least one or more inputs. Now it can be shown that $\mathrm{ONE}$ is undecidable (by using it to solve $\mathrm{EMPTY}$). Let's denote the set $A \subset \mathbb{N}$ for indexes of those TM's such that there exist one or more inputs on which all the non-halting states of the TM are visited. We want to use an oracle for $A$ to solve for $\mathrm{ONE}$, hence showing that $A$ is undecidable.

---

First, for simplicity, let's assume that in our computational model we only allow one halt state. Let's specifically consider a TM with non-halting states $S=\{x\in \mathbb{N}\,|\, x \leq 20\}$. Let's implicitly assume $0$ to be starting state.

Given a program $P$, we want to solve for $\mathrm{ONE}$ by making a list of all possible machines $P_X$ (where $X \subseteq S$). Since the number of subsets of a finite set such as $S$ will be finite, the list of machines will also be finite. Let's try to consider how $P_S$ will be formed. Given $P$, we can form $P_S$ by changing the halt state $H$ (halt) to a normal non-halting state $N$ (nothing) with both its transitions going from $N$ to $N$ (and basically doing nothing). Let's denote the index of program $P$ as $e \in \mathbb{N}$. Similarly denote the index of $P_S$ as $e_S \in \mathbb{N}$.

First observe that we have $e_S \in A$ implying $e \in \mathrm{ONE}$. Now basically we want to inquire as to when $e_S \notin A$ could be true and yet we get $e \in \mathrm{ONE}$. Let's assume it to be the case that if $e \in \mathrm{ONE}$ then there must exist at least one halting input for which all the states of $P$ (in $S$) were being visited. In that case $e_S \notin A$ would imply $e \notin \mathrm{ONE}$.

---

When we have $X \subset S$, the general idea is similar (but slightly more complicated). Essentially we want to form the program $P_X$ by merging all the states corresponding to $X'=S-X$ into a single block state $B$ (for block). So, if in the original program $P$, there was a transition going from some $s_1 \in X$ to $s_2 \in X'$, in $P_X$ we would have the same transition going from $s_1$ to $B$. In $P_X$, transitions from $s_1 \in X \cup \{H\}$ to $s_2 \in X \cup \{H\}$ remain as they are in $P$. Also, in $P_X$, we declare $B$ to be halt state and convert $H$ to be a non-halting state $N$ (as before, simply looping to itself and doing nothing).

We have again $e_X \in A$ implying $e \in \mathrm{ONE}$. Let's assume it to be the case that if $e \in \mathrm{ONE}$ then there must exist at least one halting input for which the states of $P$ (in $S$) that were being visited were exactly the ones in $X$. In that case $e_X \notin A$ would imply $e \notin \mathrm{ONE}$.

So, given the program $P$ (with index $e$), we list all the possible machines $P_X$ (with indexes $e_X$) formed from arbitary $X \subseteq S$. If $e_X \in A$ for any one of them then we return $e \in \mathrm{ONE}$ as true. If $e_X \notin A$ for all possible machines $P_X$ (we only have a finite number of them) then we return $e \notin \mathrm{ONE}$ as true.