0

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 Answers1

0

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)

  • Or, I suppose, one would talk about bijections if one finds the argument that one exists so simple that they don't think it's worth explicitly learning another way to justify things. –  Aug 12 '17 at 08:01
  • @Get_u Showing that a set injects into a countable set will do. In this case, one such injection takes TMs to the [lexicographically earliest, if you want to be really sure it's well-defined] strings which describe them in some fixed encoding. – Patrick Stevens Aug 12 '17 at 08:25
  • @Get_u: Yes, in the sense that "X is countably infinite" literally means "there is a bijective map between X and the natural numbers". No, in the sense that one often proves a set countable in the way I describe in my answer rather than messing around with bijections. –  Aug 12 '17 at 09:00