Maquina de Turing

Prévia do material em texto

Máquina de Turing
Apresentação
A construção de compiladores que traduzam linguagens de programação de alto nível para 
instruções de máquina possibilitou o desenvolvimento de softwares cada vez mais complexos. Isso 
se deve à facilidade de produzi-los por meio das abstrações e bibliotecas fornecidas por essas 
linguagens.
O processo de construção de um compilador começa com o software capaz de reconhecer uma 
linguagem de programação que tenha comandos e estruturas complexas e bem definidas. Tais 
softwares são frutos da pesquisa realizada no campo das linguagens formais mediante a 
categorização e desenvolvimento de reconhecedores para os diferentes tipos de linguagens. 
Nesta Unidade de Aprendizagem, você vai estudar um poderoso formalismo reconhecedor de 
linguagens: a máquina de Turing. Com ele, é possível reconhecer um conjunto mais abrangente de 
linguagens do que os reconhecidos pelos autômatos de pilha. Você vai conhecer também a 
definição e o funcionamento da máquina de Turing determinística, como esse formalismo pode ser 
usado para reconhecer linguagens, além de algumas modificações propostas sobre ele.
Bons estudos.
Ao final desta Unidade de Aprendizagem, você deve apresentar os seguintes aprendizados:
Definir a classe das máquinas de Turing determinísticas.•
Exemplificar a construção de máquinas de Turing como reconhecedora de linguagens.•
Introduzir variações para máquinas de Turing.•
Infográfico
A máquina de Turing é um poderoso formalismo de computação que foi proposto antes de 
existirem computadores. Além disso, seu uso é importante no estudo das linguagens formais, tendo 
em vista que uma máquina de Turing é o dispositivo reconhecedor da classe das linguagens 
enumeráveis recursivamente.
Neste Infográfico, foram sintetizadas diversas informações relevantes sobre esse formalismo, bem 
como um exemplo de máquina de Turing e de como ocorre o reconhecimento de uma palavra pela 
máquina.
Aponte a câmera para o 
código e acesse o link do 
conteúdo ou clique no 
código para acessar.
https://statics-marketplace.plataforma.grupoa.education/sagah/cb60759c-4f38-4420-9adb-7b0906cce1d3/fdb3e4b6-5508-414f-b860-ffd5a9c4641f.jpg
Conteúdo do Livro
O estudo das linguagens formais divide as linguagens existentes de acordo com uma 
taxonomia proposta por Chomsky e que, por isso, leva seu nome. Dentro dela, o tipo de linguagem 
mais abrangente e que contém todos os outros tipos de linguagens dentro dele é o conjunto das 
linguagens enumeráveis recursivamente. Portanto, um reconhecedor para esse tipo de linguagem 
consegue reconhecer todas as linguagens dessa taxonomia.
No capítulo Máquina de Turing, base teórica desta Unidade de Aprendizagem, você vai conhecer a 
máquina de Turing, que é um formalismo reconhecedor para linguagens enumeráveis 
recursivamente. Inicialmente, vamos discutir a versão determinística dela, definindo esse 
formalismo e o seu funcionamento. Em seguida, veremos como é utilizada como reconhecedor de 
linguagens, por meio de exemplos de construção de máquinas e de análise deles. Por fim, você vai 
identificar algumas mudanças que foram propostas sobre as máquinas de Turing determinística e o 
poder computacional dessas modificações comparadas com a máquina original.
Boa leitura.
LINGUAGENS 
FORMAIS E 
AUTÔMATOS
OBJETIVOS DE APRENDIZAGEM
 > Definir a classe das máquinas de Turing determinísticas.
 > Exemplificar a construção de máquinas de Turing como reconhecedora 
de linguagens.
 > Introduzir variações para máquinas de Turing.
