1
$\begingroup$

I've been going through some questions on old homework. Here was a question that confused me somehow.

Question: Given a language $$L=\{\langle M\rangle\ |\ M \text{ is a Turing machine. } M \text{ goes through some configuration } (q,s,i) \text{ infinite times on input } \epsilon\}$$ determine whether it's decidable, if not then determine if it's Turing-acceptable.

A configuration of $M$ is a triple $(q, s, i)$, where $q$ is the state, $s$ the tape (with its content), and $i$ the location of the head.

I was required to prove / refute whether $L\subseteq L'$ for $L'=\{\langle M\rangle\ |\ M \text{ does not halt on input } \epsilon\}$ so I refuted it by giving a Turing machine:

enter image description here

I don't know if this has something to do with a mapping function for the coming sections.

$\endgroup$
3
  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. We're not really looking for posts that are just the statement of an exercise-like task. $\endgroup$
    – D.W.
    May 10, 2022 at 4:24
  • $\begingroup$ @D.W The asker has solved correctly the hint, I believe, given to the question, "whether $L\subseteq L'$". $\endgroup$
    – John L.
    May 10, 2022 at 4:25
  • $\begingroup$ @D.W. it's a question and I can't explain exactly where I got stuck, I always try a lot of ways to solve a question and I get stuck somehow after a lot of thinking so I can't really describe where I got stuck exactly. Believe me, it's not just that I come and throw a question here and demand someone to solve it for me, I take the answer, analyze it and understand it as much as I can, and as you see if there is something that I can't understand I ask the answerer. You can see all my previous posts, when I achieve an answer I post it, it may not be here but in other stackoverflow sites. $\endgroup$
    – Mohamad S.
    May 10, 2022 at 17:55

1 Answer 1

3
$\begingroup$

No, $L$ is not decidable.

Summary (a complete proof for experienced readers): Given a Turing-machine $T$, we can construct algorithmically Turing-machine U that simulates $T$. Moreover, $U$ will record all $T$'s configuration history on the tape. $U$ will check whether there is one configuration repeated at least once after each simulation step. If there is, $U$ will instead move to the right always. Moreover, if $T$ halts, then $U$ will move left and right alternately. We can see that $T$ halts on empty input iff $U\in L$. Hence $L$ is undecidable.

Proof by contradiction

Given a Turing machine $T$, we will construct another Turing machine $U$ algorithmically so that $U$ is in $L$ iff $T$ halts on empty input, in the next section, "Construction of $U$ from $T$".

If $L$ is decidable, i.e., we can decide whether $U$ is in $L$, then we can decide whether $T$ halts on empty input, i.e., the HALT problem on empty input is decidable. However, the HALT problem on empty input is not decidable. That means the assumption "$L$ is decidable" is wrong. So $L$ is undecidable.

(This technique is called Turing-reduction that you might have learned or you will learn.)

Now the problem is how to construct such a $U$.

Construction of $U$ from $T$

We can view $T$'s actions upon empty input as a sequence of transitions from configuration $c_k=(q_k, s_k, i_k)$ to $c_{k+1}=(q_{k+1}, s_{k+1}, i_{k+1})$ for $k=0,1,2,\cdots$, where $c_0$ is the initial configuration and $k$ may or may not goes to infinity.

