0
$\begingroup$

The universal Turing machine $U_{TM}$ is a TM that takes in as input an encoding of a TM and a string, then runs the TM on the string and does whatever the simulated TM does. The language of the universal TM is the set of all encodings of a TM/string pair as a string for which the TM accepts the string.

I have seen several different names for the language of the universal Turing machine. Michael Sipser refers to it as $A_{TM}$ (the acceptance language for Turing machines), while Hopcroft, Ullman, and Motwani call it $L_u$ (the universal language).

Is the a standardized term for the language of the universal Turing machine? I would understand if there might be many "universal Turing machines" that vary in their encoding schemes, so if the answer is "no, there is no general term for this" that would be good to know. I'm mostly asking because I'm teaching an introductory course in the theory of computation and have been using the term $A_{TM}$ for this without knowing if there is a better term to use.

Thanks!

Improve this question
$\endgroup$
2
  • $\begingroup$ Doesn't the fact that the two main textbooks use different notation already answer your question? $\endgroup$
    – David Richerby
    Commented Mar 1, 2018 at 23:17
  • $\begingroup$ @DavidRicherby I'm not sure about that. There are some mathematical concepts where there are many different, parallel, standard notations employed for similar concepts (for example, how many different ways are there to write out the "implies" connective?) Given that those textbooks were written decades apart, it's also possible there was a shift in the notation. $\endgroup$
    – templatetypedef
    Commented Mar 1, 2018 at 23:52

1 Answer 1

Reset to default
6
$\begingroup$

No, there is no general term for this.

Improve this answer
$\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.