Introdução
O estudo dos problemas que podem ou não ser computados é o cerne da 
ciência da computação. Esse estudo surgiu há milhares de anos, mas, no início 
do século XX, houve um esforço maior em definir o conceito de computável. 
O matemático Alan Turing revolucionou essa área do conhecimento ao propor 
um formalismo de computação na forma de uma máquina e ao definir o conceito 
de efetivamente computável como um programa escrito para essa máquina. 
Esse formalismo, chamado de máquina de Turing, tornou-se um dos modelos 
mais estudados da teoria da computação (MENEZES, 2011).
Neste capítulo, vamos estudar o formalismo da máquina de Turing aplicado 
ao estudo das linguagens formais. Inicialmente, vamos explicar o funcionamento 
de uma máquina de Turing e como ela pode ser utilizada para reconhecer 
linguagens. Na sequência, descreveremos, utilizando exemplos práticos, quais 
são as linguagens que uma “máquina de Turing” é capaz de reconhecer. Por fim, 
serão apresentadas algumas modificações que foram propostas sobre esse 
formalismo na tentativa de aumentar seu poder computacional.
Máquina de Turing
Lucas Rafael Costella Pessutto
Conceitos fundamentais
A máquina de Turing é um formalismo computacional proposto pelo ma-
temático Alan Turing em 1936. Apesar de ter sido proposto 20 anos antes 
do surgimento do primeiro computador digital, esse formalismo pode ser 
considerado um modelo preciso de computador de propósito genérico, pois 
uma máquina de Turing pode solucionar todos os problemas que podem ser 
resolvidos por um computador real (DIVERIO; MENEZES, 2011; SIPSER, 2013). 
Turing concebeu esse formalismo genérico de computação imaginando 
uma pessoa, que dispõe de instrumentos para escrever e apagar, realizando 
cálculos em um papel quadriculado. Sua atividade pode ser descrita como 
uma sequência finita de ações. As ações possíveis que essa pessoa pode 
assumir incluem: ler um símbolo de um quadrado, escrever um símbolo em 
um quadrado e mover sua atenção para outro quadrado do papel (MENEZES, 
2011). Essa concepção inicial foi formalizada como uma máquina composta 
pelos três elementos listados a seguir (DIVERIO; MENEZES, 2011).
1. Fita: corresponde ao papel quadriculado. Porém, no formalismo pro-
posto por Turing, ela é unidimensional e infinita. É utilizada como um 
dispositivo de entrada, saída e memória de trabalho.
2. Unidade de controle: é responsável por refletir o estado atual da má-
quina. Também chamada de “cabeça da fita”, é responsável por apontar 
para uma única célula da fita, bem como por realizar a leitura e a 
gravação de dados nela. Além disso, a cabeça da fita pode mover-se 
para a esquerda ou para a direita. Esse elemento da máquina de Turing 
corresponde ao estado mental da pessoa realizando os cálculos na 
concepção inicial de Turing.
3. Programa: sequência de ações (leituras e gravações na fita e movimen-
tação da cabeça da fita) que serão executadas pela máquina. Também 
chamado de “função de transição”, esse componente corresponde às 
ações tomadas pela pessoa durante a computação dos valores no papel.
Conforme mencionado, considera-se a fita como tendo espaço infinito. 
Inicialmente, ela se encontra preenchida com a palavra que será processada. 
As demais células conterão um símbolo especial, chamado de “branco”. Uti-
lizaremos o caractere □ para denotar o símbolo de branco. Além do símbolo 
de branco, em cada célula da fita, é permitido armazenar os símbolos do 
alfabeto. Também assumimos que a cabeça da fita inicia o processamento 
Máquina de Turing2
apontando para a primeira célula que contém a palavra de entrada. A Figura 1 
contém um esquema representativo da fita e de sua cabeça.
Figura 1. A fita e a cabeça de uma máquina de Turing em seu estado inicial.
Fonte: Adaptada de Sipser (2013).
O programa da máquina de Turing possui um conjunto finito de estados 
possíveis. Cada instrução desse programa contém a informação que deve 
ser lida da fita, qual símbolo deve ser escrito na fita (tanto a leitura quanto 
a escrita serão feitas na mesma célula) e a direção em que a cabeça se mo-
verá ao final da instrução, que poderá ser para a direita, para a esquerda ou 
permanecer parada (MENEZES, 2011). A máquina processará instruções até 
que um estado final seja atingido. Caso isso aconteça, a entrada será ACEITA. 
Se, em algum momento durante o processamento, não existir qualquer ins-
trução possível que a máquina possa executar, ela produzirá o estado REJEITA 
para essaentrada. Há, ainda, a possibilidade de a máquina nunca produzir 
uma saída, entrando em um estado de loop infinito (SIPSER, 2013).
A definição formal de uma máquina de Turing, conforme apresentado em 
Hopcroft, Motwani e Ullman (2001), consiste em uma 7-upla:
M = {Q, Σ, Γ, δ, q0, B, F},
onde:
 � Q é o conjunto finito de estados da máquina;
 � Σ é o alfabeto da entrada, conjunto finito que não pode conter o sím-
bolo branco;
 � Γ é o conjunto completo de símbolos da fita, sendo que Σ ⊂ Γ e □ ∈ Γ;
 � δ é a função de transição, que é uma função parcial cujos argumentos 
δ(q, X) correspondem a um estado q e a um símbolo da fita X. Caso a 
transição esteja definida, é produzida uma tripla (p, Y, S), onde p é o 
próximo estado da máquina, Y é um símbolo que pertence a Γ e que 
será escrito na célula corrente da fita e S é a direção em que a cabeça 
Máquina de Turing 3
da máquina se moverá (utilizamos L para indicar movimento à esquerda 
e R para indicar movimento à direita);
 � q0 é o estado inicial da máquina, sendo que q0 ∈ Q;
 � B é o símbolo de branco (□) — lembre-se de que □ ∉ Σ e □ ∈ Γ;
 � F é o conjunto de estados finais, sendo F ⊆ Q.
