-1
$\begingroup$

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 !

$\endgroup$
5
  • 1
    $\begingroup$ Ok but, what is the definition of ALL_TM in this context? $\endgroup$ Commented Aug 20, 2020 at 20:35
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Aug 20, 2020 at 21:33
  • 1
    $\begingroup$ What is invalid TM? $\endgroup$
    – Evil
    Commented Aug 20, 2020 at 22:12
  • 1
    $\begingroup$ Probably because the definition is different: cs.stackexchange.com/questions/11411/… $\endgroup$
    – user114966
    Commented Aug 20, 2020 at 22:28
  • $\begingroup$ 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. $\endgroup$ Commented Aug 21, 2020 at 0:11

1 Answer 1

-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.