588 views
1 votes
1 votes
Can someone explain in details how set of all TM is countable?

3 Answers

Best answer
4 votes
4 votes

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.

 

selected by
0 votes
0 votes
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.
0 votes
0 votes

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.

 

Related questions

0 votes
0 votes
0 answers
1
srestha asked Apr 13, 2019
282 views
$1)L=M$ is a turing machine $M$ accepts two strings of different length $2)L=M$ is a turing machine $M$ accepts atleast two strings of different length Which one RE? Whic...
0 votes
0 votes
1 answer
3
1 votes
1 votes
0 answers
4
iarnav asked Oct 17, 2017
680 views
I have read that T.M does not accept ε , but then in questions I have read T.M taking input ε ?Well, if T.M can't accept ε then why we are giving T.M the input ε ?Th...