Trying to study for the final and got so confused with countability.
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.
Say there are 256 different input symbols.
For the string length of 1: 256 combinations.
For the string length of 2: we have 256^2 combinations.
For the string length of k, we have 256^k combinations.
Then we number all these combinations.
1, 2 ... 256, 257, 258 ... 256 + 256^2 ...
Since natural numbers are countable, there's a bijective mapping. So the set of all turing machines is countable.
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.
Many thanks!
It sounds like you are asking about Cantor's Diagonal Argument. Given a set of Infinite sequences, you can craft a sequence that is not in the set.
This is very similar to the argument that you can not count the irrational numbers. You will always be able to craft a number that is not in the set, given that the set is composed of numbers/strings/etc. that are of infinite length.
I think the biggest flaw in your argument is you say "I find all the combinations of each length" but this is impossible considering you allow for strings having up to infinite length.