[Solved]: Language consisting of all Turing machine encodings

Problem Detail: 

$A=${$ ⟨M⟩$:$M$ $is$ $a$ $Turing$ $Machine$ }

What can be said about $A$ ? Specifically, is $A$ decidable,regular,CFL,CSL?

I would say $A$ is decidable since we can write an algorithm to check whether a string is a valid encoding of a Turing machine .

But, is $A$ Regular[or CFL or CSL] ?

Edit : Someone argued that he could make an encoding where all the possible strings(What would be the alphabet here?-same as the encoding I suppose) are valid encoding of a TM(since there is a one-to-one correspondence between two countable infinite sets), hence making $A$ regular .

Asked By : atulgangwar

Answered By : Yuval Filmus

The complexity of $A$ depends on the encoding used for Turing machines. It is easy to come up with an encoding in which every string encodes some Turing machine (there are lots of ways). In contrast, it is easy to come up with artificially "hard" encodings, say the $k$th Turing machine being encoded by $1^kb$, where $b=1$ iff the $k$th Turing machine halts on the empty input; under this encoding, $A$ is not decidable. Nevertheless, it seems intuitively clear that any reasonable encoding makes $A$ decidable, though it's hard to say anything more without knowing the exact encoding.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37818

 Ask a Question

 Download Related Notes/Documents