How to show that there are countably many Turing machines?

1.2k Views Asked by At

There is a natural way to prove that there are countable many Turing machines. First we will encode the Turing machines with binary string and than by setting a bijection from set of all encodings of Turing machines to set Natural numbers , this will show that there countably infinite many Turing machines are there.

Claim : How to show that there are countably many Turing machines ?

I am looking for an alternate method to prove that there are countably infinite Turing machines . Is there a any other method by which I can prove the statement. What are the other methods to show that some set is countable other than setting a bijection.

1

There are 1 best solutions below

3
On BEST ANSWER

The "setting a bijection" part is just a nod to formality, not something you would actually do.

A better way to capture actual practice is to use these two theorems that encode basic intuition:

  • The set of (finite) strings over a (nonempty) countable alphabet is countably infinite
  • A subset of a countable set is countable

One would only talk about bijections if one were unsure how to rigorously justify the conclusion, and so they were appealing to the basics. (or if one was unsure whether their audience would be uncomfortable with the justification)