In computational theory, and talking about CFGs, Turing Machines, and so forth I haven't a satisfactory explanation or definition for what ATM means versus ALLTM or the same or similar uses with CFGs, etc. Does the single A stand for any, some, one, or all instances of the class whether it's a TM, a CFG, or anything else? Conversely, ETM and EQTM are obvious as to what they mean.

  • 3
    $\begingroup$ Those notations may not be fixed completely. Please edit the question to add a reference to the textbook you are using. $\endgroup$ – John L. Jun 9 '19 at 22:32
  • $\begingroup$ $ALL_{TM}$ usually means the set of turing machines which accept any input (that is, $L(M) = \Sigma^*$). $\endgroup$ – rici Jun 10 '19 at 2:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.