Sumários
Aula Teórica 17
23 novembro 2010, 10:00 • Maria Paula Antunes Abrantes Gouveia
Prova das seguintes proposições: (i) se A é um alfabeto então A^* é equipotente ao conjunto dos naturais, e se B é um subconjunto infinito de A^* então B é equipotente ao conjunto dos números naturais. (ii) o conjunto das linguagens sobre um certo alfabeto é equipotente ao conjunto das palavras binárias infinitas.
Aula Teórica 17
23 novembro 2010, 08:30 • Maria Paula Antunes Abrantes Gouveia
Prova das seguintes proposições: (i) se A é um alfabeto e B é um subconjunto infinito de A^* então B é equipotente ao conjunto dos números naturais. (ii)
o conjunto das linguagens sobre um certo alfabeto é equipotente ao conjunto das palavras binárias infinitas; (iii) o cardinal do
conjunto das palavras binárias infinitas é maior do que o cardinal do conjunto dos números naturais; (iv) o conjunto das máquinas de Turing é equipotente a
o conjunto dos números naturais.
Aula Prática 10
23 novembro 2010, 08:30 • Manuel Biscaia Martins
Exercício 2.10a da lista de exercícios para a aula prática 9. Exercício 1.3 e 1.2a da lista de exercícios para a aula prática 10.
Aula Prática 9
19 novembro 2010, 12:00 • Manuel Biscaia Martins
Exercícios 1.1a) b), 1.4 a) b), 2.3 e) e 2.4 b) da lista de exercícios para a aula prática 9 .
Aula Teórica 16
18 novembro 2010, 12:00 • Maria Paula Antunes Abrantes Gouveia
Enumerador. Exemplo: enumerador que enumera a linguagem sobre {1} constituída pelas palavras de comprimento ímpar. Máquinas de Turing não determinísticas. Proposição: Para cada máquina de Turing não determinística existe uma máquina de Turing equivalente. Revisões: funções bijectivas, conjuntos equipotentes, transitividade e simetria da equipotência. Proposição: existem linguagens que não reconhecidas por nenhuma máquina de Turing. Ideia geral da prova recorrendo a argumentos de cardinalidade.