0
$\begingroup$

I recently came across this language:

$L=\{<TM>| \text{TM accepts recursively enumerable languages}\}$

It was asked in the question to find out whether language L is decidable or undecidable.

As far as I could reason out, language L is the set of all recursive enumerable languages or set of all turing machines.

But I can't figure out whether this language is decidable or not.

Can anyone please help me out??

Thanks in advance!!

$\endgroup$
  • $\begingroup$ Well, if, as you say, $L$ is simply the language of all TM encodings, then what do you need to check in order to decide it? $\endgroup$ – dkaeae Dec 4 '18 at 9:10
  • $\begingroup$ cs.stackexchange.com/questions/37818/… $\endgroup$ – Sagnik Jan 22 at 6:26
2
$\begingroup$

Let us express $L$ slightly more precisely. $$ L=\{<TM>\; \mid \text{The language accepted by } TM \\ \text{ is a recursively enumerable language}\}$$

Since for any Turing machine $TM$, the language accepted by it is a recursively enumerable language by definition, that restriction clause for $TM$ does not have any effect at all. We have, as indicated by OP, $$L \text{ is the set of encodings of Turing machines.} $$

The question becomes "Whether the language of all Turing machines is decidable or undecidable or semi-decidable?" as in the title.

Now this question is really about how we encode all Turing machines (in some specified model). There are ways to encode them so that we could end up with undecidable or semi-decidable language. However, in most reasonable encodings of Turing machines of most common models such as the standard Turing machines described in Wikipedia, we can check whether a string encodes a Turing machine by an algorithm in finite time.

So the simplified answer is "$L$ is decidable". This is the generally accepted answer. It is especially suitable when the encoding of Turing machines is implied to be decidable such as in the book Introduction to the theory of computation by Michael Sipser. Or when a decidable encoding of Turing machines has been described explicitly and has been assumed to be the default such as in the book Introduction to automata theory languages and computation by John E. Hopcraft et. al.

(The complete answer would be "$L$ is decidable unless an unusual encoding of Turing machines is used", which sounds, however, pedantic and which is usually not a welcomed answer.)

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.