Lista de Exercícios 1 - Teoria da computação

Prévia do material em texto

Universidade Federal de Viçosa
Centro de Ciências Exatas e de Tecnologia
Departamento de Informática
INF130 – Teoria da Computação
23/10/06
1ª Lista de Exercícios
Explique por que é necessário, no paradoxo de Epimênides (ou do mentiroso), a frase ser dita por um cretense (ou ser expressa na primeira pessoa) para que o paradoxo seja estabelecido.
No artigo original, em inglês, sobre incomputabilidade, o adjetivo short foi usado por HOARE e ALLISON como exemplo de adjetivo autológico. Você concorda que, na tradução literal para o português, o adjetivo pequeno continue sendo considerado autológico? Explique sua resposta.
Um aluno da turma 2001 de INF130 ficou entusiasmado ao apresentar uma forma de decidir a terminação de qualquer programa imperativo escrito em uma linguagem de programação tipo Pascal, baseado na regra de prova de terminação do comando while. A regra de prova de terminação do comando while pode ser encontrada em qualquer texto que trata sobre semântica axiomática de linguagens imperativas, como, por exemplo, em:
WIRTH, Niklaus. Programação sistemática em Pascal. Rio de Janeiro: Campus, 1978. Cap. 6.
Explique em que ponto o aluno se equivocou ao achar que a regra de prova de terminação do comando while serviria de justificativa na demonstração da parada da execução do comando while e, conseqüentemente, de qualquer programa escrito em uma linguagem imperativa de alto nível, refutando assim o teorema fundamental da incomputabilidade como apresentado por HOARE e ALLISON.
Prove que a função “teorema”, como especificada em classe, é impossível de ser programada em qualquer linguagem tão ou mais poderosa que o Lisp.
Diga o que tem sido usado em projetos de linguagens para restringir que uma chamada de função possa passar a si própria como parâmetro.
Seja a função booleana 
 de apenas um parâmetro f que por sua vez é uma função de booleano em booleano. Diga se cada uma das seguintes chamadas é válida ou inválida em Algol 68. Caso seja inválida, explique por quê.
onde ‘not’ é o operador de negação lógica, ‘or’ é o operador de disjunção lógica e ‘cos’ é a função real co-seno.
Explique como as funções “hetero” e “termina” podem ser formuladas mesmo em uma linguagem estritamente tipada.
Dê a especificação da função “interpreta”.
Usando a função “interpreta”, reformule a função “hetero” sob o nome “hetero*”.
Mostre que, mesmo com a reformulação da função “hetero” sob a forma “hetero*”, é impossível responder a questão: “ ‘hetero*’ é heterológico?”
Explique por que, com o subconjunto do Algol 60 dado em classe, não se pode programar seu próprio interpretador.
A empresa de desenvolvimento de software Micosoft está tentando passar-lhe mais um mico, ou melhor, um compilador de uma nova linguagem, A#, projetada pelos seus técnicos, com a seguinte propaganda: “… a linguagem A# é tão poderosa que é capaz de implementar a função ‘termina’ com as especificações dadas…” como na classe de INF130. O que você pode concluir do poder expressivo da linguagem A# anunciada pela empresa? Você pagaria o mico, digo, o compilador A# ?
�PAGE �
�PAGE �2�
_997819330.unknown
_997819340.unknown
_997808044.unknown
_997819253.unknown
_997808025.unknown