Podemos representar a função de transição de uma máquina de Turing de 
forma gráfica, por meio de um grafo dirigido, conforme ilustrado na Figura 2. 
Nela, é representada a função de transição genérica δ(q, X) → (p, Y, S). Veremos 
exemplos de máquinas completas nas próximas seções.
Figura 2. Representação gráfica da função de transição de 
uma máquina de Turing.
Fonte: Adaptada de Menezes (2011).
A Figura 3, por sua vez, apresenta como identificaremos o estado inicial e 
os estados finais de uma máquina de Turing. Essa notação será adotada em 
todos os exemplos deste capítulo.
Figura 3. Representação gráfica do estado inicial (esquerda) 
e do estado final (direita) de uma máquina de Turing.
Máquina de Turing4
Outra forma de representar uma máquina de Turing é utilizando uma 
notação tabular. Para isso, colocamos cada estado da máquina em uma linha 
e todos os símbolos de Γ nas colunas. As células da tabela serão preenchidas 
com as triplas (próximo estado, símbolo escrito, direção). Veja, no Quadro 1, 
como a função de transição genérica δ(q, X) → (p, Y, S) é representada na 
forma tabular.
Quadro 1. Representação de uma máquina de Turing na forma tabular
Estado
Γ
... X Y ... □
p — — — — —
q — (p, Y, S) — — —
Vejamos, agora, um exemplo de máquina de Turing. Considere a linguagem 
A = {anbn | n > 0}, que consiste em todas as palavras pertencentes ao alfa-
beto {a, b} e que possuem mesmo número de símbolos a e b. São exemplos 
de palavras aceitas por essa linguagem {ab, aabb, aaabbb, ...}. Podemos 
projetar uma máquina de Turing que reconheça essa linguagem. Assumimos 
que a palavra de entrada se encontrará na fita no início do processamento. 
Devemos percorrer a fita procurando um símbolo a e seu correspondente b, 
substituindo cada símbolo por outro caractere auxiliar, por exemplo, por 0 
e 1, respectivamente. Se, ao final da computação, não restarem símbolos a 
ou b na fita, a palavra de entrada é aceita. Caso contrário, ela é rejeitada. 
A máquina de Turing descrita pode ser formalmente definida como:
M1 = 〈{q0, q1, q2, q3, q4}, {a, b}, {a, b, 0, 1, □}, δ, q0, □, {q4}〉
A função de transição de M1 está descrita, de forma tabular, no Quadro 2.
Quadro 2. Função de transição da máquina de Turing M1
Estado
Γ
a b 0 1 □
q0 (q1, 0, R) — — (q3, 1, R) —
q1 (q1, a, R) (q2, 1, L) — (q1, 1, R) —
(Continua)
Máquina de Turing 5
Estado
Γ
a b 0 1 □
q2 (q2, a, L) — (q0, 0, R) (q2, 1, L) —
q3 — — — (q3, 1, R) (q4, □, R)
q4 — — — — —
A Figura 4 contém a representação gráfica da máquina de Turing M1.
Figura 4. Representação gráfica da máquina de Turing M1.
Fonte: Adaptada de Hopcroft, Motwani e Ullman (2001).
Dada uma máquina de Turing M, definimos o conjunto das palavras que 
pertencem a Σ* e são aceitas por M como ACEITA(M). Similarmente, podemos 
definir outros dois conjuntos das linguagens que são rejeitas (REJEITA[M]) e 
das linguagens que fazem a máquina entrar em loop (LOOP [M]) (MENEZES, 
2011). São propriedades desses conjuntos, conforme Menezes (2011):
 � ACEITA(M) ∪ REJEITA(M) ∪ LOOP(M) = Σ*;
 � ACEITA(M) ∩ REJEITA(M) = ∅;
 � ACEITA(M) ∩ LOOP(M) = ∅;
 � REJEITA(M) ∩ LOOP(M) = ∅.
