Sumários
Aula Prática 9
18 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, 10:30 • Maria Paula Antunes Abrantes Gouveia
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: o conjunto {0,1}^* é equipotente ao conjunto do números naturais. Prova da proposição recorrendo à representação binária dos naturais. Proposição: A^* é equipotente ao conjunto dos naturais, para cada alfabeto A.
Proposição: existem linguagens que não reconhecidas por nenhuma máquina de Turing. Ideia geral da prova recorrendo a argumentos de cardinalidade.
Aula Prática 9
18 novembro 2010, 08:30 • Maria Paula Antunes Abrantes Gouveia
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 Prática 9
17 novembro 2010, 08:30 • Maria Paula Antunes Abrantes Gouveia
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 Prática 9
16 novembro 2010, 12:00 • Maria Paula Antunes Abrantes Gouveia
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 .