Máquinas de Turing,
Procedimentos,
Algoritmos e
Tese de Church
Alcides Calsavara
Referências Bibliográficas
 Cláudio L. Lucchesi, Imre Simon, Istvan
Simon, Janos Simon, Tomasz
Kowaltowski. Aspectos Teóricos da
Computação. Rio de Janeiro: Instituto de
Matemática Pura e Aplicada, 1979.
 A. M. Turing. On computable numbers,
with an application to the
Entscheidungsproblem. Proc. London
Math. Soc. Series 2, 42 (1936-37), 230265 e 43 (1937) 544-546.
Alan Turing
Alan Mathison Turing
23 de junho de 1912 – 7 de junho de 1954
Inglaterra, Londres
Fundador da Ciência da Computação
Matemático
Filósofo
Decifrador de código (decifrou o Enigma em 1939)
Pioneiro da Inteligência Artificial
http://www.turing.org.uk/turing/
Máquinas de Turing:
Contextualização
 Modelo formal de algoritmos
 Permite a representação de qualquer algoritmo
 Permite provar qualquer asserção matemática
 Facilita o estudo da complexidade
computacional dos algoritmos
 Máquina teórica
 Base teórica para a arquitetura dos
computadores atuais (von Neumann)
Componentes de uma
Máquina de Turing Determinística
 Fita de entrada/trabalho/saída





Subdividida em cédulas
Cada cédula contém um símbolo de um alfabeto ∑
Por exemplo, ∑ ═ { ├, ‫ٱ‬, 0, 1 }
Primeira célula à esquerda contém o símbolo ├
O símbolo ‫ ٱ‬representa o branco
 Controle central


Possui uma cabeça móvel de leitura e gravação
Em cada instante, a cabeça encontra-se sobre uma
célula da fita
Esquema de uma
Máquina de Turing Determinística
Controle central
Cabeça móvel
de leitura e
gravação
├0110001011011100 ‫ٱ ٱ ٱ‬
...
Fita de entrada/saída/trabalho
Função de uma
Máquina de Turing Determinística
 Reconhece um conjunto A de palavras
de um certo alfabeto se, para toda
palavra de entrada x, pára e aceita x se,
e somente se, x pertence a A.
 Calcula uma função que transforma uma
palavra em outra, sobre um mesmo
alfabeto.
Estados de uma
Máquina de Turing Determinística
 Em cada instante, o controle central está em um
estado q, de um conjunto finito de estados Q
 O estado inicial é chamado de q0:



Cabeça sobre a célula mais à esquerda, a qual
contém o símbolo├
As n células seguintes contêm uma palavra x,
chamada de entrada
 Uma palavra é uma seqüência finita de
símbolos de ∑, excluindo os símbolos ├ e ‫ٱ‬
As demais células da fita contêm o símbolo ‫ٱ‬
Passo de uma
Máquina de Turing Determinística
1. Ler o símbolo σ sob a cabeça;
2. Escrever o símbolo σ′ no lugar de σ;
3. Reposicionar a cabeça, que pode ser
movida uma célula à direita ou à
esquerda, ou deixada no mesmo lugar;
4. Mudar o contole central para um novo
estado q′.
Passo de uma
Máquina de Turing Determinística
 As operações (2), (3) e (4) dependem apenas do símbolo
σ, lido na operação (1) e do estado q do controle central
antes do passo corrente.
 O símbolo σ′ é necessariamente diferente de ├ sempre
que σ for diferente de ├.
 A máquina pára após uma seqüência de passos quando
o controle central alcança um dos seguintes estados
finais:


qA : a máquina aceita a entrada x
qR : a máquina rejeita a entrada x
 É possível que a máquina nunca pare.
 A saída da máquina, definida apenas se a máquina
parar, é uma palavra (nova ou idêntica à entrada x).
Função de transferência de uma
Máquina de Turing Determinística
 Determina como se dão as transições de estados e as






suas conseqüências com relação à fita de
entrada/saída/trabalho
δ( q, σ ) = ( q′, σ′, Δ )
q : estado atual da máquina
σ : símbolo lido da célula sobre a cabeça
q′ : novo estado da máquina
σ′ : símbolo escrito na célula sobre a cabeça
Δ : deslocamento da cabeça



Δ = +1 : cabeça move uma célula para a direita
Δ = -1 : cabeça move uma célula para a esquerda
Δ = 0 : cabeça não move
Exemplo de uma
Máquina de Turing Determinística
 ∑ ═ { ├, ‫ٱ‬, 0, 1, A, B }
 Reconhece toda e qualquer palavra formada
por n símbolos 0 seguidos por n símbolos 1, tal
que n ≥ 1
 Substitui alternadamente um 0 por um A e um 1
por um B. Exemplo:



entrada = 0011
saída = AABB
passos: A011, A0B1, AAB1, AABB
 Q = { q0, q1, q2, q3, q4, qA, qR }
 Função de transferência: tabela
