An enumerator is defined as a 7-tuple: https://en.wikipedia.org/wiki/Enumerator_(computer_science)

A Deterministic Turing machine is defined as a 7-tuple: https://en.wikipedia.org/wiki/Turing_machine

How are these definitions different? Can a DTM M simulate an enumerator E, for part of its computation can it call an enumerator E as a subroutine and run it to some point then do something with its output etc?

I assume the answer is yes, you can do things like enum in normal programming with universal language / universal machine. Since DTM is usual definition of universal machine it can perform an enumeration-- just want to be sure, maybe I'm wrong and its a fundamentally different kind of machine?

  • $\begingroup$ As a general rule of thumb, please don't delete your question after you have already received an answer. Some people might consider that impolite here. Part of our mission is to build up an archive of high-quality questions and answers that will be useful not only to the poster, but also to others in the future who might have a similar question. When people respond, they might be responding with that mission in mind. If you delete your question after getting an answer, you prevent others from benefiting from the answer. $\endgroup$ – D.W. May 30 at 21:28
  • $\begingroup$ To others, if you see this happen to one of your answers and you would like to preserve your answer, you can flag the post for moderator attention. $\endgroup$ – D.W. May 30 at 21:28

Yes. A deterministic Turing machine can simulate another deterministic Turing machine (possibly only up to some point), and an Enumerator is a particular kind of deterministic Turing machine.

| cite | improve this answer | |

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.