2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ "Breaking the symmetry" means that there is a most visited state, right? So, isn't this reducing $H_\epsilon \leq L$, proving that $L$ is coRE? $\endgroup$ – chi May 9 '16 at 10:22
  • $\begingroup$ @chi: Ouch you're right ... I'll fix it $\endgroup$ – Vor May 9 '16 at 10:47
  • $\begingroup$ You cases do not describe every possible case. C1 does not have to bounce between the two limiters [,]: It can also "move" the right delimiter one tile to the right every bounce, effectively growing the tape arbitrarly. This case I described is not that bad of a counterexample, as it could be resolved by increasing the forward simulation run length to $|\Sigma| \cdot (l + |\Sigma|)$ or something similar. However, it shows that a single state can do more than one would expect and I am not so sure there is no actually problematic counterexample to your solution. $\endgroup$ – Andreas T May 10 '16 at 7:06
  • $\begingroup$ @AndreasT: you're right, also the expanding conditions can be very weird. I changed the answer using a standard result. Let me know if you see other issues. $\endgroup$ – Vor May 10 '16 at 7:59
  • $\begingroup$ Your new proof seems be right. Do I understand correctly that at the time this paper was written, the halting problem did not refer to whether a TM halts on some input but rather to whether a TM halts from a given configuration (which is more general and required in this case, as we can have non-blank content on the tape in both directions). $\endgroup$ – Andreas T May 12 '16 at 3:44
1
$\begingroup$

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).
$\endgroup$
  • $\begingroup$ Yes, this was basically our approach using two tapes. But as you said yourself, this does not solve the exact problem as I defined it in my question. $\endgroup$ – Andreas T May 9 '16 at 11:28
  • $\begingroup$ @AndreasT Right, I actually overlooked that. $\endgroup$ – chi May 9 '16 at 11:35

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.