Skip to main content
added 174 characters in body
Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

You are presenting a heuristican argument, which in no way constitutesfalls short of being a proof. In particular, it is not clear why a Turing machine recognizing $L$ should know whether $M$ loops forever or not; indeed, it is not so clear what do you mean by know in this context.

Here is one way a proof could go. Suppose that $L$ were r.e. The language of Turing machines which do accept $010$ is also r.e. By running both machines in parallel, we can decide whether a given Turing machine accepts $010$, i.e., we could solve the halting problem, which we know is undecidable. Therefore $L$ cannot be r.e.

You are presenting a heuristic argument, which in no way constitutes a proof.

Here is one way a proof could go. Suppose that $L$ were r.e. The language of Turing machines which do accept $010$ is also r.e. By running both machines in parallel, we can decide whether a given Turing machine accepts $010$, i.e., we could solve the halting problem, which we know is undecidable. Therefore $L$ cannot be r.e.

You are presenting an argument which falls short of being a proof. In particular, it is not clear why a Turing machine recognizing $L$ should know whether $M$ loops forever or not; indeed, it is not so clear what do you mean by know in this context.

Here is one way a proof could go. Suppose that $L$ were r.e. The language of Turing machines which do accept $010$ is also r.e. By running both machines in parallel, we can decide whether a given Turing machine accepts $010$, i.e., we could solve the halting problem, which we know is undecidable. Therefore $L$ cannot be r.e.

Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

You are presenting a heuristic argument, which in no way constitutes a proof.

Here is one way a proof could go. Suppose that $L$ were r.e. The language of Turing machines which do accept $010$ is also r.e. By running both machines in parallel, we can decide whether a given Turing machine accepts $010$, i.e., we could solve the halting problem, which we know is undecidable. Therefore $L$ cannot be r.e.