atc unidade1111

atc unidade1111

?Pergunta 1
0,5 em 0,5 pontos
Considere as seguintes afirmações:
I – É provado ser insolúvel o seguinte o problema: “Dadas duas gramáticas gerais arbitrárias G1 e G2, determinar se as linguagens geradas por G1 e G2 são iguais”.
II – É provado ser insolúvel o seguinte problema: “Dadas duas máquinas de Turing M1 e M2 arbitrárias, elas param com as mesmas entradas”.
III – Não existe algoritmogenérico que sempre pare capaz de comparar dois arbitrários compiladores de linguagens livres do contexto e verificar se são equivalentes, ou seja, se de fato, reconhecem a mesma linguagem.
Está correta a alternativa:
Resposta Selecionada:
e.
I, II e III
Respostas:
a.
Apenas I e II

b.
Apenas I e III

c.
Apenas I

d.
Apenas II

e.
I, II e III

Pergunta 2
0,5 em 0,5pontos

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 é umconjunto 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
Respostas:
a.
I, II e III

b.
Apenas I

c.
Apenas II

d.
Apenas III

e.
Apenas I e III

Pergunta 3
0,5 em 0,5 pontos

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 daverificação formal de programas é insolúvel no seu caso geral.

Está correta a alternativa:

Resposta Selecionada:
d.
I, II e III
Respostas:
a.
Apenas I

b.
Apenas I e II

c.
Apenas II e III

d.
I, II e III

e.
Apenas II

Pergunta 4
0 em 0,5 pontos

“Apesar do aparente poder e versatilidade das variantes da Máquina de Turing […], todas apresentam uma característicaimportante. 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 únicaetapa, 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:
c.
Ambas afirmações são verdadeiras, mas a afirmação I não pode serjustificada pela afirmação II.
Respostas:
a.
Ambas afirmações, I e II, são verdadeiras e a afirmação I é justificada pela afirmação II.

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

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

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

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

Pergunta 5
0,5 em 0,5 pontos

Assinale a alternativa incorreta:

Resposta Selecionada:
e.
Sempre existe uma máquina de Turing que detecta um loop infinito.
Respostas:
a.
Todo problema solucionável é parcialmente solucionável.

b.
Existem problemas não solucionáveis que possuem solução parcial.

c.
Os problemas completamente insolúveis não possuem solução total nem…