Enumerator (computer science): Difference between revisions

Revision as of 14:49, 27 August 2022

Latest revision as of 14:21, 10 January 2025

(8 intermediate revisions by 7 users not shown)

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 enumerated by an 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==

Line 34 ⟶ 25:

'''An Enumerable Language is Turing Recognizable'''

It's very easy to construct a Turing Machine <math>M</math> that recognizes the enumerable language <math>L</math>. We can have two tapes. On one tape we take the input string and on the other tape, we run the enumerator to enumerate the strings in the language one after another. Once a string is printed in the second tape we compare it with the input in the first tape. If itsit's a match, then we accept the input, elseotherwise rejectwe continue. Note that if the string is not in the language, the turing machine will never halt, thus rejecting the string.

== References ==

{{refbegin}}

* {{cite book |last=Sipser |first=Michael |title=Introduction to the Theory of Computation - International Edition |year=2012 |publisher=Cengage Learning |isbn=978-1-133-18781-3}}

{{refend}}

[[Category: Computability theory]]

[[Category: Theory of computation]]

{{compucomp-sci-theory-stub}}