ATC ASPECTOS TEORICOS DA COMPUTAÇÃO

Prévia do material em texto

Resposta Selecionada:
e.
A fita de trabalho de uma MT é passível de ser lida e escrita
Pergunta 2
A hipótese de Turing-Church sugere:
Resposta
Selecionada:
e.
Qualquer outra forma de expressar algoritmos terá no máximo a mesma
capacidade computacional da máquina de Turing
Pergunta 3
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, 111
Pergunta 4
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.
Pergunta 5
0,5 em 0,5 pontos
0,5 em 0,5 pontos
0,5 em 0,5 pontos
0,5 em 0,5 pontos
Revisar envio do teste: Questionário Unidade I (2017/1) &ndash... https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_i...
2 de 4 18/03/2017 16:15
Considere as seguintes afirmações:
I - Uma linguagem L é aceita por uma máquina de Turing com k fitas, m dimensões, n cabeçotes de
leitura e gravação por fita se, e somente se, ela é aceita por uma máquina de Turing determinística
com uma fita infinita em apenas um sentido e um cabeçote de leitura e gravação.
II - O conjunto de todos os programas que param para uma dada entrada é um conjunto
recursivamente enumerável.
III – A tese de Church Turing iguala uma função computável por algoritmo com uma função
computável por Turing.
Está correta a alternativa: 
Resposta Selecionada: a. I, II e III
Pergunta 6
Para a classe das linguagens recursivas:
Resposta
Selecionada:
b.
Existe, pelo menos, uma máquina de Turing reconhecedora que sempre para
qualquer que seja a entrada.
Pergunta 7
Uma linguagem aceita por uma máquina de Turing é dita:
Resposta Selecionada: a. Recursivamente enumerável.
Pergunta 8
“Apesar do aparente poder e versatilidade 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 reais apresentam 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.
0,5 em 0,5 pontos
0,5 em 0,5 pontos
0,5 em 0,5 pontos
Revisar envio do teste: Questionário Unidade I (2017/1) &ndash... https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_i...
3 de 4 18/03/2017 16:15
Sábado, 18 de Março de 2017 17h12min13s BRT
Pergunta 9
Não se trata de uma máquina equivalente à máquina de Turing:
Resposta Selecionada:
b.
Autômato com uma pilha.
Pergunta 10
Considere as seguintes afirmações:
I – Como algoritmos podem representar máquinas de Turing e vice-versa, isso 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á correta a alternativa:
Resposta Selecionada: d. I, II e III
0,5 em 0,5 pontos
0,5 em 0,5 pontos
Revisar envio do teste: Questionário Unidade I (2017/1) &ndash... https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_i...
4 de 4 18/03/2017 16:15