Turmas - 1º Semestre de 2023O problema da parada para máquinas de Turing, ou simplesmente problema da parada, pode ser assim descrito: determinar, para quaisquer máquina de Turing M e palavra w, se M irá eventualmente parar com entrada w.
Mais informalmente, o mesmo problema também pode ser assim descrito: dado um algoritmo e uma entrada finita, decidir se o algoritmo terminará ou se executará indefinidamente.
Para o problema da parada,
a. Não existe uma Máquina de Turing que resolve o Problema da Parada, não importa quanto tempo seja disponibilizado.
b. Existe uma Máquina de Turing não determinística que resolve o Problema da Parada em tempo polinomial.
c. Existe uma Máquina de Turing não determinística que resolve o Problema da Parada em tempo exponencial.
d. Existe uma Máquina de Turing com múltiplas fitas que resolve o Problema da Parada em tempo polinomial.
e. Existe uma Máquina de Turing com múltiplas cabeças de leitura/gravação que resolve o Problema da Parada em tempo polinomial.
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 de leitura/gravação.
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.
Considere o seguinte termo do cálculo-lambda:
M = (λx. λy. x + y) ((λz. z * 3) 5) 6
Considerando a forma normal que resulta da redução completa do termo M, assinale a alternativa CORRETA.
a. 21
b. 23
c. 27
d. 28
e. 33
O problema P versus NP é o principal problema aberto da Ciência da Computação, possuindo enorme relevância em campos que vão deste a engenharia até a criptografia aplicada aos serviços militares e às transações comerciais e financeiras via internet. Entretanto, apesar da pergunta P = NP está sem resposta desde 1971, ano em que foi formulada, é possível provar que um problema pertence à classe P. Analise as assertivas a seguir:
A análise permite concluir que:
a. Apenas as assertivas I e II estão corretas.
b. Apenas as assertivas I e III estão corretas.
c. Apenas as assertivas II e III estão corretas.
d. Apenas as assertivas II e IV estão corretas.
e. Apenas as assertivas III e IV estão corretas.
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. Considerando as noções de solucionabilidade apresentadas, analise as assertivas que se seguem.
A análise permite concluir que:
a. Apenas as assertivas I e II estão corretas.
b. Apenas as assertivas I e III estão corretas.
c. Apenas as assertivas II e III estão corretas.
d. Apenas as assertivas II e IV estão corretas.
e. Apenas as assertivas III e IV estão corretas.
Autômatos com pilha diferem da definição normal de máquinas de estados finitos de duas maneiras: a) podem fazer uso da informação que está no topo da pilha para decidir qual transição deve ser efetuada e b) podem manipular a pilha ao efetuar uma transição. Autômatos com pilha escolhem uma transição analisando o símbolo atual na cadeia de entrada ou o topo da pilha, enquanto que máquinas de estados finitos convencionais apenas analisam o símbolo da cadeia de entrada. Desenvolver uma máquina com Pilhas, sobre o alfabeto {a, b} que verifique a quantidade de símbolos a's e b's presentes na entrada, aceitando as entradas cujas quantidades sejam diferentes.
Exemplos de entradas válidas: a, b, aa, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, aaab, aaba, ...
Exemplos de entradas inválidas: ε, ab, ba, aabb, abab, abba, baab, baba, bbaa, aaabbb, aababb, ...
M = ({a, b}, D)
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 a somatória dos n primeiros números ímpares.
Por exemplo, caso o valor de n seja 5, a função deverá retornar como resposta o valor 25, ou seja, 1 + 3 + 5 + 7 + 9.
Caso o valor de n seja inválido (menor ou igual a zero), a função deverá retornar como resposta o valor -1.
serie(n) = λn.(n <= 0 → -1, (n = 1 → 1, serie(n - 1) + (n * 2 - 1)))
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 {1, +}, que realize a adição unária de dois números fornecidos pelo usuário.
M = ({1, +}, {q0, q1, q2, q3, q4}, ∏, q0, {q4}, ∅, β, ⊗)
Ybadoo - Soluções em Software Livre • Copyright 2009/2024 • 