Turmas - 1º Semestre de 2024
Turmas
1º Semestre de 2024

(ENADE, 2021) Semelhante a um autômato finito mas com uma memória ilimitada e irrestrita, uma máquina de Turing é um modelo muito mais preciso de um computador de propósito geral. Uma máquina de Turing pode fazer tudo o que um computador real pode fazer, entretanto mesmo ela não pode resolver certos problemas. Num sentido muito real, esses problemas estão além dos limites teóricos da computação.

SIPSER, M. Introdução à Teoria da Computação. 2. ed. norte-americana. Cengage CTP, 2007 (adaptado).

Considere a seguinte máquina de Turing M que aceita apenas números binários palíndromos cujo comprimento é par.

Observação: no diagrama, as transições estão representadas no seguinte formato: "Leitura/Escrita Movimento", onde direção pode ser "D" (direita) ou "E" (esquerda). Exemplo: "0/B D" significa que o símbolo lido é "0", o símbolo escrito é "B" e o movimento é para a direita.

Considerando que o estado inicial de M é q0, que a sua fita se encontra inicializada com a entrada 110011 e infinitos símbolos "B" à esquerda e à direita, e que a cabeça de leitura encontra-se inicialmente no símbolo mais à esquerda da entrada, avalie as afirmações a seguir.

1. Após 4 movimentos de M, o conteúdo da fita, excluindo-se os símbolos "B", é "110011".
2. Após 8 movimentos de M, o conteúdo da fita, excluindo-se os símbolos "B", é "1001".
3. A máquina irá certamente travar em um estado de aceitação.
4. Existe um autômato com pilha que também aceita a linguagem de M.

É correto apenas o que se afirma em

a. I e II.

b. I e IV.

c. II e III.

d. I, III e IV.

e. II, III e IV.

(POSCOMP, 2017) Considere dois problemas de decisão PA e PB, sendo PA indecidível e PB decidível. Observe também dois problemas de decisão PC e PD, cuja decidibilidade é desconhecida. Suponha que seja possível construir de forma correta as seguintes reduções:

• de PA para PC.
• de PD para PA.
• de PD para PB.

Com base no cenário descrito, assinale a alternativa correta.

a. Não se pode afirmar nada sobre a decidibilidade dos problemas PC e PD.

b. Não se pode afirmar nada sobre a decidibilidade de PC, porém PD é decidível.

c. PC é indecidível e PD é decidível.

d. PC e PD são ambos indecidíveis.

e. PC é indecidível, contudo não se pode afirmar nada sobre a decidibilidade de PD.

(POSCOMP, 2019) Considere as seguintes afirmações sobre classes de problemas:

1. O problema de decisão CAM (caminho em grafo), descrito a seguir, pertence à classe de complexidade P.
   • Entrada: uma tripla (G, a, b) em que
   • G é um grafo
   • a e b são nodos de G
   • Pergunta: Existe caminho em G iniciando em a e terminando em b?
2. Um problema X pertence à classe de problemas NP-completos quando satisfaz às seguintes condições:
   • X pertence à classe NP, e
   • todo problema Y da classe NP pode ser reduzido em tempo polinomial a X.
3. Se um problema de decisão X pertence à classe P, então o complemento do problema X (problema com as mesmas instâncias que X, porém com as respectivas respostas invertidas) pertence à classe NP.

Quais estão corretas?

a. Apenas I.

b. Apenas III.

c. Apenas I e II.

d. Apenas II e III.

e. I, II e III.

Considere o seguinte termo do cálculo lambda:

M = (λa.λb.λc.a c b)(λd.d d) x y

Considerando a forma normal que resulta da redução completa do termo M, assinale a alternativa correta.

a. yy.

b. xyx.

c. xyy.

d. yyx.

e. yxy.

O objetivo do estudo da solucionabilidade de problemas é investigar a existência ou não de algoritmos que solucionem determinada classe de problemas, ou seja, investigar os limites da computabilidade e, consequentemente, os limites do que pode efetivamente ser implementado em um computador. Em relação ao estudo da solucionabilidade de problemas, analise as alternativas a seguir, assinalando V, se verdadeiras, ou F, se falsas.

( ) A união das Classes dos Problemas Solucionáveis e dos Não-Solucionáveis é o Universo de Todos os Problemas.

( ) Para qualquer algoritmo que solucione um Problema Solucionável, sempre existe pelo menos uma palavra de entrada que faz com que o algoritmo fique em loop.

( ) Os Problemas Parcialmente Solucionáveis não possuem solução total nem parcial.

( ) A Classe dos Problemas Parcialmente Solucionáveis contém propriamente a Classe dos Problemas Solucionáveis e parte da Classe dos Problemas Não-Solucionáveis.

A ordem correta de preenchimento dos parênteses, de cima para baixo, é:

a. F – F – V – V.

b. V – F – F – V.

c. V – V – F – F.

d. F – V – F – V.

e. V – F – V – F.

R. Bird desenvolveu um formalismo para o tratamento do conceito de recursão através de definições recursivas, os quais se verifica que a Classe das Funções com Definição Recursiva é a mesma Classe das Funções Computáveis. Implemente uma função recursiva, conforme as definições recursivas de Bird, que calcule o n-ésimo termo da sequência de Tribonacci.

tribonacci = λn.(n = 1 → 1, (n = 2 → 1, (n = 3 → 2, tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3))))

A Máquina de Turing consiste basicamente de três partes: uma fita, uma unidade de controle e uma função de transição. A fita é usada como um dispositivo de entrada, saída e memória. Ela é dividida em células que armazenam um símbolo de cada vez. A unidade de controle reflete o estado corrente da máquina. Possui uma unidade de leitura e gravação que pode deslocar-se para a esquerda (L) ou para a direita (R) da fita, podendo ler e/ou gravar um único símbolo em cada movimento. A função de transição comanda as leituras e gravações, o sentido de movimento da cabeça e define o estado corrente da máquina. Desenvolver uma máquina de Turing, sobre o alfabeto {x, y}, que duplique ao contrário a palavra fornecida pelo usuário. A seguir, são apresentados alguns exemplos de entradas possíveis de serem fornecidas pelo usuário com seus respectivos resultados.

M = ({x, y}, {q₀, q₁, q₂, q₃, q₄}, ∏, q₀, {q₄}, {X, Y}, β, ⊗)

Uma Máquina de Post, assim denominada em honra a Emil Leon Post, é um autômato determinístico, baseado na estrutura de dados de tipo fila com um símbolo auxiliar. Desenvolver uma máquina de Post, sobre o alfabeto {0, 1}, que verifique se os números binários fornecidos pelo usuário são números binários pares. A seguir, são apresentados alguns exemplos de entradas possíveis de serem fornecidas pelo usuário com seus respectivos resultados.

M = ({0, 1}, D, #)