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!

$\endgroup$
  • $\begingroup$ Doesn't the fact that the two main textbooks use different notation already answer your question? $\endgroup$ – David Richerby Mar 1 '18 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 Mar 1 '18 at 23:52
6
$\begingroup$

No, there is no general term for this.

$\endgroup$

Your Answer

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

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