2 added 297 characters in body edited Jun 1 at 15:49 Yuval Filmus 211k1616 gold badges204204 silver badges374374 bronze badges This answer assumes that $$T(w)$$ is the set of inputs that the Turing machine $$M_w$$ halts on. Given a Turing machine $$M$$, construct a new Turing machine which runs $$M$$ in parallel on all inputs. Once $$M$$ has halted on 42 different inputs, halt. (If this never happens, the new machine will never halt.) In order to run $$M$$ on infinitely many inputs, you do the following: Start with some enumeration $$x_1,x_2,\ldots$$ of all inputs. Run $$M$$ for one step on $$x_1$$. Run $$M$$ for one step on $$x_1,x_2$$. Run $$M$$ for one step on $$x_1,x_2,x_3$$. And so on. This is known as dovetailing. The argument above reduces $$L$$ to the halting problem, and so shows that $$L$$ is r.e. We can also reduce the halting problem to $$L$$, hence showing that $$L$$ is r.e.-complete. To do this, suppose that we are given a Turing machine $$M$$ as input to $$H_0$$. We construct a new Turing machine which: On input $$\epsilon$$, transfers control to $$M$$. On input $$0,00,\ldots,0^{41}$$, halts. On all other inputs, doesn't halt. On input $$\epsilon$$, transfers control to $$M$$. On input $$0,00,\ldots,0^{41}$$, halts. On all other inputs, doesn't halt. The new machine belongs to $$L$$ iff the original one belongs to $$H_0$$. This answer assumes that $$T(w)$$ is the set of inputs that the Turing machine $$M_w$$ halts on. Given a Turing machine $$M$$, construct a new Turing machine which runs $$M$$ in parallel on all inputs. Once $$M$$ has halted on 42 different inputs, halt. (If this never happens, the new machine will never halt.) The argument above reduces $$L$$ to the halting problem, and so shows that $$L$$ is r.e. We can also reduce the halting problem to $$L$$, hence showing that $$L$$ is r.e.-complete. To do this, suppose that we are given a Turing machine $$M$$ as input to $$H_0$$. We construct a new Turing machine which: On input $$\epsilon$$, transfers control to $$M$$. On input $$0,00,\ldots,0^{41}$$, halts. On all other inputs, doesn't halt. The new machine belongs to $$L$$ iff the original one belongs to $$H_0$$. This answer assumes that $$T(w)$$ is the set of inputs that the Turing machine $$M_w$$ halts on. Given a Turing machine $$M$$, construct a new Turing machine which runs $$M$$ in parallel on all inputs. Once $$M$$ has halted on 42 different inputs, halt. (If this never happens, the new machine will never halt.) In order to run $$M$$ on infinitely many inputs, you do the following: Start with some enumeration $$x_1,x_2,\ldots$$ of all inputs. Run $$M$$ for one step on $$x_1$$. Run $$M$$ for one step on $$x_1,x_2$$. Run $$M$$ for one step on $$x_1,x_2,x_3$$. And so on. This is known as dovetailing. The argument above reduces $$L$$ to the halting problem, and so shows that $$L$$ is r.e. We can also reduce the halting problem to $$L$$, hence showing that $$L$$ is r.e.-complete. To do this, suppose that we are given a Turing machine $$M$$ as input to $$H_0$$. We construct a new Turing machine which: On input $$\epsilon$$, transfers control to $$M$$. On input $$0,00,\ldots,0^{41}$$, halts. On all other inputs, doesn't halt. The new machine belongs to $$L$$ iff the original one belongs to $$H_0$$. 1 answered Jun 1 at 15:11 Yuval Filmus 211k1616 gold badges204204 silver badges374374 bronze badges This answer assumes that $$T(w)$$ is the set of inputs that the Turing machine $$M_w$$ halts on. Given a Turing machine $$M$$, construct a new Turing machine which runs $$M$$ in parallel on all inputs. Once $$M$$ has halted on 42 different inputs, halt. (If this never happens, the new machine will never halt.) The argument above reduces $$L$$ to the halting problem, and so shows that $$L$$ is r.e. We can also reduce the halting problem to $$L$$, hence showing that $$L$$ is r.e.-complete. To do this, suppose that we are given a Turing machine $$M$$ as input to $$H_0$$. We construct a new Turing machine which: On input $$\epsilon$$, transfers control to $$M$$. On input $$0,00,\ldots,0^{41}$$, halts. On all other inputs, doesn't halt. The new machine belongs to $$L$$ iff the original one belongs to $$H_0$$.