2 added 297 characters in body
source | link

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:

  1. On input $\epsilon$, transfers control to $M$.
  2. On input $0,00,\ldots,0^{41}$, halts.
  3. 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:

  1. On input $\epsilon$, transfers control to $M$.
  2. On input $0,00,\ldots,0^{41}$, halts.
  3. 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
source | link

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:

  1. On input $\epsilon$, transfers control to $M$.
  2. On input $0,00,\ldots,0^{41}$, halts.
  3. On all other inputs, doesn't halt.

The new machine belongs to $L$ iff the original one belongs to $H_0$.