Aula Teórica 12

8 novembro 2011, 08:30 • Maria Paula Antunes Abrantes Gouveia

Computabilidade: motivação. Postulado de Church-Turing. Conjuntos equipotentes, conjuntos numeráveis. Proposição: os conjuntos N, Z e Q são numeráveis. Prova dos dois primeiros casos. Proposição: o conjunto {0,1}^* é numerável. Prova da proposição. Extensão ao caso de um alfabeto Sigma qualquer. Proposição: Seja Sigma um alfabeto e seja A um subconjunto infinito de Sigma^*. O conjunto A é numerável. Prova da proposição. Teorema de Cantor (enunciado e prova).