U n i v e r s i d a d e da M a d e i r a
DEPARTAMENTO DE MATEMÁTICA E ENGENHARIAS
TEORIA DA COMPUTABILIDADE E COMPLEXIDADE
Licenciatura em Engenharia Informática (2.º ano – 1.º->2.º semestre)
Licenciatura em Ensino de Informática (2.º ano – 1.º->2.º semestre)
Licenciatura em Matemática (2.º ano – 1.º->2.º semestre)
Ano Lectivo 2006/2007
Folha de Exercícios n.º 8
Máquina de Turing. Funções Turing-computáveis
1. Desenvolva uma máquina de Turing que, recebendo uma palavra escrita no
sistema binário, devolve a negação da mesma.
2. Generalizando a ideia do exercício anterior, construa uma máquina de Turing que
efectue a negação, não de uma, mas sim de n palavras binárias. Na especificação
dessa máquina considere que duas palavras binárias consecutivas são separadas
por um (e só um) espaço em branco.
3. Desenvolva uma máquina de Turing que ao receber uma palavra escrita com
simbolos do conjunto {A,B,C}, apaga essa palavra e devolve a fita em branco.
4. Mostre que as seguintes funções são Turing-computáveis:
(a) f:IN o → IN o com f(x) = x
(b) f:IN o → IN o com f(x) = 0
(c) 1: IN o → IN o assim 1(x) = 1
(d) f:IN o → IN o com f(x) = x + 1
(e) f:IN o → IN o com f(x) = x + 5
⎧0 se x = 0
(f) f:IN o → IN o , com f ( x) = x −& 1 = ⎨
⎩ x-1 se x ≥ 1
(g) f:IN o2 → IN o , com f ( x,y ) = x + y
1
5. Especifique uma máquina de Turing que calcule a função f: IN o → IN o assim
definida f (n) = 2n .
6. Construa uma máquina de Turing que calcule a função g: IN o → IN o , definida
por g(n) = n (mod 3) (resto da divisão inteira de n por 3).
7. Identifique qual é a função unária calculada pela seguinte máquina de Turing:
q1 0 R q1
q1 1 0 q2
q2 0 R q2
q2 1 R q1
8. Especifique uma máquina de Turing que calcule a função h: IN o → IN o , definida
⎡n⎤
por h(n) = ⎢ ⎥ .
⎣3⎦
2