Turmas - 1º Semestre de 2026
Turmas
1º Semestre de 2026

(IFFar, 2016) A Máquina de Turing, proposta por Alan Turing em 1936, é um mecanismo simples que formaliza a ideia de uma pessoa que realiza cálculos, usando um instrumento de escrita e um apagador. O modelo formal de uma Máquina de Turing é baseado em três componentes básicos: uma fita (utilizada para entrada, saída e rascunho); uma unidade de controle que possui cabeça de leitura e escrita sobre a fita; e um programa. Considerando as extensões da Máquina de Turing, a extensão que aumenta seu poder computacional é:

A Múltiplas fitas.

B Múltiplas cabeças.

C Não determinismo.

D Fita bidimensional infinita à esquerda e à direita.

E As extensões da Máquina de Turing não aumentam seu poder computacional.

(Marinha, 2011) O problema P versus NP é uma das maiores questões em aberto na ciência da computação. Em 2000, foi incluído entre os sete Problemas do Prêmio Millennium do Clay Mathematics Institute. Embora o consenso científico aponte que P ≠ NP, nenhuma demonstração formal foi estabelecida, mantendo a questão como um dos grandes desafios não resolvidos da matemática e da computação teórica. Em relação às classes de complexidade de problemas, assinale a opção correta.

A A classe de problemas em P consiste nos problemas que, dado um "certificado" de uma solução, é possível verificar se a solução é correta em tempo polinomial no tamanho da entrada.

B Dado que exista um problema NP-completo com solução em tempo polinomial, então todos os problemas em NP terão soluções em tempo polinomial.

C A classe de problemas NP consiste nos problemas que não pertencem à classe P, e por isso são problemas não "verificáveis" em tempo polinomial.

D A busca binária é um problema NP-completo, dependendo do tamanho da entrada.

E Um problema que está em P não estará em NP, exceto problemas NP-completos, os quais não foram demonstrados pela ciência.

(IFNMG, 2018) Na década de 1930, motivados pelos desafios de David Hilbert sobre decidibilidade matemática, Alonzo Church e Alan Turing lançaram as bases da teoria da computação. A Tese de Church-Turing formalizou a noção intuitiva de "cálculo efetivo", estabelecendo um consenso sobre o que é computável. No mesmo contexto, Turing propôs as máquinas universais, dispositivos teóricos capazes de emular qualquer outro processo computacional, antecipando a concepção dos computadores de propósito geral. Juntas, essas contribuições redefiniram a lógica matemática e delimitaram o alcance teórico da computação moderna. Sobre o conjunto de problemas que podem ser computados por Máquinas de Turing, é correto afirmar que:

A A demonstração da tese de Church-Turing permitiu compreender o que pode ser computado com diversos modelos de computação, como a máquina de Turing.

B Uma Máquina de Turing Universal não determinística pode resolver o Problema da Parada.

C Uma Máquina de Turing com duas fitas pode resolver o Problema da Parada em tempo polinomial.

D Uma Máquina com mais que duas Pilhas pode resolver o Problema da Parada em tempo polinomial.

E O Problema da Parada é um problema indecidível, cuja demonstração de impossibilidade algorítmica foi provada por Alan Turing em 1936.

(UFRPE, 2019) O cálculo lambda, desenvolvido por Alonzo Church na década de 1930, é um sistema formal que modela a computação por meio de funções e aplicação, servindo como um dos pilares teóricos da ciência da computação. Embora abstratos, seus conceitos — como funções anônimas, aplicação, abstração e redução — influenciaram diretamente o design de linguagens modernas. Linguagens funcionais como Haskell, Lisp e Scala adotam o paradigma lambda de forma explícita, enquanto recursos como closures, higher-order functions e expressões lambda estão presentes em linguagens multiparadigma como Python, JavaScript e Java. Assim, o cálculo lambda permanece vivo não apenas na teoria, mas como fundamento prático para programação modular, concisa e expressiva. Abaixo temos a descrição de uma função lambda em Python:

((lambda x: (lambda y: x**2 - y))(5))(4)

O valor resultante da expressão será:

A 4.

B 6.

C 11.

D 21.

E 29.

Richard Bird elaborou um formalismo para tratar a recursão por meio de esquemas de definição estruturada, tomando como base o resultado clássico da teoria da computabilidade de que a classe das funções recursivas coincide com a das funções computáveis. Essa equivalência, originalmente estabelecida por Church, Turing e Kleene, sustenta seu método de derivação e cálculo de programas, amplamente utilizado no paradigma funcional. Implemente um conjunto de funções recursivas, conforme o formalismo de Bird, que apresente o valor da constante matemática e utilizando a série 1/0! + 1/1! + 1/2! + 1/3! + ... + 1/n!. O valor de n será um número natural não negativo (n ≥ 0). Por exemplo, caso o valor de n seja 5, a resposta deverá ser 2,716667, ou seja, 1/0! + 1/1! + 1/2! + 1/3! + 1/4! + 1/5!.

A Máquina de Post, proposta por Emil Leon Post, é um autômato determinístico que utiliza uma estrutura de fila (FIFO) como memória de trabalho. Desenvolva uma Máquina de Post, definida sobre o alfabeto Σ = {0, 1, $}, capaz de calcular a disjunção exclusiva (XOR) entre duas sequências binárias. A entrada será fornecida no formato A$B, em que A e B representam os operandos e $ atua como delimitador. Após o processamento, a fila deve conter a sequência resultante da operação bit a bit (XOR). A seguir, são apresentados exemplos de entradas e os respectivos resultados esperados.

A Máquina com Pilhas é um autômato determinístico que utiliza uma estrutura de pilha (LIFO) como memória de trabalho. Contudo, é com duas pilhas que se atinge a equivalência à Máquina de Turing, cujo modelo de fita infinita e cabeça de leitura/escrita estabelece o padrão de computabilidade. Desenvolva um autômato com pilha, definido sobre o alfabeto Σ = {0, 1, $}, capaz de realizar a adição de dois números binários. A entrada será fornecida no formato A$B, em que A e B representam os operandos e $ atua como delimitador. Após o processamento, a máquina deve gerar a sequência correspondente à soma binária. A seguir, são apresentados exemplos de entradas e os respectivos resultados esperados.

Uma Máquina de Turing é um modelo computacional composto por uma fita infinita dividida em células, uma cabeça de leitura/escrita e um controle finito. A cada passo, a função de transição, formalizada como δ(q, σ) → (q’, σ’, D), determina o próximo estado q’, o símbolo a ser escrito σ’ e a direção do movimento da cabeça D ∈ {L, R}. Desenvolva uma Máquina de Turing definida sobre o alfabeto Σ = {0, 1, 2, 3, 4, 5, 6, 7} que aplique a operação de negação bit a bit (NOT) a cada dígito de um número octal fornecido como entrada. A entrada será uma sequência contígua de dígitos octais na fita. Após o processamento, a fita deve conter exclusivamente a sequência transformada, sem símbolos auxiliares residuais. A seguir, são apresentados exemplos de entradas e os respectivos resultados esperados.