1° Lista de exercícios 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
8/9/16
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.
R: “Todos os cretenses são mentirosos”. Se assumirmos que a sentença é verdadeira, então quer dizer que o que os cretenses dizem é mentira, mas quando um cretense diz isso, torna a sentença falsa, desta forma, faz com que os cretenses não sejam mentirosos. E aí tem-se o paradoxo.
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.
R: Autológico é tudo que pode ser aplicado a si mesmo. A palavra no inglês “short” é autológica pois ela é uma palavra pequena, então é aplicável a si mesma. Porém no português “pequeno” não é uma palavra pequena, desta forma não pode ser usada como exemplo de adjetivo autológico.
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.
R: Para provar que não se pode programar a função “teorema” assumimos o contrário, ou seja, que podemos escrever um programa que testa se uma proposição é válida ou não. Usando este programa com função, mostramos como escrever a função “termina”. Como essa não pode ser implementada, a função “teorema” também não.
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.
R: A teoria dos tipos é usada para restringir que uma chamada de função possa passar a si própria como parâmetro, direta ou indiretamente. 
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ê.
Válida
Não Válida
Não Válida
 Não válida
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.
R: Or não é válida pois a funçãoor fornecida como argumento, é de dois argumentos, e a função f é de apenas um.
Cos não é valido pois é definido sobre o domínio dos números reais, e não de booleano. 
G não é válida pois g(g)=g(true)=true(true) e a tentativa de aplicar uma constante como uma função é absurda. (não há como gerar uma avaliação para true(true)).
Explique como as funções “hetero” e “termina” podem ser formuladas mesmo em uma linguagem estritamente tipada.
R: Podemos criar uma função análoga de “hetero” e “termina” que tem como primeiro parâmetro um item de dados comum que pode ser visto como uma representação de uma função, ao invés da própria função.
Dê a especificação da função “interpreta”.
R: interpreta( R ( f ), y ) = f ( y ).
Usando a função “interpreta”, reformule a função “hetero” sob o nome “hetero*”.
hetero*(z) = if termina*(z,z)
			then ( interpreta (z,z)
			else true
Mostre que, mesmo com a reformulação da função “hetero” sob a forma “hetero*”, é impossível responder a questão: “ ‘hetero*’ é heterológico?”
R: Considerando a pergunta, “hetero” é heterológico? Chegamos a:
hetero*(R(hetero*)) =
			if termina* (R(hetero*), R(hetero*))
			 then ( interpreta (R(hetero*), R(hetero*))
			 else true
Que pela função “interpreta” vai ser igual a ( interpreta ( R (hetero*), R (hetero*)).
	Chegando novamente ao resultado: 
hetero*( R (hetero*)) = (hetero*( R (hetero*))
e novamente esta contradição não pode ser resolvida pois hetero*( R (hetero*)) não termina.
Explique por que, com o subconjunto do Algol 60 dado em classe, não se pode programar seu próprio interpretador.
R: o Algol 60 era poderoso o suficiente e permitia a programação da função “termina”, com isso sabemos que a linguagem não é poderosa o suficiente para escrever 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# ?
R: Se uma linguagem permite escrever a função “termina” então não é possível escrever seu próprio compilador. 
�PAGE �
�PAGE �3�
_997819330.unknown
_997819340.unknown
_997808044.unknown
_997819253.unknown
_997808025.unknown