Let $A$ be the language consisting of descriptions of Turing machines $\{M_1, M_2, \dots \}$, where each $M_i$ is a decider. Prove that $A$ is not Turing-recognizable.

Then suppose $A$ is Turing-recognizable and suppose $s = \{s_1, s_2, \dots \}$ is a set of all possible binary strings. Then I construct decider $D$ as follows. On input $w$, if $w$ is not equal to binary string, then reject. Else, $w$ is a binary string that is equal to $s_i$ for some $i$. Use the enumerator $E$ to print the $i$-th output which is $M_i$. If $M_i$ accepts $s_i$, $D$ is going to reject $s_i$. Otherwise, accept $s_i$.

But in the last step, what happens when $M_i$ doesn't have defined transition over the alphabet $\{0,1\}$? Does $M_i$ immediately enter a reject state? What should I argue?

  • $\begingroup$ The set of decidable languages is countably infinite. $\endgroup$ – Yuval Filmus Nov 24 '17 at 23:12
  • $\begingroup$ I'm not sure what you mean by "$M_i$ doesn't have defined transition". Turing machines, as usually defined, always have "defined transition". If you use another definition, it's up to you to define its semantics. $\endgroup$ – Yuval Filmus Nov 24 '17 at 23:13
  • $\begingroup$ @YuvalFilmus Sorry about the confusion. I edited the title and some stuff. About undefined transition, I was talking about what if the tape alphabet of M_i doesn't have 0 and 1? In the argument, for decider D, I immediately reject an input string w if it's not binary string. Otherwise, I enumerate to find M_i and feed it a binary string input w, but I didn't make any assumptions about tape alphabets of deciders in A $\endgroup$ – Ted Nov 24 '17 at 23:23
  • $\begingroup$ Since your goal is to show that your machine is not part of the list, and your machine operates on binary strings, then you don't really care about machines which have a different input alphabet. $\endgroup$ – Yuval Filmus Nov 24 '17 at 23:25
  • $\begingroup$ @Yuval Filmus Can you please elaborate? My machine is forced to enumerate a list of all possible deciders, not only the ones that have binary alphabets. $\endgroup$ – Ted Nov 24 '17 at 23:31

The basic idea of the proof is to come up with a Turing machine which doesn't belong to the enumeration, hence contradicting the claim that deciders can be enumerated. To this end, we use diagonalization – for each potential machine in the enumerate, we ensure that there is at least one input on which the diagonalizing machine has a different behavior.

If the diagonalizing machine $D$ has alphabet $\Sigma$, then we already know that any machine in the enumeration with a different alphabet cannot be $D$. Therefore $D$ doesn't care much about these machines. What $D$ has to ensure is that for every machine $M_i$ with alphabet $\Sigma$ there is an input $x_i$ such that $D(x_i) \neq M_i(x_i)$.


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.