Let S be the set of total functions from $N \rightarrow M$, such that for each $f \in S$, there is $i > 1$ such that for all $j < i$, $f(i)$ and $f(j)$ are not equivalent Turing machines. Prove or disprove that S is countable

I don't think this is actually countable, but I'm having a hard tie proving this using diagonilzation. Can anyone give me pointers / hint? Preferably explained at a lower level.


Hint: Let $M_1,M_2$ be an arbitrary pair of inequivalent Turing machines. Your set $S$ contains all functions satisfying $f(1) = M_1$ and $f(2) = M_2$.

  • $\begingroup$ Not sure I understand here. Would you mind expanding a bit? I'm only in an introductory course, so I'm not sure whether I'm reading this correctly or not.... You're saying since we can let i = 2, and j = 1 and j < i by the question's statement the set contians all of these and so it is countable? Just no infinitely countable? $\endgroup$ Dec 14 '17 at 19:14
  • $\begingroup$ It's just a hint. You'll have to work out the rest. $\endgroup$ Dec 14 '17 at 19:23
  • $\begingroup$ I understand I'll have to work out the rest..... I'm trying to make sure I understand you rhint. The hint does little good if I don't understand / misinterpret your answer. $\endgroup$ Dec 14 '17 at 19:25
  • $\begingroup$ The only way to learn is to solve exercises. I've given you a start. $\endgroup$ Dec 14 '17 at 19:28
  • $\begingroup$ Okay. Here's my attempt. Wondering if I've done anything glaringly wrong. Let $M_1$ and $M_2$ be an arbitrary pair of inequivalent Turing achines. Note that by definiton of S we have that $S$ contains all functions satisfying $f(1) = M_1 $ and $f(2) = M_2$. Suppose $S$ is countable. Then there exists an exhaustive list of these functions: $f_0, f_1, .... $. Consider $g: N \rightarrow M$ defined by $g(x)=f_x((x+1)mod 2 + 1) $. (I made f(1) -> f(2) and f(2) -> f(1)). By definition we have that $g(x) \ne f_x(x)$ for all $x$ and so $S$ cannot be countable. $\endgroup$ Dec 14 '17 at 21:08

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.