Enumerador (informática)

Un enumerador es una máquina de Turing con una impresora conectada. La máquina de Turing puede usar esa impresora como dispositivo de salida para imprimir cadenas de caracteres. Cada vez que la máquina de Turing desea agregar una cadena a la lista, la envía a la impresora. El enumerador es un tipo de variante de máquina de Turing y es equivalente a una máquina de Turing.

Un enumerador${\displaystyle E}$puede definirse como una máquina de Turing de 2 cintas ( Máquina de Turing de múltiples cintas donde${\displaystyle k=2}$) cuyo idioma es${\displaystyle \emptyset }$. Inicialmente,${\displaystyle E}$No recibe ninguna entrada y todas las cintas están en blanco (es decir, llenas de símbolos en blanco). Símbolo recién definido${\displaystyle \#\in \Gamma \land \#\notin \Sigma }$es el delimitador que marca el final de un elemento de${\displaystyle S}$. La segunda cinta puede considerarse como la impresora, las cadenas en ella están separadas por${\displaystyle \#}$El idioma enumerado por un enumerador${\displaystyle E}$denotado por${\displaystyle L(E)}$se define como el conjunto de cadenas en la segunda cinta (la impresora).

Un lenguaje sobre un alfabeto finito es Turing-reconocible si y solo si puede ser enumerado por un enumerador. Esto demuestra que los lenguajes Turing-reconocibles también son recursivamente enumerables.

Prueba

Un lenguaje reconocible por Turing puede ser enumerado por un enumerador.

Consideremos una máquina de Turing.${\displaystyle M}$y el idioma aceptado por él sea${\displaystyle L(M)}$Dado que el conjunto de todas las cadenas posibles sobre el alfabeto de entrada${\displaystyle \Sigma }$es decir, el cierre Kleene${\displaystyle \Sigma ^{*}}$es un conjunto contable , podemos enumerar las cadenas en él como${\displaystyle s_{1},s_{2},\dots ,s_{i},}$etc. Luego, el enumerador enumera el lenguaje.${\displaystyle L(M)}$seguirá los pasos:

1 para i = 1,2,3,... 2 carreras${\displaystyle M}$con cadenas de entrada${\displaystyle s_{1},s_{2},\dots ,s_{i}}$para${\displaystyle i}$- Paso 3 Si se acepta alguna cadena, entonces imprímala.

Ahora surge la pregunta de si cada cadena en el lenguaje${\displaystyle L(M)}$será impreso por el Enumerador que construimos. Para cualquier cadena${\displaystyle w}$en el idioma${\displaystyle L(M)}$la TM${\displaystyle M}$ejecutará un número finito de pasos (seamos${\displaystyle k}$para${\displaystyle w}$) para aceptarlo. Luego en el${\displaystyle k}$-º paso del Enumerador${\displaystyle w}$se imprimirá. Por lo tanto, el enumerador imprimirá cada cadena${\displaystyle M}$reconoce pero una sola cadena puede imprimirse varias veces.

Un lenguaje enumerable es reconocible por Turing.

Es muy fácil construir una máquina de Turing.${\displaystyle M}$que reconoce el lenguaje enumerable${\displaystyle L}$Podemos usar dos cintas. En una, tomamos la cadena de entrada y en la otra, ejecutamos el enumerador para enumerar las cadenas del lenguaje una tras otra. Una vez que se imprime una cadena en la segunda cinta, la comparamos con la entrada de la primera. Si coinciden, aceptamos la entrada; de lo contrario, continuamos. Cabe destacar que si la cadena no pertenece al lenguaje, la máquina de Turing nunca se detendrá, rechazando así la cadena.