Função de transferência (δ)
para o exemplo: tabela
q
σ
q′
σ′
∆
q0
├
q0
├
+1
q0
0
q1
A
+1
q1
0
q1
0
+1
q1
B
q1
B
+1
q1
1
q2
B
-1
q2
B
q2
B
-1
q2
0
q3
0
-1
q2
A
q4
A
+1
q3
0
q3
0
-1
q3
A
q0
A
+1
q4
B
q4
B
+1
q4
‫ٱ‬
qA
‫ٱ‬
0
qA
σ
qA
σ
0
qR
σ
qR
σ
0
* Para todo (q, σ) não especificado na tabela acima, δ ( q, σ ) = ( qR, σ, 0 )
Função de transferência (δ)
para o exemplo: diagrama
├ / ( ├, +1 )
σ / ( σ, 0 )
0 / ( 0, -1 )
A / ( A, +1 )
q0
q3
0 / ( A, +1 )
qR
0 / ( 0, -1 )
0 / ( 0, +1 )
1 / ( B, -1 )
q1
q2
B / ( B, +1 )
‫ ٱ‬/ ( ‫ٱ‬, 0 )
A / ( A, +1 )
B / ( B, -1 )
q4
B / ( B, +1 )
( Não estão representadas as transições para o estado qR. )
qA
σ / ( σ, 0 )
Execução da máquina
exemplo para a entrada 01
q0 ├ 0 1 ‫ٱ‬
q4 ├ A B ‫ٱ‬
q0 ├ 0 1 ‫ٱ‬
q4 ├ A B ‫ٱ‬
q1 ├ A 1 ‫ٱ‬
qA ├ A B ‫ٱ‬
q2 ├ A B ‫ٱ‬
qA ├ A B ‫ٱ‬
Portanto, a máquina aceita a entrada 01 e pára a sua execução.
Execução da máquina
exemplo para a entrada 001
q0 ├ 0 0 1 ‫ٱ‬
q2 ├ A 0 B ‫ٱ‬
q1 ├ A A B ‫ٱ‬
q0 ├ 0 0 1 ‫ٱ‬
q3 ├ A 0 B ‫ٱ‬
qR ├ A A B ‫ٱ‬
q1 ├ A 0 1 ‫ٱ‬
q0 ├ A 0 B ‫ٱ‬
qR ├ A A B ‫ٱ‬
q1 ├ A 0 1 ‫ٱ‬
q1 ├ A A B ‫ٱ‬
Portanto, a máquina rejeita a entrada 001 e pára a sua execução.
Execução da máquina
exemplo para a entrada 0011
q0
▼
├ 0 0 1 1 ‫ٱ‬
q1
▼
├ A A B 1 ‫ٱ‬
q0
▼
├ 0 0 1 1 ‫ٱ‬
q2
▼
├ A A B B ‫ٱ‬
q1
▼
├ A 0 1 1 ‫ٱ‬
q2
▼
├ A A B B ‫ٱ‬
q1
▼
├ A 0 1 1 ‫ٱ‬
q4
▼
├ A A B B ‫ٱ‬
q2
▼
├ A 0 B 1 ‫ٱ‬
q4
▼
├ A A B B ‫ٱ‬
q3
▼
├ A 0 B 1 ‫ٱ‬
q4
▼
├ A A B B ‫ٱ‬
q0
▼
├ A 0 B 1 ‫ٱ‬
qA
▼
├ A A B B ‫ٱ‬
q1
▼
├ A A B 1 ‫ٱ‬
qA
▼
├ A A B B ‫ٱ‬
Portanto, a máquina aceita a entrada 0011 e pára a sua execução.
Máquina de Turing
Não Determinística
 Contém uma fita adicional: fita de
sugestões.
 O controle central não pode escrever na
fita de sugestões.
 A função de transferência da máquina
depende não só do estado q do controle
central e do símbolo σ lido da fita de
entrada/saída/trabalho, mas também do
símbolo lido da fita de sugestões.
Procedimento Efetivo
1. A descrição do procedimento deve ser finita.
2. Deve partir de um certo número de dados e deve
produzir um certo número de resultados que mantêm
uma relação específica com os dados.
3. Deve existir um agente computacional (humano,
mecânico, eletrônico, etc) que execute as instruções do
procedimento.
4. Cada instrução especificada pelo procedimento deve
estar bem definida, não deixando dúvidas quanto ao seu
resultado.
5. As instruções do procedimento devem ser efetivas, isto
é, devem ser tão simples que poderiam ser executadas,
em princípio, por uma pessoa usando lápis e papel, num
espaço de tempo finito.
Algoritmo
 Um procedimento que termina para
quaisquer valores dos dados.
Exemplo de procedimento
efetivo: Algoritmo de Euclides
Cálculo do máximo divisor comum (mdc) de dois inteiros positivos m e n:
Passo 1: Adote como valores iniciais de x e y os valores m e n, respectivamente.
Passo 2: Adote como valor de r o resto da divisão do valor de x pelo valor de y.
Passo 3: Adote como o novo valor de x o valor de y,
e como novo valor de y o valor de r.
Passo 4: Se o valor de r é nulo, então o valor de x é o mdc procurado,
e o cálculo termina; caso contrário, volte a executar as instruções
do procedimento a partir do passo 2.
Tese de Church
 Qualquer procedimento efetivo pode ser
realizado por uma máquina de Turing.
 Para cada programa em um certa linguagem
existe uma máquina de Turing que calcula a
mesma função.
 Passível de demonstração, pois afirma a
equivalência de um conceito informal
(procedimento efetivo) e um conceito formal
(máquina de Turing).
 Evidência empírica: cada um dos algoritmos e
procedimentos efetivos usados em matemática
pode ser descrito por meio de uma máquina de
Turing.
Medidas de complexidade de
máquinas de Turing
 Eficiência de um algoritmo: função que
dá o tempo de execução de acordo com
a entrada.
 “tempo” é dado pelo número de passos
tomados pela máquina até parar.
 “memória” utilizada é dada pelo número
de células da fita visitadas pela cabeça
de leitura/gravação da máquina até
parar.
Exercícios
 Mostre os passos da máquina de Turing
vista acima para as seguintes entradas:




010
011
000111
10