3
$\begingroup$

$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 .

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Under any reasonable encoding, $A$ is decidable, but in order to say anything more, you need to fix an encoding. $\endgroup$ – Yuval Filmus Jan 31 '15 at 22:41
  • 7
    $\begingroup$ Under one encoding, all strings are encodings of Turing machines. Under others, the encoding is so complicated that it is not even context-free. It depends on the encoding. If the question doesn't specify the encoding, the answer is: "it depends on the encoding". $\endgroup$ – Yuval Filmus Jan 31 '15 at 22:51
  • 1
    $\begingroup$ Enumerate all Turing machines. As the encoding of an arbitrary Turing machine, use the number of the machine denoted in unary. Every unary number is now the encoding of a Turing machine, by definition. So the language of the encodings is $1^*$ (or $1^+$). $\endgroup$ – reinierpost Jan 31 '15 at 22:58
  • 3
    $\begingroup$ The question does have an answer – it depends on the encoding. $\endgroup$ – Yuval Filmus Jan 31 '15 at 23:13
  • 1
    $\begingroup$ Well, may be you could add it as an answer. $\endgroup$ – PleaseHelp Jan 31 '15 at 23:19
3
$\begingroup$

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.

Improve this answer
$\endgroup$
0

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