Language of TMs such that one state is visited most often

Question

To be safe, let me start this question by giving the definition of a TM I will be using: A TM is some $M = (Q, \Sigma, \Gamma, q_0, \delta, q_F)$, where $Q$ is the finite state set, $\Sigma \subset \Gamma$ are the input and working alphabet, $q_0, q_F$ are the initial and final states, and $\delta : Q \times \Gamma \times Q \times \Gamma \times \{L,N,R\}$ is the transition function. I am talking about single-tape TMs without input or output tape, so the initial configuration of input $w$ is just $B^{-\omega} q_0 w B^\omega$, where $B$ is the blank symbol.

The language I am considering is $L$ of all Turing machines $M$ which satisfy the following: There is a state $q$ of $M$ such that on the run of $M$ on the empty word $\varepsilon$, $q$ is visited more often than any other state.

"More often" talks about the cardinality, i.e. $q$ is visited more often than $p$ if $p$ is visited $n$ times (finitely often) and ($q$ is visited infinitely often or $q$ is visited finitely often but $>n$ times).

I came up with this language as an exercise for students, when I found that neither I nor any colleague I asked could come up with precise decidability results.

It is clear that $L$ is not coRE and therefore undecidable. We can, for example, reduce the epsilon halting problem $H_\varepsilon$ to $L$ by inserting a new state and have the TM visit that state once after each step of computation.

Unsolved so far is the question whether $L$ is RE. When allowing multiple tapes, it is not, as we can reduce $\overline{H_\varepsilon}$ to $L$. However, for single-tape TMs, our last guess was that it is enumerable by using the fact that a positive input which does not halt has to stay in a single state forever and can only expand the tape into one direction from that point on. We could not come up with an exact solution so far though.

Answer 1

After a deleted (wrong) answer I thought about the following to prove that $L$ is RE for single tape Turing machines.

As you said in the question, the problem is "recognizing" $M \in L$ that doesn't halt.

Note that a non-halting TM $M \in L$ not necessarily must expand the tape; for example:

q,[ -> q,[,R
q,a -> q,b,R
q,] -> q,],L
q,b -> q,a,L
causes an endless ping-pong in the same state q
...[aaaaa]....
   ^head

Also note that a non-halting TM $M \in L$ can expand the tape without changing its state; for example:

q,[ -> q,[,R
q,a -> q,b,R
q,B -> q,b,L
q,b -> q,a,L
causes an endless expanding loop:
...[aaaaaBB...

But for both expanding and non-expanding cases, we must have that the Turing machine $M$ must continue forever in the same state otherwise it doesn't belong to $L$ (cardinality constraint).

But the halting problem for one-state one-tape Turing machine, on a blank tape except for a finite number of cells, is decidable. See for example Gabor T. Herman: The uniform halting problem for generalized one-state turing machines. Information and Control; Volume 15, Issue 4, October 1969, Pages 353-367):

-----
Introduction: The uniform halting problem (UH) can be stated as follows: Give a decision procedure which for any given TM will decide whether or not it has an immortal instantaneous description (ID). An ID is called immortal if it has no terminal successor.
... we assume that in an ID the tape must be blank except for some finite number of squares ...
In this paper we show the solvability of the UH for one-state TM's ...
-----

So, to enumerate the $M_i \in L$ start a dovetailed simulation of $M_1,M_2,M_3,....$.

• if $M_i$ halts at steps $n$ then just count the states visited and outputs $M_i$ if there is a most visited state;

• otherwise, if $M_i$ doesn't halt at step $n$, and it is in state $q$; decide if the corresponding one-state TM halts or not. If it doesn't halt then $M$ belongs to $L$;...

• ... otherwise continue the dovetailed simulation (if it halts it will be detected at a later step)

Answer 2

This does not completely qualify, but I'll share it anyway.

We "cheat", by redefining TMs so that, instead of performing "read cell - write cell - move head", they instead perform "read cell - move head - write cell". The variant is still Turing powerful.

Given a TM $M$ using alphabet $\{0,1,-\}$ and with states $Q$, we can craft a TM $N(M)$ using alphabet $\{0,1,-\}\times Q \times S$ ($S$ defined below) and with states $q_1,q_2$ as follows:

• $N$ starts from state $q_1$, and writes on its first cell $(-,q_i,s_0)$ where $q_i$ is the starting state of $M$
• $N$ never leaves state $q_1$, while simulating $M$ on the current tape. The current cell $(x,q,s)$ contains the symbol under the head of $M$, the state $q$ of the simulated $M$, and the auxiliary state $s\in S$ of the simulator. Doing this heavily relies on the ability of writing the cell after the move, so that the $s$ in the current cell can be updated and written in the adjacent cell.
• If $M$ halts, then $N(M)$ starts alternating $q_1,q_2$ infinitely often.

TM with multiple tapes could also perform this trick, I guess.

This is a reduction because:

• $N(M)$ can be computed from $M$
• If $M$ halts on the empty tape, then $N(M)$ has no most visited state ($q_1,q_2$ are visited infinitely often).
• If $M$ does not halt on the empty tape, then $N(M)$ has a most visited state ($q_1$ is visited infinitely often, $q_2$ is never visited).