# proving existence of TM that accepts the next language

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\,\,\,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$$

• 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$? Jun 19 '20 at 1:15
• I updated what I wrote, I hope it's clear now
– 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.