EXERCICIO 8

Prévia do material em texto

03494 - COMPUTABILIDADE E A MÁQUINA DE TURING
	 
		
	
		1.
		Com base nas afirmativas abaixo sobre a descrição instantânea (DI) da máquina de Turing assinale a resposta correta:
 
I. Lembra o estado da máquina.
II. Lembra da célula que está sendo digitalizada pelo cabeçote de leitura e gravação.
III. O conteúdo de todas as células da fita.
IV. O conteúdo da célula seguinte a que está sendo lida.
	
	
	
	I e IV, apenas.
	
	
	I, II e IV, apenas
	
	
	II e IV, apenas
	
	
	I, II e III, apenas
	
	
	II e III, apenas
	Data Resp.: 04/12/2023 18:24:35
		Explicação: 
Não há como a cabeça de leitura saber o que está na célula seguinte a ser lida. Esta afirmativa está errada. As demais estão corretas conforme a definição de Descrição Instantânea.
	
	
	 
		
	
		2.
		Para resolver problemas, precisamos construir algoritmos. Para esses algoritmos, suas complexidades precisam ser calculadas, as quais são necessárias para analisar os algoritmos e encontrar o mais adequado.  Considere as seguintes quatro funções:
f1 (n) = 2n
f2 (n) = n2
f3 (n) = 2n2
f4 (n) = 2n + 3
 
Quais das seguintes sentenças matemáticas são verdadeiras?
I. para n > 0, f2 (n) < f3 (n)
II. para n > 2, f1 (n) < f2 (n)
III. para n = 0, f2 (n) < f3 (n)
IV. para n < 2, f1 (n) < f2 (n)
V. para n > 2, f3 (n) < f4 (n)
 
	
	
	
	somente I, II e V.
	
	
	somente I e II.
	
	
	somente III, IV e V.
	
	
	somente II, III e IV.
	
	
	somente I, III e IV.
	Data Resp.: 04/12/2023 18:25:03
		Explicação: 
Consideremos a seguinte tabela:
	Função
	n = 0
	n = 2
	n = 10
	n = 20
	f1(n)
	0
	4
	20
	40
	f2(n)
	0
	4
	100
	400
	f3(n)
	0
	8
	200
	800
	f4(n)
	4
	7
	1027
	1.048.579
 
É fácil observar que para n = 0, f2 (n) = f3 (n) = 0 e que para n < 2, f1 (n) = f2 (n) = 0, logo são falsas; as sentenças I e II são verdadeiras.
	
	
	 
		
	
		3.
		Na máquina de Turing, a função de transição δ está na forma:(onde Q é o conjunto finito de estados, Σ é o conjunto finito de alfabetos de entrada, Γ é o símbolo de fita permitido, L significa esquerda, R significa direita e H significa parada).
	
	
	
	Q × Γ → (Q × Σ)
	
	
	Q × Γ → (Q × Γ × {L, R, H})
	
	
	Q × Γ → (Q × Σ × {H})
	
	
	Q ×Σ→ (Q × {L, R, H})
	
	
	Q ×Σ→ (Q × Σ × {L, R, H})
	Data Resp.: 04/12/2023 18:25:47
		Explicação: 
A função de transição de estados para MT é definida como um produto cartesiano de Q × Γ, onde Γ é alfabeto da fita, levando em uma imagem definida por outro produto cartesiano de Q × Γ multiplicado pelas ações da máquina em seguir para a esquerda, direita ou parar {L, R, H}.
	
	
	 
		
	
		4.
		Seja uma MT T dada pelas quíntuplas:
1. (0, 1, 1, 0, D)
                2. (0, b, 1, 1, H)Considere que 0 é um estado inicial e 1 é um estado final e a configuração inicial da fita igual a 111, com brancos antes e depois da cadeia 111 e n é o tamanho da cadeia, neste caso igual a 3. 
Qual a função que calcula essa MT?
	
	
	
	2n
	
	
	2n+1 - 1
	
	
	2n+1
	
	
	2n -1
	
	
	2n +1
	Data Resp.: 04/12/2023 18:26:14
		Explicação: 
Esse exemplo mostra o poder de computação das MT. Deve-se começar utilizando a quíntupla 1. Enquanto a MT ler 1 na fita, escreve 1, continua no estado 0 e anda para a direita (D). Ao encontrar um branco, escreve 1, muda para o estado final 1 e para (H). A cadeia final é 1111. A cadeia inicial era 111 = 23-1, foi transformada em 1111 = 24-1. Logo a MT calcula 2n+1 - 1
	
	
	 
		
	
		5.
		O problema da parada para máquinas de Turing, ou simplesmente problema da parada, pode ser assim descrito: determinar, para qualquer máquina 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 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. 
	
	
	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. 
	
	
	Não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução polinomial que o soluciona, fornecendo respostas aproximadas.
	Data Resp.: 04/12/2023 18:26:41
		Explicação: 
