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 '20 at 1:15
  • $\begingroup$ I updated what I wrote, I hope it's clear now $\endgroup$ – Ella Jun 19 '20 at 5:02

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 '20 at 7:35
  • $\begingroup$ Thanks, changed to "repeat a configuration". $\endgroup$ – Yuval Filmus Jun 19 '20 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 '20 at 7:42
  • $\begingroup$ Yes. I'll let you figure out why. $\endgroup$ – Yuval Filmus Jun 19 '20 at 7:43

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.