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 algoritmo gené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,5 pontos

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

Respostas:
a.
I, II e III

b.
Apenas I

c.
Apenas II

d.
Apenas III