(Continuação)
Máquina de Turing6
Linguagens com máquinas de Turing
Alonzo Church postulou, em 1936, a Hipótese de Church, segundo a qual 
qualquer função computável pode ser processada por uma máquina de Tu-
ring. Ela é chamada de “hipótese” porque não pode ser matematicamente 
provada. Apesar disso, nenhum outro formalismo computacional possui poder 
computacional maior do que uma máquina de Turing, atingindo, no máximo, 
a mesma capacidade computacional que ela (MENEZES, 2011).
Pela implicação da tese de Church, costumamos assumir que a máquina 
de Turing é o dispositivo de computação mais genérico; ou seja, toda a função 
que é computável pode ser representada utilizando-se o formalismo da má-
quina de Turing. Por analogia, podemos dizer que toda linguagem que pode 
ser reconhecida mecanicamente (compilada) é reconhecida por uma máquina 
de Turing (DIVERIO; MENEZES, 2011).
De acordo com a hierarquia de Chomsky, a classe das linguagens reco-
nhecidas por uma máquina de Turing é denominada linguagens enumeráveis 
recursivamente ou, ainda, linguagem tipo 0. Essa categoria de linguagens está 
no nível mais alto da hierarquia, conforme mostra a Figura 5. Portanto, uma 
máquina de Turing é capaz de reconhecer também as linguagens dos tipos 1, 2 
e 3. Na sequência, serão apresentados alguns exemplos de máquinas de Turing 
para reconhecer linguagens de cada um dos tipos da hierarquia de Chomsky.
Figura 5. Hierarquia de Linguagens segundo Chomsky.
Fonte: Menezes (2011, p. 238).
Máquina de Turing 7
Reconhecimento de linguagens regulares (tipo 3)
Linguagens regulares são aquelas capazes de serem representadas por um 
autômato finito determinístico. Elas também podem ser expressas por meio 
de expressões regulares ou de gramáticas regulares. Um exemplo desse tipo 
de linguagem é L1 = {w | w ∈ {a, b}* e w inicie com a e termine com b}. Vejamos 
como pode ser projetada uma máquina de Turing para essa linguagem. 
A Figura 6 contém a representação gráfica dessa máquina. Ela pode ser 
representada formalmente por:
M1 = 〈{q0, q1, q2, q3}, {a, b}, {a, b, □}, δ, q0, □, {q3}〉
Figura 6. Máquina de Turing que reconhece a linguagem regular L1.
A partir do estado inicial (q0), só poderemos atingir o estado seguinte (q1) 
caso haja um símbolo a na primeira posição da fita. Caso contrário, a palavra 
de entrada será rejeitada. Na sequência, o restante da palavra será percorrido 
e a máquina iterará entre os estados q1 e q2, dependendo do valor lido na 
fita. A leitura de um valor a levará a máquina para o estado q1, e a leitura do 
símbolo b fará a máquina transitar para o estado q2. Quando atingir o primeiro 
símbolo branco da fita, a máquina transitará para o estado q3 se, e somente 
se, ela estiver no estado q2, ou seja, se ela anteriormente tiver lido um símbolo 
b. Caso esteja em outro estado, a máquina rejeitará a palavra de entrada.
Perceba que a simplicidade da linguagem fez com que não usássemos 
todo o potencial da máquina de Turing. Não foi necessário utilizar um alfabeto 
auxiliar para modificar as informações contidas na fita, e somente percorremos 
a entrada no sentido esquerda-direita.
Máquina de Turing8
Reconhecimento de linguagens livres de contexto 
(tipo 2)
As linguagens livres de contexto são as linguagens que podem ser reconhecidas 
por um autômato de uma pilha. Esse tipo de linguagem pode ser expresso por 
meio de gramáticas livres de contexto e, por definição, contém o conjunto 
de todas as linguagens regulares. Vejamos como construir uma máquina de 
Turing para a linguagem livre de contexto L2 = {wwR | w é a palavra de {a, b}*}, 
onde wR significa a palavra w escrita de forma reversa. Ou seja, a linguagem 
L2 contém strings espelhadas,e a primeira metade da palavra está escrita 
de forma reversa na segunda metade da string de entrada. Por exemplo, 
a palavra “abba” pertence à L2, enquanto a palavra “aba” não pertence à L2. 
Definiremos M2 como a máquina de Turing que aceita a linguagem descrita:
M2 = 〈{q0, q1, q2, q3, q4, q5, q6, q7, q8}, {a, b}, {a, b, 1, 2, □}, δ, q0, □, {q8}〉
A função de transição que ilustra o comportamento de M2 pode ser vista 
na Figura 7. A partir do estado inicial da máquina (q0), é identificado o primeiro 
símbolo lido. Se esse símbolo for a, a máquina desviará para o estado q1; caso 
contrário, ela se moverá para o estado q4. Nesses estados, será percorrida 
a fita em busca de um símbolo de branco ou de um símbolo auxiliar de 1 ou 
2. O objetivo é encontrar o último símbolo da fita que ainda não tenha sido 
processado. Ao detectar esse símbolo, a máquina se move para o estado se-
guinte (q2 ou q5). Em seguida, checa-se se o último símbolo é igual ao primeiro: 
caso não seja, a palavra será rejeitada; caso contrário, a máquina avançará 
ao próximo estado (q3 ou q6). Esses estados serão responsáveis por retornar 
ao início da fita em busca do próximo símbolo não processado. Ao encontrar 
esse símbolo, a máquina retornará ao estado q0 e repetirá esse processo até 
que não haja mais símbolos não processados na fita.
Quando a máquina se encontrar no estado q0 e o símbolo atual já tiver sido 
processado (seu valor será um dos símbolos auxiliares 1 ou 2), significará que 
não há mais símbolos para serem processados no início da fita. A máquina 
passará, então, para o estado q7, que garantirá que não existem símbolos 
não processados no final da fita. Caso não houver e a cabeça da fita atingir 
um símbolo de branco, a máquina se moverá ao estado q8, e a palavra de 
entrada é aceita.
Máquina de Turing 9
Figura 7. Máquina de Turing que reconhece a linguagem livre de contexto L2.
Reconhecimento de linguagens enumeráveis 
recursivamente (tipo 0)
Por fim, apresentaremos um exemplo de uma máquina de Turing capaz de 
reconhecer uma linguagem enumerável recursivamente, que são as lingua-
gens que são reconhecidas somente por uma máquina de Turing (ou outro 
formalismo equivalente). Vejamos um exemplo de linguagem enumerável 
recursivamente, bem como sua respectiva máquina de Turing. 
Considere a linguagem L3 = {a2n|n ≥ 0}. Essa linguagem reconhece palavras 
cujo tamanho é uma potência de dois. A máquina de Turing M3 a seguir é capaz 
de reconhecer essa linguagem. A representação gráfica das transações da 
máquina pode ser vista na Figura 8.
M3 = 〈{q0, q1, q2, q3, q4, q5}, {a}, {a, 1, □}, δ, q0, □, {q5}〉
O algoritmo dessa máquina de Turing inicia substituindo o primeiro sím-
bolo a da fita pelo símbolo de branco; caso este seja o único símbolo na fita, 
a máquina aceita essa palavra, pois 20 = 1. Havendo mais símbolos na fita, 
a máquina entra no loop dos estados q2 e q3, onde símbolos a são alternada-
mente substituídos pelo símbolo auxiliar 1, até encontrar um símbolo branco, 
o que moverá a máquina para o estado q4, que moverá a cabeça da fita para a 
esquerda, até atingir um símbolo de branco, o que fará a máquina retornar ao 
estado q1. Nesse ponto, a máquina buscará por um símbolo a, o que a levará 
de volta ao loop dos estados q2 e q3. Se não houver mais símbolos a na fita, 
Máquina de Turing10
a linguagem é aceita. Perceba como, a cada iteração, metade dos símbolos a 
da fita é substituída (SIPSER, 2013).
Figura 8. Máquina de Turing que reconhece a linguagem enumerável recursivamente L3.
Variações das máquinas de Turing
O estudo das máquinas de Turing resultou na proposição de diversas modifi-
cações do modelo original proposto por Turing, com o objetivo de aumentar 
seu poder computacional. Apesar de nenhuma delas ter atingido seu objetivo, 
ou seja, não ter estendido o conjunto de linguagens aceitas pela máquina 
de Turing original, essas modificações foram importantes para facilitar o 
desenvolvimento de certos algoritmos, por terem mais flexibilidade do que 
o modelo original. Outro ponto destacado por Harel e Feldman (2004) é que 
esses modelos dão robustez à hipótese de Church, que, apesar de não poder 
ser provada, ganha respaldo no fato de que nenhuma extensão da máquina 
de Turing supera o poder computacional do modelo original. 
Menezes (2011) enumera algumas das principais modificações propostas 
para a máquina de Turing. A lista de modificações inclui:
 � o não determinismo, que ocorre quando a função de transição δ(q, X) 