Given empty input, $U$ will simulate $T$ in the following way. The illustration below is what the tape looks like before and after simulating $T$ for $m$ steps, usually, where block $b_k$ encodes $c_k$. $$\begin{aligned} \text{before: }\ &\underbrace{\overline\sqcup\sigma_0}_{b_0}\#\# \underbrace{0\overline\sqcup\sigma_1}_{b_1}\#\# \underbrace{\overline01\sigma_2}_{b_2}\# \underbrace{\overline\sqcup11\sigma_3}_{b_3}\#\#\cdots\#\# \underbrace{\cdots1\overset{\downarrow}{0}0\cdots}_{b_{m-1}}\\ \text{ after: }\ &\underbrace{\overline\sqcup\sigma_0}_{b_0}\#\# \underbrace{0\overline\sqcup\sigma_1}_{b_1}\#\# \underbrace{\overline01\sigma_2}_{b_2}\# \underbrace{\overline\sqcup11\sigma_3}_{b_3}\#\#\cdots\#\# \underbrace{\cdots1\overline{0}0\cdots\sigma_{m-1}}_{b_{m-1}}\#\# \underbrace{\cdots11\overset{\downarrow}{0}\cdots}_{b_{m}} \end{aligned}$$ The symbol $\sqcup$ is the tape blank symbol. The extra symbol $\#$ is a block separator. $\sigma_k$ is a tape symbol that represents the state $q_k$. In each block $b_k$ except the rightmost block, there is a unique symbol that has a bar on it; that symbol marks the location of $T$'s head at configuration $c_k$. In the rightmost block, the arrow above one of the symbols indicates the current head position of $U$. (While that bar is a part of each "barred symbols" on the tape, that arrow is not. The arrow just to indicate the head position of $U$. Similarly, those underbraces with $b_k$ are not part of the tape. They are used to group the symbols)

For the $m$-th step taken by $T$, $U$ will change its tape from "before" to "after" as follows.

  1. mark the current head location by adding a bar to the current tape symbol,
  2. append $\sigma_{m-1}\#\#$ to the right of the current block $b_{m-1}$, which is also the rightmost block, where $\sigma_{m-1}$ is the current state of the simulated $T$.
  3. append a copy of $b_{m-1}$ to the right, which becomes the new rightmost block. Remove the rightmost symbol $\sigma_{m-1}$.
  4. Move head to unique cell with a tape symbol that has a bar at the rightmost block. Remove the bar. Simulate $T$'s action.

With the steps above, $U$ simulates $T$ with $T$'s computation history $c_0, c_1, c_2, \cdots$ preserved as well.

Furthermore, between step 2 and step 3, $U$ will also perform step 2' as below.
$\quad$2'. Check whether there is one configuration that has been repeated by $T$. This is possible since $U$ preserves the full computation history of $T$. If a repetition is found, $U$ will always moves to right regardless of the content of the tape (so no other kinds of actions can be taken by $U$ any more).

Furthermore, after step 4, if the simulated $T$ halts, $U$ will move left or right alternately forever. (so no other kinds of actions can be taken by $U$ any more). In particular, $U$ will repeat one of its own configurations infinite times.

On input other than the empty word, $U$ will halt immediately.

Claim: $U\in L$ $\iff$ $T$ halts on empty input.
Proof:
"$\impliedby$": This is straightforward by the construction of $U$.
"$\implies$": If $T$ does not halt, either it never repeat its configuration or repeat one configuration at least twice. In the former case, $U$ will write more and more blocks. In the latter case, $U$ will always move right after some time. In both cases, $U$ cannot repeat any configuration infinite times.

$\endgroup$
4
  • $\begingroup$ $L$ is Turing-acceptable since we can adapt a universal Turing machine to simulate a given machine $T$ similarly to $U$, accepting once $T$ is found to repeat one configuration. $\endgroup$
    – John L.
    May 10, 2022 at 5:23
  • $\begingroup$ What I can see is that you've made a mapping function (or something similar) which is $L'\leq_mL$ but it's not given that $L'$ is decidable so what's your point? $\endgroup$
    – Mohamad S.
    May 10, 2022 at 17:51
  • $\begingroup$ @CSStudent Please come to chat with me. $\endgroup$
    – John L.
    May 10, 2022 at 18:53
  • $\begingroup$ This answer can be summarized as "Given a Turing machine $T$, we can construct algorithmically Turing machine $U$ that repeats some configuration infinite times on empty input iff $T$ halts on empty input. Since it is undecidable whether $T$ halts on empty input, so it $L$." $\endgroup$
    – John L.
    May 11, 2022 at 2:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.