Turing Machine Self Doubt

Question

Can someone explain in details how set of all TM is countable?

Comments

Countable means acceptable by TM and also has some pattern match, See 2019 question as an example

https://gateoverflow.in/302814/gate2019-34

Answer 1

Every TM can be encoded with 0's and 1's, i mean to say every TM can be represented by a unique Binary Number.

let ∑ = {0,1} then Set of all Binary strings = ∑*

We know that,  ∑* is countable. ==> Set of all TM's are countable.

 

Answer 2

A Turing machine always has a finite description.So there are finite number of states, transitions and tape symbols for each Turing machine.The set of all finite length strings is still countable, and the set of valid Turing machine string literals is a subset of all finite length strings.

Answer 3

1. TM is an encoding of (0,1). but every encoding of 0,1 is not Turing machine. There might be languages for which TM doesn't exists(which are not REL).

2. (0,1)* is countable (can be enumerated in increasing order of the size of string like epsilon, 0, 1 , 00, 01,10,11...)

3. As TM implies encoding in {0,1}, from point 2 as encoding in 0,1 is countable, set of TM is also countable.