Questoes Prova Teoria da Computação UFRGS

Prévia do material em texto

<p>Questão 2 Correto Determine se cada uma das seguintes afirmações é verdadeira ou falsa: Atingiu de ,00 1. conjunto a N, b E N, N} é infinito e FALSE Marcar 2. termo lambda possui forma normal. FALSE 3. Apesar da Máquina Norma armazenar e operar sobre números naturais, é possível representar o tipo de dado "booleano" e definir a operação "OU lógico" (or) por meio de codificações numéricas adequadas. TRUE 4. variável b ocorre livre no termo lambda TRUE 5. A variante da Máquina Norma com 5 registradores de trabalho possui poder computacional estritamente maior que a Máquina Norma com somente 3 registradores de trabalho FALSE 6. operador de ponto fixo Y permite a definição de funções recursivas no Cálculo Lambda. Usando esse recurso, podemos construir em cálculo lambda um simulador de Máquina Norma, provando que poder computacional do Cálculo Lambda é igual ou maior do que poder da Máquina Norma. TRUE 7. Um programa universal U recebe como entrada um par (p,x), sendo um programa codificado e x uma entrada para p, sendo que tal programa universal U simula rodando sobre x e devolve mesmo valor de saída ou entra em loop, a depender do comportamento de p sobre x TRUE 8. Suponha uma máquina chamada Zorma, similar à Norma porém com a principal diferença dos registradores armazenando números inteiros ao invés de naturais. Ao compararmos poder computacional de Zorma e Norma (isto é, conjunto de funções computáveis por ambas), concluímos que Zorma é mais poderosa pois permite definir funções de inteiros para inteiros, em contraste a Norma que só permite funções de naturais para naturais. FALSE 9. Se a máquina M1 simula a máquina M2, e a máquina M2 simula a máquina M3, consequentemente podemos construir uma forma da máquina M1 simular a máquina M3. Em outras palavras, a relação de simulação entre máquinas é transitiva. TRUE 10. resultado da FALSE</p>