Enumerator (computer science): Difference between revisions

Revision as of 14:49, 27 August 2022

Revision as of 11:42, 18 October 2022

Line 2:

{{One source|date=May 2021}}

An '''enumerator''' is ana [[AutomataTuring theory|automatonmachine]] thatwith lists,an possiblyattached withprinter. repetitions,The elementsTuring ofmachine somecan [[Setuse (mathematics)|set]]that {{mvar|S}},printer whichas itan isoutput saiddevice to ''enumerate''print strings. AEvery settime enumeratedthe byTuring somemachine enumeratorwants isto saidadd a string to bethe [[recursivelylist, enumerable]]it sends the string to the printer. AnEnumerator enumeratoris a type of Turing machine variant and is equivalent towith a [[Turing machine]].

==Formal definition==

{{Unreferenced section|date=April 2021}}

An enumerator <math>E</math> can be defined as a 2-tape Turing machine ([[Multitape Turing machine]] where <math> k=2 </math>) whose language is <math>\empty</math>. Initially, <math>E</math> receives no input, and all the tapes are blank (i.e., filled with blank symbols). Newly defined symbol <math>\#\in \Gamma\land\#\notin \Sigma</math> is the delimiter that marks end of an element of <math>S</math>. The second tape can be regarded as the printer, strings on it are separated by <math>\#</math>. The language of enumerator <math>E</math> denoted by <math>L(E)</math> is defined as set of the strings on the second tape (the printer).

An enumerator <math>E</math> is usually represented as a 2-tape [[Turing machine]]. One working tape, and one print tape. It can be defined by a 7-tuple, following the notation of a [[Turing machine]]:

<math>E = \langle Q, \Sigma, \Gamma, \delta, q_0, q_{print}, q_{reject}\rangle</math>

where

* <math>Q</math> is a finite, non-empty set of ''states''.

* <math>\Sigma</math> is a finite, non-empty set of the ''output / print alphabet''

* <math>\Gamma</math> is a finite, non-empty set of the ''working tape alphabet''

* <math>\delta</math> is the transition function. <math>\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\} \times \Sigma_\epsilon</math>

* <math>q_0 \in Q</math> is the start state

* <math>q_{print} \in Q</math> is the print state.

* <math>q_{reject}</math> is the reject state with <math>q_{print} \neq q_{reject}</math>

==Equivalence of Enumerator and Turing Machines==