-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 !

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

1 Answer 1

Reset to default
-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.

Improve this answer
$\endgroup$

Your Answer

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

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