questionario_1

Prévia do material em texto

Assinale a alternativa incorreta:
Sempre existe uma máquina de Turing que detecta um loop
infinito.
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 =*
*, **, ***
←
Revisar envio do teste: QUESTIONÁRIO UNIDADE I – D561_... https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_i...
1 of 4 03/05/2019 21:16
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:
I, II e III
Para a classe das linguagens recursivas:
Existe, pelo menos, uma máquina de Turing reconhecedora que
sempre para qualquer que seja a entrada.
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:
Problema da parada.
Revisar envio do teste: QUESTIONÁRIO UNIDADE I – D561_... https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_i...
2 of 4 03/05/2019 21:16
Assinale a alternativa incorreta:
Não existem problemas não solucionáveis.
“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:
Ambas afirmações são falsas.
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
Revisar envio do teste: QUESTIONÁRIO UNIDADE I – D561_... https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_i...
3 of 4 03/05/2019 21:16
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: 
I, II e III
É um exemplo de problema não solucionável:
Detector universal de loops.
 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 .
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 .
Assinale a alternativa correta:
Se X existe, então T não existe.
Revisar envio do teste: QUESTIONÁRIO UNIDADE I – D561_... https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_i...
4 of 4 03/05/2019 21:16