leva a máquina para múltiplos estados em vez de um único;
 � o uso de múltiplas fitas;
Máquina de Turing 11
 � o uso de múltiplas cabeças de leitura;
 � o uso de uma fita multidimensional;
 � o uso de combinações dessas modificações. 
Para cada uma dessas modificações, existe uma prova de que o modelo 
original da máquina de Turing consegue simular seu comportamento. Neste 
capítulo, discutiremos, em detalhes, a máquina que possui múltiplas fitas e 
a máquina de Turing não determinística.
Máquina de Turing com múltiplas fitas
Esse modelo estendido de máquina de Turing assume que existem múltiplas 
fitas que poderão ser utilizadas para processar a palavra de entrada, cada 
uma delas com sua própria cabeça da fita, independente das demais. Assume-
-se que a entrada estará na primeira fita e que as demais se encontrarão 
preenchidas com o símbolo de branco (SIPSER, 2013). 
A função de transição δ é modificada para atender a múltiplas fitas, ficando 
δ(q, a1,..., ak) = (p, Y1,..., Yk, S1,..., Sk), onde k é o número de fitas da máquina 
e k > 1. Isso significa dizer que uma máquina que se encontre no estado q e 
leia os valores a1, ..., ak nas fitas 1 até k passará para o estado p, escreverá 
os valores Y1, ..., Yk em cada fita e moverá cada cabeça nas direções S1,..., Sk 
(SIPSER, 2013). A Figura 9 ilustra uma representação da máquina de Turing 
contendo múltiplas fitas.
Figura 9. Máquina de Turing com múltiplas fitas.
Fonte: Adaptada de Hopcroft, Motwani e Ullman (2001).
Máquina de Turing12
Podemos reproduzir o comportamento de uma máquina com múltiplas 
fitas em uma máquina de Turing de fita única. Para isso, armazenamos o 
conteúdo de todas as fitas em uma única, separando seu conteúdo por um 
novo símbolo auxiliar #, que não faz parte do alfabeto utilizado da máquina. 
Esse símbolo delimitará o conteúdo de cada fita. Além disso, será necessá-
rio manter a localização que cada cabeça da fita está ocupando. Para isso, 
o símbolo para o qual a cabeça da fita está apontando é reescrito, mas agora 
com um ponto sobre ele; por exemplo, o símbolo a passa a ser ȧ Também será 
necessário adicionar esses novos símbolos ao alfabeto da fita (SIPSER, 2013). 
Veja, na Figura 10, como ficaria a conversão de uma máquina com múltiplas 
fitas para uma máquina de uma única fita.
Figura 10. Conversão da máquina M com múltiplas fitas para a máquina S 
com uma única fita.
Fonte: Adaptada de Sipser (2013).
Vejamos um exemplo de máquina de Turing com múltiplas fitas para re-
conhecer a linguagem L = {anbncn | n ≥ 1}. Construiremos uma máquina com 
três fitas, que serão utilizadas como uma pilha, para contar o número de 
repetições de símbolos de cada tipo. Nesse exemplo, adicionaremos, ainda, 
outra extensão à máquina de Turing: permitir que a cabeça da fita permaneça 
parada, em vez de se mover para uma direção. Denotaremos como S esse 
movimento da cabeça da fita. 
Máquina de Turing 13
A Figura 11 contém a representação gráfica das transições dessa máquina. 
Perceba como, a cada transição, é lido um símbolo de cada fita, escrito um 
símbolo em cada uma das fitas e, por fim, cada cabeça da fita é movida para 
uma direção.
Figura 11. Máquina de Turing com múltiplas fitas.
Máquina de Turing não determinística
Uma máquina de Turing não determinística, conforme mencionado anterior-
mente, é aquela cuja função de transição permite múltiplos estados possíveis 
a partir de um estado q, lendo um símbolo X. Portanto, sua função de transição 
δ pode ser expressapor δ(q, X) = {(q1, Y1, D1), (q2, Y2, D2),..., (qk, Yk, Dk)}, sendo k 
um número inteiro finito (HOPCROFT; MOTWANI; ULLMAN, 2001).
A cada passo, a máquina não determinística escolhe uma das triplas para 
ser seu próximo movimento. Uma máquina de Turing não determinística 
aceitará uma palavra, caso haja uma sequência de escolhas de que conduza a 
um estado final de aceitação, e não aceitará, caso essa sequência não exista. 
Veja um exemplo de máquina de Turing não determinística na Figura 12.
Máquina de Turing14
Figura 12. Máquina de Turing não determinística.
Podemos enxergar as transições pela máquina como uma árvore, onde 
cada subárvore corresponde a uma escolha possível da máquina. Veja, por 
exemplo, o nodo q0 da máquina de Turing da Figura 12. Ao ler o símbolo a 
nesse estado, ocorrem três possiblidades: 
1. a máquina pode mover-se para a direita e manter-se nesse estado;
2. a máquina pode substituir o símbolo atual por X, mover a cabeça da 
fita para a direita e ir para o estado q1; 
3. a máquina pode substituir o símbolo a por Y, mover a cabeça da fita 
para a esquerda e direcionar a máquina ao estado q2.
O comportamento não determinístico da máquina pode ser simulado 
em uma máquina de Turing determinística. Basta, apenas, que a máquina 
determinística execute todas as possíveis ramificações de um estado. Caso 
a linguagem seja aceita por uma dessas ramificações, é, então, aceita; caso 
ela não seja reconhecida por nenhuma delas, então é rejeitada. Outro ponto 
importante destacado em Sipser (2013) é que essa expansão das ramificações 
possíveis de estados não determinísticos deve ser feita com busca em largura, 
em vez de com busca em profundidade. O motivo disso é que expandir uma 
única ramificação em profundidade pode levar a máquina a um estado de 
loop, o que faria a linguagem não ser aceita. Logo, o ideal é que todos os 
estados possíveis sejam expandidos gradativamente.
Máquina de Turing 15
Não apresentamos a prova completa da conversão de uma máquina 
não determinística em uma máquina determinística, apenas uma ideia 
geral de como isso pode ser feito. A prova completa pode ser vista em Sipser 
(2013). Leia o Teorema 3.16, que descreve essa transformação passo a passo.
Neste capítulo, descrevemos o funcionamento de uma máquina de Turing 
e explicamos como utilizar esse formalismo para reconhecer os diversos 
tipos de linguagem presentes na taxonomia de Chomsky. Além disso, foram 
vistas extensões propostas para esse modelo de computação e discutida, 
brevemente, a equivalência computacional dessas modificações com o modelo 
determinístico da máquina de Turing. Existem outros tópicos que você pode 
explorar em relação a esse conteúdo para aprofundar seu conhecimento. Por 
exemplo, como a máquina de Turing pode ser utilizada para computar funções 
e as provas completas da equivalência da máquina de Turing determinística 
com suas extensões. Você também pode se aprofundar no estudo da lin-
guagens recursivamente enumeráveis, identificando como esse conjunto de 
linguagens está organizado e que linguagens fazem parte dele.
Referências
DIVERIO, T. A.; MENEZES, P. B. Teoria da computação: máquinas universais e computabi-
lidade. 3. ed. Porto Alegre: Bookman, 2011. (Série Livros Didáticos Informática UFRGS, 5).
HAREL, D.; FELDMAN, Y. Algorithmics: the spirit of computing. 3rd ed. London: Pearson, 
2004.
HOPCROFT, J. E.; MOTWANI, R.; ULLMAN, J. D. Introduction to automata theory, languages, 
and computation. 2nd ed. London: Pearson, 2001.
MENEZES, P. B. Linguagens formais e autômatos. 6. ed. Porto Alegre: Bookman, 2011. 
(Série Livros Didáticos Informática UFRGS, 3).
SIPSER, M. Introduction to the theory of computation. 3rd ed. Boston: Cengage Learning, 
2013.
Máquina de Turing16
Dica do Professor
O projeto, a construção e os testes da função de transição de uma máquina de Turing podem ser 
executados em um computador, por meio de softwares que simulem seu funcionamento. Além de 
agilizar o processo de criação de máquinas, estes também permitem realizar a simulação de como 
uma entrada é tratada pela máquina de Turing, o que possibilita entender melhor seu 
funcionamento.
Nesta Dica do Professor, você vai aprender como criar máquinas de Turing utilizando o software 
JFLAP, uma das principais ferramentas de estudo de linguagens formais. Vai descobrir também 
como executar uma máquina de Turing para reconhecer entradas fornecidas pelo usuário.
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
https://fast.player.liquidplatform.com/pApiv2/embed/cee29914fad5b594d8f5918df1e801fd/3f01d7ea55fe3b4cf5b45a0e8704dd73
Exercícios
1) Uma das funções de uma máquina de Turing consiste em reconhecer linguagens. Isso quer 
dizer que ela é capaz de classificar palavras como pertencentes ou não a determinada linguagem.
Considere a máquina de Turing definida a seguir:
Qual das seguintes cadeias é rejeitada pela máquina acima?
A) aabbbaaaaa
B) abaa
C) aaaabaaaaa 
D) aabbaa
E) abbbbaaaaa
A função de transição de uma máquina de Turing é uma função parcial que mapeia um estado e um 
símbolo lido na posição atual da cabeça da fita em uma tripla que consiste no próximo estado, no 
símbolo que será escrito na fita e na direção em que a cabeça da fita se moverá.
Considere a máquina de Turing dada a seguir:
2) 
Com base no conteúdo da fita e no estado corrente da máquina, qual será o próximo estado 
alcançado? O que será escrito na posição para onde a cabeça da máquina está apontando?
A) Próximo estado: indefinido. A entrada será rejeitada.
B) Próximo estado: q4. Será escrito ’2’ na fita.
C) Próximo estado: q1. Será escrito ’1’ na fita.
D) Próximo estado: q4. Será escrito ’b’ na fita.
E) Próximo estado q7. Será escrito ’2’ na fita.
3) O estudo do que pode (ou não) ser computado é o cerne da ciência da computação. Apesar 
de ser bastante antigo, ele se desenvolveu principalmente na primeira metade do século XX 
e foi revolucionado quando Alan Turing propôs um formalismo genérico de 
computação capaz de representar qualquer problema computável.
Avalie as seguintes afirmações sobre a máquina de Turing e assinale a alternativa correta.
A) Uma máquina de Turing é capaz de reconhecer qualquer linguagem que se enquadre na 
taxonomia de Chomsky.
B) Em uma máquina de Turing, sempre é possível saber se um programa termina sua execução, 
aceitando ou rejeitando a entrada.
C) Um processador Intel Core i9 reconhece linguagens que não são possíveis de se reconhecer 
por meio de uma máquina de Turing.
D) Toda linguagem que pode ser reconhecida por uma máquina de Turing também pode ser 
reconhecida por um autômato de uma pilha.
E) Uma máquina de Turing com três fitas, não determinística e com fita multidimensional 
consegue processar linguagens que uma máquina de Turing tradicional não conseguiria.
Diversas modificações para as máquinas de Turing determinística foram propostas ao longo dos 
anos com o objetivo de aumentar seu poder computacional. Até hoje, todos os modelos 
conseguiram no máximo igualar o poder de processamento da máquina determinística, sem 
superá-lo.
Dado o gráfico de transições de uma máquina de Turing a seguir, qual é uma sequência possível de 
estados percorridos para que essa máquina aceite a palavra de entrada ‘aabccb’?
4) 
A) q0 — q0 — q0 — q0 — q3 — q4.
B) q1 — q1 — q1 — q1 — q1 — q4.
C) q0 — q0 — q2 — q2 — q2 — q4.
D) q0 — q2 — q2 — q2 — q2 — q4.
E) q0 — q0 — q0 — q3 — q3 — q4.
Uma máquina de Turing é composta de uma fita de tamanho infinito com sua cabeça de 
leitura e escrita que servem de memória e como dispositivo de entrada e saída. Também 
5) 
existe uma função de transição, que corresponde ao programa executado pela máquina. 
Sobre a máquina de Turing, analise as seguintes afirmações:
I. Uma máquina de Turing com múltiplas fitas pode reconhecer qualquer linguagem 
recursivamente enumerável.
II. Para refutar a hipótese de Church, basta apresentar uma modificação da máquina deTuring que comprovadamente tenha mais poder computacional que uma máquina de Turing 
determinística.
III. Por padrão, uma máquina de Turing determinística pode alterar diversos pontos da fita 
em cada transição e é capaz de transferir sua atenção para mais de uma posição da fita em 
cada argumento da função de transição.
Qual(is) dessas afirmações está(ão) correta(s)?
A) Apenas I.
B) Apenas II.
C) I e II.
D) I e III.
E) I, II e III.
Na prática
A hipótese de Church diz que qualquer função computável pode ser representada por meio de uma 
máquina de Turing. Apesar de não haver como comprová-la, tal hipótese tem fortes indícios de que 
é verdadeira. Um desses indícios é o fato de que nenhuma das modificações propostas até hoje 
para esse modelo superou sua capacidade computacional.
Neste Na Prática, é explorado o poder computacional de uma máquina de Turing. Você verá como 
uma arquitetura simples de computador pode ser simulada utilizando-se uma máquina de Turing de 
múltiplas fitas. Além disso, poderá perceber a organização das fitas, para que cada uma simule um 
componente dessa arquitetura, bem como a função de transição, que deverá executar o programa 
passado como entrada.
Aponte a câmera para o 
código e acesse o link do 
conteúdo ou clique no 
código para acessar.
https://statics-marketplace.plataforma.grupoa.education/sagah/1b985ab1-b039-4b07-9b7c-77fe3e9deed9/3ddd3037-1c60-48ea-8f8d-b52c8dc486d9.jpg
Saiba mais
Para ampliar o seu conhecimento a respeito desse assunto, veja a seguir as sugestões do professor:
Alan Turing - Documentário
Neste documentário do canal DocumentáriosCiência, são apresentadas as contribuições de Alan 
Turing para diversas áreas do conhecimento como matemática, criptoanálise, lógica e filosofia, 
ciência da computação, ciência cognitiva, inteligência artificial, biologia matemática e vida artificial.
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
Da computabilidade formal às máquinas programáveis
Neste livro, é feito um paralelo entre os diversos dispositivos de computação - das calculadoras 
mecânicas aos computadores modernos - com o conceito de computabilidade. O autor dedica um 
capítulo para discutir as máquinas de Turing e as contribuições de Turing para outras áreas da 
informática.
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
A Turing machine overview
Neste website, é apresentado um projeto que construiu uma máquina de Turing. Além de vídeos 
com demonstração de seu funcionamento, há uma descrição de como a máquina foi construída e 
programada.
https://www.youtube.com/embed/x2AXca1kPQk
https://repositorio.ufsc.br/handle/123456789/157317
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
Linguagens formais e autômatos
No oitavo capítulo da obra de Menezes, é discutida a máquina de Turing como reconhecedor de 
linguagens, com enfoque nas linguagens recursivamente enumeráveis e sensíveis ao contexto.
Conteúdo interativo disponível na plataforma de ensino!
http://aturingmachine.com/index.php