Enumerador

Existem diversas definições alternativas para máquinas de Turing simples. Elas são chamadas de variantes do modelo de máquina de Turing e são equivalentes em poder com o modelo original, isto é, reconhecem a mesma classe de linguagens.

Um tipo de variante de máquina de Turing é denominada enumerador. Um enumerador é, em termos simples, uma máquina de Turing com uma impressora em anexo. A máquina usa esta impressora como um dispositivo de saída para imprimir cadeias. Toda vez que a máquina de Turing quer adicionar uma cadeia à lista, ela envia a cadeia para a impressora.

Descrição

Um esquema deste modelo é dado na figura abaixo.

Um enumerador E inicia com uma fita de entrada em branco. Se o enumerador não pára, ele pode imprimir uma lista infinita de cadeias. A linguagem enumerada por E é a coleção de todas as cadeias que ela em algum momento imprime. Além disso, E pode gerar as cadeias da linguagem em qualquer ordem, possivelmente com repetições.

A partir dos enumeradores, surgiu o termo linguagem recursivamente enumerável. Dizemos que uma linguagem é Turing-reconhecível se e somente se algum enumerador a enumera.

Prova

Para provar tal teorema, teremos que provar nos dois sentidos, a ida e a volta. Primeiro mostramos que se tiver um enumerador E que enumera a linguagem A, uma MT M reconhece A. A MT M funciona da seguinte maneira.

M = "Sobre a entrada w:

1. Rode E. Toda vez que E dá como saída uma cadeia, compare-a com w.

2. Se w em algum momento aparece na saída de E, aceite."

Podemos perceber que a M aceita aquelas cadeias que aparecem na lista de E, como queríamos demonstrar.

Agora, fazemos a outra direção. Se a MT M reconhece uma linguagem A, podemos construir o seguinte enumerador E para A. Digamos que s1, s2, s3,... é uma lista de todas as possíveis cadeias de um Σ* qualquer.

E = "Ignore a entrada.

1. Repita o seguinte para i = 1,2,3...

2. Rode M por i passos sobre cada entrada, s1, s2, ..., si.

3. Se quaisquer computações aceitam, imprima a sj correspondente."

Se M aceita uma cadeia específica s, em algum momento ela vai aparecer na lista gerada por E. Na verdade, ela vai aparecer na lista uma quantidade infinita de vezes porque M roda do início sobre cada cadeia para cada repetição do passo 1. Esse procedimento dá o efeito de se rodar M em paralelo sobre todas as possíveis cadeias de entrada.

Referências

• Michael Sipser. Introdução à Teoria da Computação. Tradução brasileira de "Introduction to the Theory of Computation" (PWS Publishing Company, 2nd edition, 2005), por Ruy de Queiroz, revisão Newton Vieira, Cengarle Learning, 2007 ISBN 978-85-221-0499-4.