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 Problem. O Boletim do EATCS 57 (1995) contém duas provas diferentes, e o grande livro de Li, Ming, Vitányi, Paul M.B; An Introduction to Kolmogorov Complexity and Its Applications apresenta-a como um exercício (com uma sugestão de como resolvê-la, creditado a P. Gács por W. Gasarch em uma comunicação pessoal em 13 de fevereiro de 1992). Aqui nós damos uma prova extensa, com mais detalhes, de que o Problema de Parada pode ser decidido usando um oráculo que calcula a complexidade de uma cadeia de caracteres de Kolmogorov, ou seja, que o Problema de Parada é Turing redutível à Complexidade de Kolmogorov.
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 Problem. O Boletim do EATCS 57 (1995) contém duas provas diferentes, e o grande livro de Li, Ming, Vitányi, Paul M.B; An Introduction to Kolmogorov Complexity and Its Applications apresenta-a como um exercício (com uma sugestão de como resolvê-la, creditado a P. Gács por W. Gasarch em uma comunicação pessoal em 13 de fevereiro de 1992). Aqui nós damos uma prova extensa, com mais detalhes, de que o Problema de Parada pode ser decidido usando um oráculo que calcula a complexidade de uma cadeia de caracteres de Kolmogorov, ou seja, que o Problema de Parada é Turing redutível à Complexidade de Kolmogorov.
Usando a Complexidade de Kolmogorov para resolver o Problema da Parada
O Problema da Parada é representado pela linguagem HALT:
HALT = {⟨M,x⟩ ∣ M é uma máquina de Turing que para sobre a entrada x}
Seja Tmax(n) o tempo de execução mais longo entre as Máquinas de Turing de tamanho n que param sobre uma fita vazia; e seja BBn a Máquina de Turing que atinge Tmax(n). Note que Tmax é simplesmente uma variante da função Busy Beaver, na qual a pontuação é o número de passos necessários para parar. A partir do par dado ⟨M, x⟩, podemos construir M' que sobre a fita vazia escreve x e simula M(x), e que |M'| = n. Claramente, se M' do tamanho n ainda estiver sendo executado após as etapas de Tmax(n), então isso rodará para sempre.
Para n grande o suficiente, existe outra máquina Z de tamanho n + c < 2n que “incorpora” a máquina BBn e:
- Calcula Tmax(n) simulando BBn;
- Em seguida, enumera todas as Máquinas de Turing M1, M2,… de tamanho menor que 2n e simula-as sobre a fita vazia;
- Se Mi pára antes de Tmax(n) então Z mantém o rastro da cadeia yi deixada na fita e seu comprimento li; caso contrário, continua com a próxima máquina;
- Z pára quando todos as Mis de tamanho menor que 2n foram verificadas;
- Z retorna uma das cadeias de comprimento 2n que não foram geradas durante o processo; pelo menos uma delas existe pelo princípio da casa de pombos (há apenas 2n - 1 programas de comprimento menor que 2n).
Agora suponha que a complexidade de Kolmogorov C(x) de uma cadeia x é computável, então para cada cadeia yi de comprimento l podemos realmente encontrar a máquina de Turing mais curta que a gera: simplesmente encaixar a execução de todas as máquinas de Turing de comprimento C(yi) até que um deles pare com yi na fita de saída.
Assim, podemos encontrar todas as cadeias yi de comprimento 2n que tem C(yi) menor que 2n e as máquinas de Turing correspondentes Mi (|Mi| < 2n) que as geram; Também podemos calcular o tempo necessário para que o Mi gere yi.
Se T = max{ti}, então devemos ter que T > Tmax(n). Caso contrário, Z é capaz de simular todos os programas de tamanho menor 2n que geram uma cadeia de comprimento 2n até que eles parem, e registrem suas saídas; então, por construção, sua saída é uma cadeia y de comprimento 2n com C (y) = 2n (isto é, incompressível), mas |Z| = n + c < 2n e isso é uma contradição porque temos um programa de tamanho menor que 2n que produz uma cadeia cuja Complexidade de Kolmogorov é 2n.
Portanto, T é um limite superior para Tmax(n) e pode ser usado para verificar se M' para e, portanto, decide ⟨M, x⟩ ∈ HALT.
Conclusão
As duas reduções, do Problema da Parada à Complexidade de Kolmogorov e
da Complexidade de Kolmogorov ao Problema de Parada, implicam que os
dois problemas são Turing Equivalentes.
Comentários
Postar um comentário