Lista 3 - Tese Church-Turing e Maquinas de Turing

Prévia do material em texto

Área Conhecimento em Algoritmos e Teoria DCC/UFMG Fundamentos de Teoria da
Computação 2021/2
LISTA DE EXERCÍCIOS
Lista 3
(A Tese de Church-Turing e Máquinas de Turing)
Leitura necessária:
• Introdução à Teoria da Computação, 2a Edição (Michael Sipser):
– Caṕıtulo 3.1: Máquinas de Turing
– Caṕıtulo 3.2: Variantes de Máquina de Turing
– Caṕıtulo 3.3: A definição de Algoritmo
Revisão.
1. Responda formalmente às seguintes perguntas:
(a) Qual a definição formal de uma máquina de Turing?
(b) Qual a diferença entre um reconhecedor e um decisor para uma linguagem?
(c) Qual a diferença entre uma linguagem Turing-reconhećıvel e uma linguagem Turing-decid́ıvel?
Qual das duas classes de linguagens é mais geral?
(d) O que diz a Tese de Church-Turing?
(e) Baseado no que você aprendeu no curso, cite três evidências que sugiram que a Tese de Church-
Turing seja verdadeira.
Exerćıcios.
2. (Sipser 3.1 - Itens (a), (b) e (c)) Este exerćıcio concerne a MT M2 cuja descrição e diagrama de estados
aparecem no Exemplo 3.7 (vide figura abaixo).
Em cada um dos itens abaixo, dê a sequência de configurações nas quais M2 entra quando iniciada
sobre a cadeia de entrada indicada:
1
(a) 0.
(b) 00.
(c) 000.
3. (Sipser 3.2 - Itens (a), (c) e (e)) Este exerćıcio concerne a MT M1 cuja descrição e diagrama de estados
aparecem no Exemplo 3.9 (vide figura abaixo).
Em cada um dos itens abaixo, dê a sequência de configurações nas quais M1 entra quando iniciada
sobre a cadeia de entrada indicada:
(a) 11.
(c) 1##1.
(e) 10#10.
4. (Sipser 3.3) Modifique a demonstração do Teorema 3.16 (que diz que toda MT não-determińıstica tem
uma MT determińıstica que lhe é quivalente) para obter o Corolário 3.19 (que diz que uma linguagem
é decid́ıvel se, e somente se, alguma MT não-determińıstica a decide).
(Você pode assumir o seguinte resultado sobre árvores. Se todo vértice em uma árvore possui um
número finito de filhos e todo ramo da árvore tem um número finito de vértices, então a árvore como
um todo possui um número finito de vértices.)
5. (Sipser 3.5) Examine a definição formal de uma máquina de Turing para responder às seguintes per-
guntas, e explique seu racioćınio.
(a) Uma máquina de Turing pode alguma vez escrever o śımbolo em branco na sua fita?
(b) O alfabeto de fita Γ pode ser o mesmo que o alfabeto de entrada Σ?
(c) A cabeça de uma máquina de Turing pode alguma vez estar na mesma localização em dois passos
sucessivos?
(d) Uma máquina de Turing pode conter apenas um único estado?
2
6. (Sipser 3.6) No Teorema 3.21 mostramos que uma linguagem é Turing-reconhećıvel sse algum enume-
rador a enumera. Por que não usamos o seguinte algoritmo mais simples para a direção de ida da
prova? Tal qual anteriormente, s1, s2, . . . é uma lista de todas as cadeias em Σ
∗.
E = “Ignore a entrada.
1. Repita o que se segue para i = 1, 2, 3, . . .
2. Rode M sobre si.
3. Se ela aceita, imprima si.”
7. (Sipser 3.7) Explique por que a descrição abaixo não é uma descrição de uma máquina de Turing
leǵıtima.
Mruim = “A entrada é um polinômio p sobre as variáveis x1, . . . , xk.
1. Tente todas as posśıveis valorações de x1, . . . , xk para valores inteiros.
2. Calcule o valor de p sobre todas essas valorações.
3. Se alguma dessas valorações torna o valor de p igual a 0, aceite; caso contrário, rejeite.”
8. (Sipser 3.8 - Itens (a) e (b).) Dê descrições a ńıvel de implementação de máquinas de Turing que
decidam as linguagens abaixo sobre o alfabeto {0, 1}.
Apenas para o item (a), dê também o diagrama de estados de sua Máquina de Turing. (Não precisa
fazer o mesmo para o item (b)!)
(a) {w | w contém o mesmo número de 0’s e 1’s}.
(b) {w | w contém duas vezes mais 0’s que 1’s}.
9. (Sipser 3.10) Digamos que uma máquina de Turing de escrita-única é uma MT de uma única fita que
pode alterar cada célula da fita no máximo uma vez (incluindo a parte da entrada da fita). Mostre
que essa variante do modelo da máquina de Turing é equivalente ao modelo comum da máquina de
Turing. (Dica: Como um primeiro passo considere o caso no qual a máquina de Turing pode alterar
cada célula de fita no máximo duas vezes. Use bastante fita.)
10. (Sipser 3.15 - Itens (a), (b), e (c)) Mostre que a coleção de linguagens decid́ıveis é fechada sob a
operação de
(a) união.
(b) complementação.
(c) concatenação.
11. (Sipser 3.16 - Itens (a) e (d)) Mostre que a coleção de linguagens Turing-reconhećıveis é fechada sob
a operação de
(a) união.
(d) interseção.
12. (Sipser 3.22) Seja A a linguagem contendo somente a única cadeia s, onde
s =
{
0, se vida nunca será encontrada em Marte, ou
1, se vida será encontrada em Marte algum dia.
A é decid́ıvel? Por que ou por que não? Para os propósitos deste problema, assuma que a questão de
se vida será encontrada em Marte tem uma resposta não-amb́ıgua “SIM” ou “N~AO”.
3