0
$\begingroup$

This question already has an answer here:

Is the following language:

$\qquad\displaystyle L= \{\langle M\rangle \mid M \text{ is a TM }, |L(M)|>1\}$

Turing-decidable?

I think it isn't, because if a Turing machine T can decide L, then T can say if M stops or not (impossible this is the halting problem). So T accepts when M stops and accepts the string (with a length > 1) and refuses otherwise.

I want build a Turing machine S, based on T, that decide if M with an input w stops or not, but how I can build it? If T exists then also S exists, so the halting problem would be Turing-decidable (impossible).

I think L is only Turing-recognizable. Is my reasoning right?

$\endgroup$

marked as duplicate by Ran G., Luke Mathieson, David Richerby, Kaveh, Juho Jun 6 '15 at 20:30

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 4
    $\begingroup$ Just follow your idea and make it formal. See also our reference question which should give you some ideas. $\endgroup$ – Raphael Dec 8 '14 at 18:06
  • $\begingroup$ The answer follows immediately from Rice's theorem: the language is undecidable. $\endgroup$ – Rick Decker Dec 8 '14 at 20:04
  • $\begingroup$ See answer to almost the same question here. Voting to close as duplicate. $\endgroup$ – Ran G. Jun 3 '15 at 22:18