Não existe nenhuma máquina de Turing M que consiga decidir se vai parar ou entrar em loop infinito. O problema da parada é indecidível, portanto não existe algoritmo que o solucione.
	
	
	 
		
	
		6.
		Uma redução é um processo de conversão de um problema em outro problema resolvido de tal forma que a solução do segundo problema possa ser usada para resolver o primeiro problema. Em particular, a redutibilidade pode ser usada para demonstrar que problemas são indecidíveis ou decidíveis. Nesse contexto, avalie as seguintes afirmativas:
I. A Redutibilidade não diz nada em resolver os problemas A ou B sozinhos, mas somente sobre a resolução de A na presença de um método para resolver B.
II. Reduções apresentam um importante papel em classificar os problemas em decidíveis ou indecidíveis.
III. Se A é redutível a B e B é um problema indecidível, então A é um problema decidível.
 
Quais as afirmativas verdadeiras?
	
	
	
	II e III.
	
	
	I, II e III.
	
	
	III.
	
	
	I e II.
	
	
	I e III.
	Data Resp.: 04/12/2023 18:27:06
		Explicação: 
Na afirmativa III, se A é redutível a B e B é um problema indecidível, então A é um problema indecidível.
	
	
	 
		
	
		7.
		Uma analogia matemática simples do conceito de redutibilidade ocorre quando desejamos medir a área de um retângulo. Nesse sentido, podemos reduzir o problema a medição da largura e comprimento. Acerca dos conceitos de redução, o que é verdadeiro para redutibilidade?
 
	
	
	
	Converter um problema resolvido em outro problema não resolvido.
	
	
	Se A se reduz a B, podemos usar uma solução de A para resolver B.
	
	
	Se A é redutível a B e B é um problema indecidível, então A é um problema decidível.
	
	
	Converter um problema não resolvido em outro problema não resolvido.
	
	
	Se A se reduz a B, podemos usar uma solução de B para resolver A.
	Data Resp.: 04/12/2023 18:27:47
		Explicação: 
Pela definição de redutibilidade: Uma redução é um processo de conversão de um problema em outro problema resolvido de tal forma que a solução do segundo problema possa ser usada para resolver o primeiro problema.
	
	
	 
		
	
		8.
		Na classificação da hierarquia de Chomsky a gramática tipo 0 é uma gramática de estrutura de frase sem qualquer restrição. Dentro dessa hierarquia estão classificadas a linguagem recursiva e a linguagem recursivamente enumerável.  Acerca de suas características assinale a afirmação verdadeira.
 
	
	
	
	Uma linguagem recursiva é um subconjunto de uma linguagem recursivamente enumerável.
	
	
	Uma linguagem recursiva e uma recursivamente enumerável são equivalentes.
	
	
	Uma linguagem recursiva e uma recursivamente enumerável podem fazer um loop para sempre na entrada de uma máquina de Turing.
	
	
	Uma linguagem recursivamente enumerável é um subconjunto de uma linguagem recursiva.
	
	
	Uma linguagem recursiva é uma linguagem que não é aceita por uma Máquina de Turing.
	Data Resp.: 04/12/2023 18:28:24
		Explicação: 
As linguagens recursivas estão contidas no conjunto das linguagens recursivamente enumeráveis. Portanto, não são equivalentes. Uma linguagem recursiva é uma linguagem aceita por uma Máquina de Turing. Ambas as linguagens são aceitas por Máquinas de Turing. Quando uma linguagem é rejeitada a MT para, não entra em loop infinito.
	
	
	 
		
	
		9.
		Existem dois tipos principais de complexidade computacional para um algoritmo: complexidade de tempo e complexidadedo espaço. Nesse sentido, o que é falso para o problema da classe P?
	
	
	
	Ele contém todos os conjuntos nos quais a pertinência pode ser decidida por um algoritmo cujo tempo de execução é limitado por um polinômio.
	
	
	Em geral, a classe P contém todos os problemas que são resolvidos facilmente usando computadores.
	
	
	P é definido como o conjunto de todos os problemas de decisão para os quais existe um algoritmo que pode ser realizado por uma máquina de Turing não-determinística em tempo polinomial.
	
	
	O número de passos (ou tempo) necessários para completar o algoritmo é uma função polinomial de n.
	
	
	É computável por uma máquina de Turing determinística em tempo polinomial.
	Data Resp.: 04/12/2023 18:29:03
		Explicação: 
P é definido como o conjunto de todos os problemas de decisão para os quais existe um algoritmo que pode ser realizado por uma máquina de Turing determinística em tempo polinomial.
	
	
	 
		
	
		10.
		. Em síntese, qualquer programa de computador pode ser traduzido em uma máquina de Turing, e qualquer máquina de Turing pode ser traduzida para uma linguagem de programação de propósito geral. Acerca de suas características principais, qual item não faz parte do diagrama mecânico da máquina de Turing?
	
	
	
	Pilha.
	
	
	Cabeça de leitura-escrita.
	
	
	Controle finito.
	
	
	Fita de entrada.
	
	
	Direção de leitura..
	Data Resp.: 04/12/2023 18:29:07
		Explicação: 
O diagrama não contempla uma pilha. Todos os outros itens podem ser visualizados na figura do diagrama mecânico.