Sobre o Episódio
Neste episódio falarei um pouco sobre os limites teóricos da computação. Mostrarei que existem problemas matemáticos que não podem ser resolvidos computacionalmente. O mais interessante é que este fato é independente da capacidade física — velocidade, memória — de qualquer computador (clássico).
Durante a discussão, fazemos menção a duas figuras centrais e fundadoras da ciência da computação teórica: Alan Turing (1912–1954) e Alonzo Church (1903–1995).
Referências Citadas
- FEOFILOFF, Paulo. Busca de uma palavra em um texto. Notas de aula.
- PORTO DA SILVEIRA, J. F. Problema do caixeiro viajante.
- HOPCROFT, J. E.; MOTWANI, R.; ULLMAN, J. D. Introduction to automata theory, languages and computation. Addison-Wesley; 2nd edition, 2001.