Sobre o Episódio
Neste episódio falarei um pouco sobre os conceitos matemáticos de compressibilidade, aleatoriedade e complexidade residentes na teoria da informação algorítmica desenvolvida principalmente pelos matemáticos Andrey Kolmogorov e Gregory Chaitin. Em particular, falarei sobre o problema do programa elegante de Chaitin, que nos permite concluir a incompletude em sistemas formais.
Figuras Citadas
- Andrey Kolmogorov (1903 - 1987)
- Gregory John Chaitin (1947 - )
- Michiel van Lambalgen (1954 - )
Obras de Destaque
- Livro: CHAITIN, G. — MetaMat: Em Busca do Ômega. Tradução de Gita K. Guinsburg. Editora Perspectiva, 2009.
- Artigo: LAMBALGEN, M. V. — Algorithmic Information Theory. The Journal of Symbolic Logic - Vol. 54, N. 4, Dec. 1989.
Outras Referências
- CASTI, John L. Five Golden Rules: Great Theories of 20th-Century Mathematics and Why They Matter (cap. 4 em particular). Wiley, 1996.
- CASTI, John L. Five More Golden Rules: Knots, Codes, Chaos and Other Great Theories of 20th-Century Mathematics (cap. 5 em particular). Wiley, 2000.
- CHAITIN, G. The Limits of Reason. Scientific American, March 2006.
- CHAITIN, G. The Halting Probability Omega: Irreducible Complexity in Pure Mathematics. Milan Journal of Mathematics, Vol. 75, 2007.
- MATOS, A. e MOREIRA, N. Introdução à complexidade de Kolmogorov. Faculdade de Ciências, Universidade do Porto.
- RAATIKAINEN, P. On Interpreting Chaitin's Incompleteness Theorem. Journal of Philosophical Logic 27: 569–586, 1998.
- RAATIKAINEN, P. Algorithmic information theory and undecidability. Synthese 123: 217–225, 2000.