Aula 6
Por:
Tarcisio Coutinho da Silva
{tcs5}@cin.ufpe.br
David Barros Hulak
{dbh}@cin.ufpe.br

10º problema de Hilbert

Tese de Church-Turing
- Algoritmos
- Computabilidade

AFD:
(Q, Σ, δ, q0, F)

PDA:
(Q, Σ, δ, q0, Γ, F)
- Pilha

MT:
(Q, Σ, δ, q0, Γ, qa, qr)
- Fita

Definição Formal
 Uma MT é uma 7-upla, (Q, ∑, Γ, δ, qo, qaceita, qrejeita),
onde
▪
▪
▪
▪
▪
▪
▪
Q é o conjunto finito de estados;
∑ é o alfabeto da entrada, ⊔ ∉ ∑;
Γ é o alfabeto da fita, ⊔ ∈ Γ e ∑ ⊆ Γ;
δ é a função de transição, δ: Q × Γ -> Q × Γ × {E, D};
qo é o estado inicial, qo ∈ Q;
qaceita é o estado de aceitação, qaceita ∈ Q;
qrejeita é o estado de rejeição, qrejeita ∈ Q.

Computação
 Uma MT M recebe como entrada w ∈ ∑*
 Coloca w na porção mais a esquerda da fita e preenche os
campos seguintes com branco, o fim da entrada é
determinado pelo primeiro símbolo em branco.
 Segue-se os passos determinado pela função de transição.
 Se tentar mover para a esquerda além da extremidade a
cabeça permanece no mesmo lugar.
 A computação só pára se entrar no estado de aceitação,
aceitando a cadeia, ou de rejeição, rejeitando a cadeia.
Caso contrário, M continua para sempre.
Durante a computação uma MT troca o estado atual, o
conteúdo da fita e a posição da cabeça. Podemos
demonstrar um momento da computação através de uma
configuração.
 Definição
▪ Escrevemos uqv e dizemos que o estado atual é q, o
conteúdo da fita é uv e a cabeça aponta para o primeiro
símbolo de v.
 Exemplo


Dizemos que uma configuração C1 origina C2 se a MT
puder ir legitimamente de C1 para C2 em um único
passo.

Casos particulares
- Extremidade direita: v qi ⊔
- Extremidade esquerda: o que fazer quando
qi a v e há movimento para a esquerda?
- Configurações de parada: estado da configuração = qa
(configuração de aceitação) ou qr (configuração de rejeição)

Exemplo:
 Dê as configurações na computação de w= 0000
na seguinte MT.
Resposta
1.
Dê as configurações na computação das
seguintes cadeias na MT usada no exemplo.
1. ε
2. 0
3. 000

Linguagem Turing-Reconhecível (Recursivamente
Enumerável)
 Linguagem que uma Máquina de Turing M reconhece.
 L(M) é o conjunto de cadeias que M aceita.
 Se uma cadeia não pertence a L(M), M rejeita ou entra em
loop.

Linguagem Turing-Decidível
 Linguagem que uma Máquina de Turing M decide.
 M pára ao computar qualquer cadeia (aceita ou rejeita).
 Toda linguagem decidível é reconhecível.

As variantes da MT têm o mesmo poder que
ela
 Multifita
 MT Não-Determinística
 Enumerador

Pode ser convertida em uma MT colocando as suas fitas
em uma só, determinando uma separação entre elas.

Toda MT multifita tem uma MT equivalente de uma fita.

Uma linguagem é Turing-reconhecível se e somente se
uma MT multifita a reconhece.

Uma MT que gera uma árvore de configurações.

Se em algum ramo da computação origina um estado
de aceitação, MT aceita w.

Toda MT não determinística tem uma MT equivalente
determinística.

Uma linguagem é Turing-reconhecível se e somente
se uma MT não-determinística a reconhece.

É uma MT que controla uma impressora e imprime
as cadeias que ela aceita.

Uma linguagem é Turing-reconhecível se e somente
se um enumerador a enumera
(1ª questão)
Defina:

-
Máquina de Turing.
-
M aceita w.
-
Linguagem reconhecível.
-
Linguagem decidível.
-
Mostre que toda linguagem decidível é
reconhecível.

Michael Sipser: Introduction to the Theory of
Computation (2nd edition)
Aula 6
Arthur Ramos - [email protected]
David Hulak - [email protected]
Filipe Martins - [email protected]
Hugo Azevedo - [email protected]
Paulo Orlando - [email protected]
Ricardo Salomão - [email protected]
Tarcisio Coutinho - [email protected]
Tiago Ferreira - [email protected]
Thyago Machado - [email protected]
Vinícius Henrique - [email protected]