Prévia do material em texto

01/05/2020 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 1/4
O Problema da Parada - problemas não solucionáveis
Exercício 4:
Considere a máquina de Turing M = (Q, A, g, q0, F), onde:
 Q = {q0, q1, qf}
 A = {b, ·, x}
 F = {qf}
 q0 é o estado inicial;
 b representa “branco” e · representa i início da fita;
 A função de transição é dada pela tabela abaixo:
 
estado Símbolo de
entrada
g
q0 x (q1, b)
q0 b (qf, b)
q0 · (q0, ®)
q1 x (q0, x)
q1 b (q0, ®)
q1 · (q1, ®)
 
Qual deve ser a representação “M” da máquina de Turing M?
A)
 “M” = (q01, q100, q01, a000), (q01, a000, q11, a000), (q10, a001, q00, a011), (q01, a100,
q00, q011), (q01, a001, q00, a001), (q01, a011, q01, a011).
B)
“M” = (q00, a100, q01, a000), (q00, a000, q11, a000), (q00, a001, q00, a011), (q01, a100, q00,
a011), (q01, a000, q00, a011), (q01, a001, q01, a011).
C)
 
“M” = (q01, q100, q01, a000), (q01, a000, q11, a000), (q01, a001, q00, a111), (q10, a100, q00,
q011), (q01, a000, q00, a001), (q01, a001, q01, a011).
D)
“M” = (q00, q100, q01, q000), (q00, a000, q11, a000), (q00, a001, q00, a011), (q01, a100, q00,
q011), (q01, a000, q00, a001), (q01, a001, q01, a011).
E)
“M” = (a00, a100, a01, q000), (q00, a000, q11, a000), (q00, a001, q00, a011), (q01, a100, q00,
q011), (q01, a000, q00, a001), (q01, a001, q01, a011).
https://online.unip.br/Arquivo?id=63521.pdf
01/05/2020 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 2/4
O aluno respondeu e acertou. Alternativa(B)
Comentários:
B) sem justificativa
Exercício 5:
Considere a seguinte definição: “Dada uma Máquina Universal M qualquer e uma palavra w
qualquer sobre o alfabeto de entrada, existe um algoritmo que verifique se M para, aceitando ou
rejeitando, ao processar a entrada w?”. Trata-se da definição do problema conhecido como:
A)
Problema da Análise Lexicográfica;
B)
Problema das Máquinas Universais;
C)
 Problema das Entradas;
D)
 Problema da Parada;
E)
Problema da Auto-Aplicação;
O aluno respondeu e acertou. Alternativa(D)
Comentários:
B) Existe, pelo menos, uma máquina de Turing reconhecedora que sempre para
qualquer que seja a entrada
D) sem justificativa
Exercício 6:
Considere uma máquina de Turing X capaz de analisar qualquer máquina de Turing T. As duas
únicas possibilidades de X parar são descritas a seguir:
I - A Máquina de Turing X deve parar com a fita contendo apenas um algarismo 1, se e somente
se, T aceitar uma cadeia a.
II - A Máquina de Turing X deve parar com a fita contendo apenas um
algarismo 0, se e somente se T, nunca parar ao processar a cadeia a.
Assinale a alternativa correta:
 
A)
 X existe e T não existe;
B)
Se X existe então T não existe;
01/05/2020 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 3/4
C)
 X existe, mas T pode existir.
D)
X não existe.
E)
 T existe se e somente se X existir.
O aluno respondeu e acertou. Alternativa(D)
Comentários:
B) sem justificativa
E) sem justificativa
D) sem justificativa
Exercício 7:
Considere as seguintes afirmações:
I – Toda Linguagem Turing-decidível é Turing-aceitável;
II – Se L é Turing-decidível então seu complemento também será
III – Nem toda Linguagem Turing-aceitável é Turing-decidível e nem todo
complemento de linguagem Turing-aceitável é Turing-decidível;
Estão corretas as afirmações:
A)
Apenas I;
B)
Apenas I e II;
C)
 Apenas III;
D)
Apenas II e III;
E)
 I, II e III;
O aluno respondeu e acertou. Alternativa(E)
Comentários:
C) sem justificativa
E) sem justificativa
Exercício 8:
01/05/2020 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 4/4
A investigação da solucionabilidade de problemas em máquinas de Turing pode ser vista como um
problema de reconhecimento de linguagens. Assim a questão da solucionabilidade de um
problema pode ser traduzida como uma investigação se a linguagem gerada é recursiva
(problema solucionável) ou recursivamente enumerável (problema parcialmente solucionável). A
não-solucionabilidade refere-se à inexistência de um método geral e efetivo para decidir se um
programa (máquina de Turing) executado em uma máquina universal para, qualquer que seja a
entrada. Considere as seguintes afirmações:
I – Como algoritmos podem representar máquinas de Turing e vice-versa, isto implica que
questões gerais sobre algoritmos não podem ser sempre respondidas com o auxílio de algoritmos.
II – Nenhuma linguagem (Máquina de Turing Universal) permite sistematizar a forma de descobrir
se um programa (Máquina de Turing) faz realmente o que se deseja para qualquer entrada
possível;
III – O problema da verificação formal de programas é insolúvel no seu caso geral;
 
Estão corretas as afirmações:
A)
Apenas I;
B)
 Apenas I e II;
C)
Apenas II e III;
D)
I, II e III;
E)
Apenas II;
 
O aluno respondeu e acertou. Alternativa(D)
Comentários:
B) sem justificativa
E) sem justificativa
D) sem justificativa