I have an idea of how to approach the problem, but I'm not sure about it. Given a Turing Machine, I can check how many states the machine has, and somehow by the number of states to know if the run uses endless cells of the tape. However, I am not sure how I can use the number of states and what I should check. What confuses me is that entering an endless loop does not necessarily require the use of endless cells of the film.

$L_k=\{<M>| \,M\,\,\,is\,\,a\,\,TM\,\,that\,\,uses\,\,at\,\,most\,\,k\,\,tape\,\,cells\,\,\,when\,\,\,running\,\,\,on\,\,\,\epsilon\}$

prove that: $L^*=\bigcup\limits_{k\,\in\,\mathbb{N}} L_k\,\in\,\,\,RE\setminus R$

  • $\begingroup$ Is $k$ an absolute constant or is $L = \{ M : \exists k, M(\epsilon) \text{ uses at most $k$ tape cells} \}$? Do you just need to prove that there is a TM that accepts $L$? Or you want to decide $L$? $\endgroup$
    – Steven
    Jun 19, 2020 at 1:15
  • $\begingroup$ I updated what I wrote, I hope it's clear now $\endgroup$
    – Ella
    Jun 19, 2020 at 5:02

1 Answer 1


The language $L^*$ consists of all Turing machines $M$ which either eventually halt or repeat a configuration. For each machine $M$, by simulating the machine you can easily observe that one of these possibilities has happened.

  • $\begingroup$ using infinite number of tape cells not considered an endless loop? $\endgroup$
    – Ella
    Jun 19, 2020 at 7:35
  • $\begingroup$ Thanks, changed to "repeat a configuration". $\endgroup$ Jun 19, 2020 at 7:38
  • $\begingroup$ Is it always true that once a configuration is repeated, the Turing machine necessarily uses a finite number of cells? $\endgroup$
    – Ella
    Jun 19, 2020 at 7:42
  • $\begingroup$ Yes. I'll let you figure out why. $\endgroup$ Jun 19, 2020 at 7:43

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.