The Set of All Turing Machines is Countable vs the set of all infinite binary sequences is uncountable
<p>Trying to study for the final and got so confused with countability.</p>

<p>I understand any turing machine can be described as a string. We have a finite number of inputs (Σ). We can calculate the string combinations for each length. </p>

<p>Say there are 256 different input symbols. </p>

<p>For the string length of 1: 256 combinations. </p>

<p>For the string length of 2: we have 256^2 combinations.</p>

<p>For the string length of k, we have 256^k combinations.</p>

<p>Then we number all these combinations. </p>

<p>1, 2 ... 256,
257, 258 ... 256 + 256^2 ...</p>

<p>Since natural numbers are countable, there's a bijective mapping. So the set of all turing machines is countable.</p>

<p>My question is why couldn't I do the same for all infinite binary sequences? I find all the combinations for each length, number them, then I will get a bijective mapping.</p>

<p>Many thanks!</p>