Proving or disproving a set of total functions is countable

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.

1 Answer

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

• 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? – Overflow2341313 Dec 14 '17 at 19:14
• It's just a hint. You'll have to work out the rest. – Yuval Filmus Dec 14 '17 at 19:23
• 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. – Overflow2341313 Dec 14 '17 at 19:25
• The only way to learn is to solve exercises. I've given you a start. – Yuval Filmus Dec 14 '17 at 19:28
• 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. – Overflow2341313 Dec 14 '17 at 21:08