# Does the set ALL_TM contain all Turing Machines?

ALL_TM = { TM | A valid TM }

This was a question on my exam.

As my choice of answer I went with yes, since the set of all Turing Machines is countable, ( you can produce a binary string for each and every new Turing Machine ) my take on the answer that yes it does contain all Turing machines. But apparently my answer was wrong so I am curious

why ?

Thanks in advance for anyone's answer !

• Ok but, what is the definition of ALL_TM in this context? Commented Aug 20, 2020 at 20:35
• Something is very weird about the current wording of this question. You define ALL_TM as the set of all Turing machines and then say you were marked incorrect for responding that it contains all Turing machines? And why is the countability relevant? I feel like we are still missing some information or context. Commented Aug 20, 2020 at 21:33
• What is invalid TM?
– Evil
Commented Aug 20, 2020 at 22:12
• Probably because the definition is different: cs.stackexchange.com/questions/11411/…
– user114966
Commented Aug 20, 2020 at 22:28
• You could be very picky and slightly reword the definition to be $ALL_{TM}=\{\langle M\rangle\mid \langle M\rangle$ is a valid TM description $\}$. Doing this is more the custom when dealing with problems like this and then the answer would then be "$ALL_{TM}$ is not a set of TMs, but rather a set of TM descriptions". As I said, this is a very picky quibble. A lot depends on what exactly you have for the definition of $ALL_{TM}$; as @Dmitry said, that customarily refers to an entirely different object. Commented Aug 21, 2020 at 0:11

## 1 Answer

It turned out that the set of ALL_TM = { | M accepts all strings }, the set wasn't specified on the exam and I have seen it within notes but it was in the formulation that I have stated above so that was a bit confusing !

Anyway the set of ALL_TM does not contain all TM's since it only contains TM's that accept all strings.