Teoria da Computação: Problema da Parada e Máquina de Turing

Prévia do material em texto

04/06/2020 EPS
simulado.estacio.br/alunos/ 1/3
 
 
 
 TEORIA DA COMPUTAÇÃO
8a aula
 Lupa 
PPT MP3
 
Exercício: CCT0832_EX_A8_201908040459_V2 19/05/2020
Aluno(a): JOSEILDON DA SILVA DANTAS 2020.1 EAD
Disciplina: CCT0832 - TEORIA DA COMPUTAÇÃO 201908040459
 
 1a Questão
Qual das seguintes afirmações é falsa?
 
 Não existe autômato finito determinístico que reconheça alguma linguagem livre de contexto.
 
 Dada uma máquina de Turing M com alfabeto de entrada Σ e uma string w∈Σ, não se sabe se a computação de M com
entrada w vai ou não parar.
 
Um autômato com duas pilhas pode ser simulado por uma máquina de Turing.
 
 O problema da parada é indecidível.
 
 Não existe algoritmo que determina quando uma gramática livre de contexto arbitrária é ambígua.
 
Respondido em 19/05/2020 08:51:47
Explicação:
(A) Dada uma máquina de Turing M com alfabeto de entrada Σ e uma string w∈Σ, não se sabe se a computação de M com entrada
w vai ou não parar.
(B) O problema da parada é indecidível.
(C) Não existe algoritmo que determina quando uma gramática livre de contexto arbitrária é ambígua.
(D) Não existe autômato finito determinístico que reconheça alguma linguagem livre de contexto.
(E) Um autômato com duas pilhas pode ser simulado por uma máquina de Turing.
A única alternativa falsa é a D. Linguagens regulares são reconhecidas por autômatos finitos determinístico e, pela hierarquia de
Chomsky, toda linguagem regular também é livre de contexto.
 
 2a Questão
O problema da parada para máquinas de Turing, ou simplesmente problema da parada, pode ser assim descrito: determinar, para
quaisquer máquinas de Turing M e palavra w, se M irá eventualmente parar com entrada w.
Mais informalmente, o mesmo problema também pode ser assim descrito: dados um algoritmo e uma entrada finita, decidir se o
algoritmo termina ou se executará indefinidamente.
Para o problema da parada, 
 existe algoritmo exato de tempo de execução polinomial para solucioná-lo.
 
 não existe algoritmo que o solucione, não importa quanto tempo seja disponibilizado.
 
http://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
javascript:diminui();
javascript:aumenta();
javascript:abre_frame('2','8','','','');
javascript:abre_frame('3','8','','','');
04/06/2020 EPS
simulado.estacio.br/alunos/ 2/3
existe algoritmo exato de tempo de execução exponencial para solucioná-lo.
 
 não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução exponencial que o soluciona,
fornecendo respostas aproximadas.
 
 não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução polinomial que o soluciona,
fornecendo respostas aproximadas.
 
Respondido em 19/05/2020 08:51:51
Explicação:
O problema da parada pode ser definido como:
Seja S o conjunto de todos os pares (A,D), em que A é um algoritmo, e D, dado de entrada; (A,D) tem a propriedade P se o
algoritmo A, quando recebe o dado D, eventualmente produz um resultado (ou seja, eventualmente para) A tese de Church-Turing
mostra que o problema da parada é não decidível, ou seja, não existe um algoritmo H tal que para todo (A,D) que pertence à
S: H(A,D)= { 1 se A(D) eventualmente para; 
0 caso contrário 
A prova informal de que tal H não existe é obtida por contradição.
Suponha que H existe. Seja C o algoritmo: ¿entrada A; executa H(A,A); se H(A,A)=0, então, retorna 1, senão entra em loop¿.
Então, ∀A,(H(A,A)=0 ⇿ ¬A(A) eventualmente para ⇿ H(A,A)=0) (pois H é função total) e ∀A,(H(A,A)=0 ⇿ ¬A(A) eventualmente
para).
Tomando A como sendo C, obtemos que C(C) eventualmente para, se e somente se ¬C(C) eventualmente para, e isto é uma
contradição!
Logo, não existe um algoritmo que solucione o problema.
As respostas das alternativas A e B não estão corretas, pois afirmam que existe um algoritmo que resolve o problema.
As respostas das alternativas D e E não estão corretas, pois afirmam que existe um algoritmo de aproximação e, pelo exposto na
justificativa da resposta correta, tal algoritmo não existe.
 
 3a Questão
No que concerne a utilização e o processamento de máquina de Turing, assinale a opção correta.
 
 O conjunto de símbolos usados pela máquina de Turing é infinito. 
A máquina em questão registra o valor da palavra de entrada e depois pára, quando a função indicar um movimento da
cabeça para a esquerda e ela já se encontrar no início da fita. 
Uma máquina de Turing pode alterar várias entradas em cada vez, pois ela é capaz de transferir sua atenção para mais de
uma posição da fita em cada argumento da função de transição.
 
 
As saídas podem ser apenas binárias, pois as referidas máquinas trabalham com representações lógicas. 
 Na máquina de Turing, o processamento inclui a sucessiva aplicação da função programada até ocorrer uma condição de
parada. 
Respondido em 19/05/2020 08:51:54
Explicação:
.
 
 4a Questão
Considere a máquina de Turing descrita pelas seguintes regras, iniciando no estado q0:
(q0, 0) (q0, 0, D)
(q0, 1) (q1, 0, D)
(q2, 0) (q2, 1, D)
O que essa máquina faz?
 Anda para a direita indefinidamente, sem modificar a fita.
 Anda para a direita até encontrar um 1, substitui por 0 e para. 
Para assim que encontrar um 0.
Substitui todos os 0¿s por 1¿s na fita.
Substitui todos os 1¿s por 0¿s na fita.
 
Respondido em 19/05/2020 08:51:56
04/06/2020 EPS
simulado.estacio.br/alunos/ 3/3
Explicação:
A máquina inicia no estado q0. Se ela ler um 0,continua em q0 e anda para a direita, conforme a primeira regra.
Se ela ler um 1, ela o substitui por 0, muda para o estado q1 e vai para a direita, conforme a segunda regra. Como não existe
regra que trate o estado q1, a máquina para. 
Logo, a alternativa d está correta.
 
 5a Questão
Correlacionando a hierarquia de Chomsky com os reconhecedores de linguagem, é correto afirmar que a máquina de Turing,
tradicional ou básica, corresponde às gramáticas
 livres do contexto. 
irregulares. 
sensíveis ao contexto. 
 sem restrição.
 
regulares. 
Respondido em 19/05/2020 08:52:15
Explicação:
A MAQUINA DE TURING CORRESPONDE A GRAMATICAS SEM RESTRIÇÕES
 
 6a Questão
Na máquina de turing o componente que contem o estado corrente da máquina é:
 
 A memoria
 A unidade de controle
 
O processador
A fita
O programa
Respondido em 19/05/2020 08:52:01
Explicação:
UNIDADE DE CONTROLE ¿ Contém o estado corrente da máquina, lê ou escreve dados na fita e pode se mover para a
¿frente¿(direita) ou para ¿trás¿(esquerda)
javascript:abre_colabore('38403','194141018','3876731372');