sábado, 16 de maio de 2015

Chaitin, mais uma vez!

Orsoni, muito obrigado pelo belo presente. Fantástico artigo. Gostei muito da elaboração teórica do conceito de randomness, e ligação com complexidade, com teoria dos algoritmos, e finalmente com teoria da informação. Tudo isso saindo do teorema de Gödel! Maravilha. E ainda dizem que o teorema de Gödel foi um desastre para muitos matemáticos. Ao contrário, pode-se dizer que a computação, via Turing, foi consequência do teorema de Gödel.

[...], tem mais conexões incríveis. Chaitin se refere a Kolmogorov, que lá atrás definiu uma máquina, máquina de Kolmogorov-Uspensky, equivalente à máquina de Turing. Recentemente lendo sobre programação funcional encontrei material sobre teoria dos tipos (como tipos de dados em uma linguagem de programação), baseados no trabalho de um lógico sueco Per Martin-Löf, que foi discípulo de Kolmogorov.

Tudo se liga!