Aspectos Teoricos I E II

Páginas: 5 (1061 palavras) Publicado: 4 de maio de 2015
Pergunta 1
0,5 em 0,5 pontos



A máquina de Turing permite a computação de números naturais. Seja I um símbolo fixo não branco. Um número natural n pode ser representado em notação unária, pela cadeia de símbolos I, de comprimento n+1.
Considerando essa definição, selecione a representação unária para os números 0, 1 e 2, respectivamente, com I =1|.




Resposta Selecionada:
c. 
1, 11, 111d)     
Respostas:
a. 
a)     1 - 1, 1, 1+1
b)    

b. 
i, ii, iii
c)     

c. 
1, 11, 111
d)     

d. 
0, 1, 2
e)      

e. 
00, 01, 10




Pergunta 2
0 em 0,5 pontos



Para a classe das linguagens recursivas:




Resposta Selecionada:
d. 
Existe, pelo menos, uma máquina de estados finitos que sempre para qualquer que seja a entrada.
Respostas:
a. 
Não existe uma máquina de Turing que a reconheça. 

b. 
Existe, pelo menos, uma máquina de Turing reconhecedora que sempre para qualquer que seja a entrada.



c. 
Existe uma classe equivalente de linguagens dinâmicas.



d. 
Existe, pelo menos, uma máquina de estados finitos que sempre para qualquer que seja a entrada.

e. 
 Existe uma classe equivalente de linguagens irregulares.




Pergunta 3
0,5 em 0,5 pontos



“Apesar do aparente poder eversatilidade das variantes da Máquina de Turing [...], todas apresentam uma característica importante. O modelo de memória é sequencial, isto é, a fim de acessar uma informação armazenada em alguma localização, a máquina necessita primeiramente acessar, uma a uma, todas as células da memória localizadas entre a célula atual e aquela que se deseja acessar. Em contraste, os computadores reaisapresentam uma memória de acesso aleatório, onde cada célula da memória pode ser acessada em uma única etapa, se for adequadamente endereçada.”  (LEWIS, Papadimitrious). Considere as afirmações I  e II:
I - As máquinas de Turing de acesso aleatório são mais poderosas que as máquinas de Turing padrão.
PORQUE
II - Prova-se que a hipótese de Turing Church é verdadeira.
Assinale a alternativa correta:   Resposta Selecionada:
b. 
Ambas afirmações são falsas.
c)       
Respostas:
a. 
a)       Ambas afirmações, I e II, são verdadeiras e a  afirmação I é justificada pela afirmação II.
b)       

b. 
Ambas afirmações são falsas.
c)       

c. 
Ambas afirmações são verdadeiras, mas a afirmação I não pode ser justificada pela afirmação II.
d)      


d. 
 Apenas a afirmação I é verdadeira.e)       

e. 
Ambas afirmações são verdadeiras, mas a afirmação II é justificada pela afirmação I.
 




Pergunta 4
0,5 em 0,5 pontos



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:Resposta Selecionada:
d. 
 Problema da parada.
Respostas:
a. 
a)     Problema da análise lexicográfica.
b)    

b. 
Problema das máquinas universais.
c)     

c. 
Problema das entradas.
d)   


d. 
 Problema da parada.

e. 
a)     Problema da autoaplicação.




Pergunta 5
0,5 em 0,5 pontos



Uma linguagem aceita por uma máquina de Turing é dita:




Resposta Selecionada:
a. 
Recursivamenteenumerável.
Respostas:
a. 
Recursivamente enumerável.

b. 
Dinâmica.



c. 
Regularmente recursiva.



d. 
Regularmente adaptável.
 

e. 
Adaptável.




Pergunta 6
0,5 em 0,5 pontos








Resposta Selecionada:
e. 
A fita de trabalho de uma MT é passível de ser lida e escrita
 
Respostas:
a. 
a)     O cursor de acesso à fita de trabalho de uma máquina de Turing pode se deslocar apenas à direita.b)    

b. 
Apresenta a fita de trabalho limitada à direita.
c)     

c. 
Sempre, para qualquer que seja o conteúdo da fita de entrada e qualquer que seja a função de transição.
d)    

d. 
Apresenta um conjunto ilimitado de estados.
e)     

e. 
A fita de trabalho de uma MT é passível de ser lida e escrita
 




Pergunta 7
0,5 em 0,5 pontos



Considere as seguintes afirmações:
I – Como...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • ASPECTOS TEÓRICOS E CONCEITUAIS
  • Aspectos Teóricos Lista 1
  • Teorico LITERATURA BRASILEIRA I
  • Estagio i
  • Os Teóricos clássicos da Sociologia II
  • Texto Teorico I
  • Ética nas atividades informativas: aspectos teóricos”
  • Manutencao de software aspectos teoricos e praticos

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!