Baixe o app para aproveitar ainda mais
Prévia do material em texto
• Pergunta 1 O diagrama de transição de estados, ou diagrama de máquina de estados, é uma representação do estado ou situação em que um objeto pode se encontrar no decorrer da execução de processos de um sistema. Observe a imagem a seguir, que apresenta uma ilustração de um diagrama de transição a fim de exemplificar o funcionamento da máquina de Turing: Figura – Exemplo de um diagrama de transição Fonte: Adaptada de Passos (2018). #PraCegoVer : a imagem está dividida em três círculos, em que dois retornam para a direita e uma seta para esquerda, finalizando com uma seta reta para a esquerda, no q4, e ela está dividida com setas retas, para esquerda e para a direita, que fazem a ligação desses círculos. PASSOS, Y. T. dos P. Máquinas de Turing. Slideshare , 2018. Disponível em: https://www.slideshare.net/yuripassos58/01-maquinas-de-turing. Acesso em: 27 jun. 2021. Considerando a imagem apresentada, ilustrada a fim de apresentar o diagrama de transição, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F para a(s) Falsa(s). I. ( ) O q0 é o estado inicial e M entra toda vez que retorna ao 0 restante mais à esquerda. II. ( ) O q1 indica que deve ir à direita enquanto for 0 ou y, troca 1 por y e anda à direita para encontrar novos ys. III. ( ) O q2 volta para a direita até encontrar o y, andando à direita, enquanto for x ou y. IV. ( ) O q3 lê ys até encontrar um b à direita. Assinale a alternativa que apresenta a sequência correta. Resposta Correta: V, V, F, V. Comentário da resposta: Sua resposta está incorreta. A sequência está incorreta, pois a afirmativa III é falsa, porque, para definir formalmente o comportamento dessa transição, é necessário entender a definição da função programa e usar como argumento um estado e uma palavra, logo, o q2 não volta para a direita até encontrar o y, andando à direita, enquanto for x ou y. • Pergunta 2 A máquina de Turing é um dispositivo teórico, conhecido como máquina universal, concebido pelo matemático britânico Alan Turing e que foi fundamental para o desenvolvimento da teoria da computação, tendo em vista ter sido o marco que deu origem aos primeiros dispositivos computacionais. Considerando o texto apresentado, que aborda a implementação de uma das primeiras máquinas de Turing sob a ótica de sua essencialidade, analise as afirmativas a seguir e assinale V para a(s) verdadeira(s) e F para a(s) falsa(s). I. ( ) A máquina de Turing foi inicialmente implementada como uma máquina automatizada capaz de calcular qualquer algoritmo e processar instruções. II. ( ) Podemos dividir a aplicabilidade da máquina de Turing em problemas solucionáveis e problemas não solucionáveis ou não processáveis. III. ( ) Para a máquina de Turing, uma das características de um algoritmo processável é ter uma descrição infinita e executável. IV. ( ) Para a máquina de Turing, uma das características de um algoritmo processável é ter uma sequência de passos discretos. Assinale a alternativa que apresenta a sequência correta. Resposta Correta: V, V, F, V. Comentário da resposta: Sua resposta está incorreta. A sequência está incorreta, pois a afirmativa III é falsa. Para a máquina de Turing, uma das características de um algoritmo processável é ter uma descrição finita e executável, e não infinita e executável, uma vez que, se ela fosse infinita, teríamos um loop sem solução, logo, somente a alternativa III apresenta erro ao definir uma descrição infinita. • Pergunta 3 Leia o trecho a seguir: “Uma consequência importante do estudo das linguagens recursivamente enumeráveis é que, computacionalmente falando, existem mais problemas não computáveis (para os quais não existem máquinas de Turing capazes de processá-los) do que problemas computáveis (caso contrário)”. MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 2015. p. 169. A partir do apresentado, analise as asserções a seguir e a relação proposta entre elas. I. A classe das linguagens recursivamente enumeráveis inclui algumas linguagens, para as quais é impossível determinar mecanicamente se uma palavra não pertence à linguagem. Pois: II. Um problema computável sempre será um problema parcialmente solucionável, todavia, há vários cenários, em que existem problemas não computáveis, aos quais a máquina de Turing não se aplica. A seguir, assinale a alternativa correta. Resposta Correta: A asserção I é uma proposição verdadeira, e a asserção II é uma proposição falsa. Comentário da resposta: Resposta correta. A alternativa está correta, pois a asserção I é uma proposição verdadeira, já que, de fato, a classe das linguagens recursivamente enumeráveis inclui algumas linguagens para as quais é impossível determinar, mecanicamente, se uma palavra não pertence à linguagem. A asserção II é uma proposição falsa, porque um problema computável pode ser um problema parcialmente solucionável, logo, nem sempre será parcialmente solucionavel, uma vez que existem problemas não computáveis, aos quais a máquina de Turing não se aplica. • Pergunta 4 Apesar da sua simplicidade, o modelo máquina de Turing possui, no mínimo, a mesma capacidade, ou seja, o mesmo poder computacional de qualquer computador de propósito geral. O ponto de partida de Turing foi analisar a situação, a partir da qual uma pessoa, com um instrumento de escrita e um apagador, poderia realizar cálculos em uma folha de papel e, a partir disso, derivar resultados lógicos. Assinale a alternativa que indica a sequência correta para essa operação simples. Resposta Correta: A pessoa é capaz de observar e alterar o símbolo de apenas um quadrado de cada vez, bem como de transferir sua atenc ̧ão para somente um dos quadrados adjacentes. Comentário da resposta: Resposta correta. A alternativa está correta, pois, quando for encontrada alguma representação satisfatória no resultado, encontra-se a resposta desejada, e a pessoa finalizará seus cálculos, e isso viabilizará esse procedimento, por isso, essas hipóteses são aceitáveis. • Pergunta 5 Leia o trecho a seguir: “O modelo abstrato de computação, proposto por Turing em 1936 e conhecido como máquina de Turing, tinha como objetivo explorar os limites da capacidade de expressar soluções de problemas. Trata-se de uma proposta de definição formal da noção intuitiva de algoritmo. Diversos outros trabalhos, como Cálculo Lambda e funções recursivas, resultaram em conceitos equivalentes ao da máquina de Turing”. MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 2015. p. 114. A respeito da hipótese de Church, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F para a(s) Falsa(s). I. ( ) A hipótese de Church apresenta-se demonstrável como na noção computável ou na função de algoritmo. II. ( ) A capacidade de computação representada pela máquina de Turing é o limite máximo que pode ser atingido por qualquer dispositivo de computação. III. ( ) A hipótese de Church não consegue afirmar que qualquer outra forma de expressar algoritmos terá a mesma capacidade computacional da máquina de Turing. IV. ( ) A nomenclatura hipótese de Church não é assumida como verdadeira na ciência da computação. Assinale a alternativa que apresenta a sequência correta. Resposta Correta: F, V, F, F. Comentário da resposta: Resposta correta. A sequência está correta, porque, em termos de capacidade de expressar computabilidade, que é conhecido como tese de Church ou tese de Turing- Church, os trabalhos elaborados são um forte reforço nesse sentido, e a capacidade de computação representada pela máquina de Turing é o limite máximo que pode ser atingido. • Pergunta 6Leia o excerto a seguir: “Uma máquina de Turing é um autômato cuja fita não possui tamanho máximo e pode ser usada, simultaneamente, como dispositivo de entrada, como dispositivo de saída e como memória de trabalho. Partindo desse pressuposto, temos que as linguagens recursivamente enumeráveis ou linguagens tipo 0, por sua vez, são fundamentais na aplicabilidade da máquina de Turing. MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 2015. p. 167. A respeito da teoria das linguagens recursivas e de sua aplicabilidade quanto a máquina de Turing, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F para a(s) Falsa(s). I. ( ) Podemos considerar que, segundo a hipótese de Church, a máquina de Turing é o dispositivo computacional mais geral. II. ( ) Algumas classes de linguagens podem representar as linguagens recursivamente enumeráveis usando um formalismo axiomático. III. ( ) Uma gramática irrestrita possuirá qualquer restrição quanto à forma das produções, conforme o modelo de Turing. IV. ( ) O formalismo gramatical não possui o mesmo poder computacional que o formalismo da máquina de Turing. Assinale a alternativa que apresenta a sequência correta. Resposta Correta: V, V, F, F. Comentário da resposta: Resposta correta. A sequência está correta. De fato, a hipótese ou modelo de Church, ao tratar da máquina de Turing, tem ela como o dispositivo computacional mais geral e algumas classes de linguagens podem receber a designação de recursivamente enumeráveis, tratando-se, então, de um formalismo axiomático, essa é a definição científica por trás do formalismo axiomático. • Pergunta 7 Na matemática, uma equação diofantina é uma equação polinomial que permite que duas ou mais variáveis assumam apenas valores inteiros. Uma equação linear diofantina é uma equação entre duas somas de monômios de grau zero ou um. Observe, a seguir, a equação diofantina: Diofantinas ax + by = c Solução inteira Considerando o exposto, a fim de apresentar o funcionamento da equação diofantina, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F para a(s) Falsa(s). I. ( ) Equações diofantinas são equações algébricas com coeficientes inteiros. II. ( ) Problemas diofantinos têm menos equações que variáveis desconhecidas e se resumem a achar soluções inteiras que deverão funcionar corretamente para todas as equações. III. ( ) Ao se desenvolver um conhecimento sobre as equações diofantinas lineares em duas ou mais variáveis não será possível solucionar problemas. IV. ( ) Dada uma equação diofantina P(a0,...,an) = 0, em que P é um polinômio com coeficientes inteiros, quer-se saber se existe um procedimento efetivo que seja capaz de determinar, em um tempo finito, se suas raízes são inteiras. Assinale a alternativa que apresenta a sequência correta. Resposta Correta: V, V, F, V. Comentário da resposta: Sua resposta está incorreta. A sequência está incorreta, pois a afirmativa III é falsa. Em uma linguagem um pouco mais técnica, elas definem uma curva algébrica, uma superfície algébrica ou um objeto mais comum e, então, pede-se para que sejam encontradas as soluções. Logo, uma equação diofantina é uma equação polinomial que permite que duas ou mais variáveis assumam apenas valores inteiros. • Pergunta 8 Leia o trecho a seguir: “Com o passar do tempo vários modelos surgiram, e a máquina de Turing é o modelo mais basilar da teoria da computação, porém, apesar das várias modificações, observou-se que, ao mudar as variáveis, os outros modelos não se mostraram diferentes em relação à máquina de Turing”. MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 2015. p. 114. Considerando o excerto apresentado sobre a definição do modelo autômato com múltiplas pilhas, analise as afirmativas a seguir: I. As combinações de múltiplas modificações na máquina de Turing aumenta o poder computacional da máquina de Turing. II. Trata-se de uma nítida proporção entre a máquina de Turing e as pilhas. III. Adicionar um maior número de pilhas não gerará aumento da eficácia computacional. IV. A definição básica é que a máquina de Turing permite que a fita seja limitada dos dois lados. Está correto o que se afirma em: Resposta Correta: II e III, apenas. Comentário da resposta: Resposta correta. A alternativa está correta, pois, conforme citado no estudo das linguagens livres do contexto, o poder computacional do autômato com duas pilhas é o mesmo da máquina de Turing, por definição. Dessa forma, temos uma nítida equivalência entre ambos. Logo, com um maior número de pilhas, não se terá aumento na capacidade computacional, o que faz com que as alternativas II e III estejam corretas. • Pergunta 9 Leia o trecho a seguir: “O teorema da não completude apresenta que todas as formulações axiomáticas consistentes da teoria dos números incluem proposições indecidíveis, ou seja, que não podem ser provadas como verdadeiras ou como falsas. Portanto, se um sistema formal é consistente, ele não pode ser completo, e a consistência dos axiomas não pode ser provada usando o próprio sistema formal”. MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 2015. p. 144. Considerando o excerto apresentado sobre o teorema da não completude e suas formulações, que não poderiam ser provadas como verdadeiras ou como falsas, analise as afirmativas a seguir. I. O teorema da não completude é capaz de provar todas as verdades sobre as relações aritméticas. II. O teorema da não completude estabelece limitação própria a quase todos os sistemas axiomáticos, exceto aos mais triviais. III. O teorema da não completude pode ser usado para manipular qualquer máquina de Turing de única fita e, assim, a princípio, qualquer computador. IV. Existe uma derivação formal do teorema da não completude, tal derivação é uma lista finita de passos, em que cada passo é obtido por meio de um axioma ou de regras de inferência básicas aplicadas a passos anteriores. A seguir, assinale a alternativa correta. Resposta Correta: I e II, apenas. Comentário da resposta: Sua resposta está incorreta. A alternativa está incorreta, pois as alternativa III e IV indicam que o teorema da completude conceitua regras de inferência da lógica de primeira ordem completas, no sentido de que nenhuma nova regra de inferência é necessária para derivar todas as fórmulas logicamente válidas, o que não é correto, na realidade, o que ocorre é o inverso. • Pergunta 10 O problema de decisão, o qual questionava a existência de um procedimento mecânico (baseado no trabalho de Gottfried Leibniz, que buscava um mecanismo mecânico de manipulação de fórmulas) capaz de decidir se, dado um enunciado (proposição) da lógica de primeira ordem, ele seria válido ou não, em um tempo finito. Assinale a alternativa que indica a definição do problema de decisão. Resposta Correta: Alan Turing transforma-o em um problema de parada em sua máquina. Comentário da resposta: Resposta correta. A alternativa está correta, pois a definição do problema de decisão se dá por meio de matemáticos que o definem como um sistema formal. Pretendia-se obter uma teoria aritmética como um sistema formal consistente e completo, o que, infelizmente, não foi possível, segundo David Hilbert.
Compartilhar