1
$\begingroup$

My understanding is an "Enumerator" is a Turing Machine that: instead of taking an input string, then going through a series of transitions and "halting" or "not halting" on it, it does not accept any input string and it starts with a blank string and builds the final string according to the rules of the language

For example: if our language was L = { w | w is made up of 0^n1^n, where n >= 0 }

A normal Turing Machine would have a input tape and it would receive an input on that tape and this normal Turing Machine would go through a series of transitions to deduce whether this string belongs to the language or not

An enumerator, a variant of normal Turing Machine, would have 3 different tapes, an input tape + work tape + output tape. Since, we don't have any input we don't interact with input tape at all ( which means we can remove that tape if we want to ), the work tape is used as a temporary workspace for constructing strings - at the end when we finish constructing a string we may choose to copy the symbols from the work tape to output tape and adding a "#" symbol on the output tape at the end of the output tape which will act as a separator from the next string and we will then blank out the work tape, the output tape acts like a printer for string with '#' separating different strings

In an enumerator, to produce strings for the given language, we will start on a start state and then take the transition to write 'n' number of '0' on the work tape, then writing 'n' number of '1' on worktape ( using appropriate logic of crossing out / blank symbol for 'counting' ). Then once we are done with that we will go to a special state called the "enumeratored state" which will copy the symbols from the work tape to output tape ( again through a series of transitions ) and then blank out the work tape + add the separator symbol on the output tape

This will continue on forever for strings of all lengths unless we have designed to produce specific strings of this language

In a nutshell, enumerator just helps building strings according to a pattern whilst turing machines help to check if a certain strings adheres to a certain pattern

Which also gives rise to the theorem that: "A language is accepted by a Turing machine if and only if some enumerator enumerates it"

Is my understanding correct?

$\endgroup$
4
  • $\begingroup$ I suggest you read this page for some insight. $\endgroup$
    – Nathaniel
    Dec 23, 2022 at 7:07
  • $\begingroup$ @Nathaniel Just confirming, but after reading the wikipedia page - whatever i said in this post is correct, Am i right? $\endgroup$ Dec 23, 2022 at 7:31
  • $\begingroup$ @PratikHadawale What you said in the post are pretty good understanding. I would say they are correct if you rephrase them in formal terms. $\endgroup$
    – John L.
    Dec 23, 2022 at 12:02
  • $\begingroup$ The usage of "pattern" in the question might be misleading. The only "pattern" of a recursively-enumerable language (or "the description of language") is the algorithm (a.k.a a Turing machine) that produces/accepts the language (or an equivalent algorithm) in general. $\endgroup$
    – John L.
    Dec 23, 2022 at 12:08

1 Answer 1

1
$\begingroup$

Your idea of "an enumerator" is pretty good.

In fact, you have recovered the origin of the term "recursively enumerable" as explained in the textbook Introduction to the Theory of Computation by Michael Sipser.

ENUMERATORS

As we mentioned earlier, some people use the term recursively enumerable language for Turing-recognizable language. That term originates from a type of Turing machine variant called an enumerator. Loosely defined, an enumerator is a Turing machine with an attached printer. The Turing machine can use that printer as an output device to print strings. Every time the Turing machine wants to add a string to the list, it sends the string to the printer. Exercise 3.4 asks you to give a formal definition of an enumerator. The following figure depicts aschematic of this model. Schematic of an enumerator by Michael Spiser

Your theorem also appears in that book.

THEOREM 3.21

A language is Turing-recognizable if and only if some enumerator enumerates it.

$\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.