Usando a Complexidade de Kolmogorov para resolver o Problema da Parada
Assumimos que o leitor esteja familiarizado com as noções de Indecidibilidade, Reduções de Turing, Complexidade de Kolmogorov, Problema da Parada e assuntos relacionados. A prova de que a incomputabilidade da Complexidade de Kolmogorov implica a indecidibilidade do Problema da Parada pode ser encontrada em muitas palestras, notas e livros; geralmente, a prova assume que o Problema da Parada é decidível e deriva a computabilidade da complexidade de Kolmogorov, que é uma contradição. Em outras palavras, dado um oráculo para o Problema da Parada, podemos calcular a complexidade de Kolmogorov de uma cadeia x. Mas também podemos derivar a incomputabilidade da Complexidade de Kolmogorov a partir da indecidibilidade do Problema da Parada; a prova é "menos popular", mas mesmo assim pode ser encontrada depois de algumas pesquisas no Google. Por exemplo, o relatório técnico: Gregory J. Chaitin, Asat Arslanov e Cristian Calude: Program-size Complexity Computes the Halting Prob...