O décimo problema de Hilbert e a equação diofantina de Chaitin "Computador"?
Na Meta Matemática de Chaitin ! The Quest For Omega , ele fala brevemente sobre o 10º Problema de Hilbert. Ele então diz que qualquer equação diofantina pode ser alterada em dois polinômios iguais com coeficientes inteiros positivos: .p = 0p = 0p=0p = 0⟺p1 1= p2p=0⟺p1=p2
Então ele diz que podemos pensar nessas equações como um "computador":
Equação Diofantina Computador : Programa: , Saída: , Tempo:
L ( k , n , x , y, z, . . . ) = R ( k , n , x , y, z, . . . )L(k,n,x,y,z,...)=R(k,n,x,y,z,...)
kk nn x , y, z, . . .x,y,z,...
Com o lado esquerdo , lado direito . Ele diz que é o programa deste computador, que gera . Ele também diz que as incógnitas são uma variável de tempo multidimensional .R k neuLRRkknn
O que me confunde é que ele diz que o décimo problema de Hilbert claramente não é solucionável quando visto dessa maneira. Ele basicamente diz "por causa do problema de parada de Turing". Mas não vejo a conexão (estou apenas começando a aprender a teoria). Eu esperava que alguém pudesse explicar mais claramente qual é o argumento de Chaitin aqui.
Eu sei que o problema de parada de Turing basicamente afirma que você não pode prever quando um programa será interrompido antes que ele realmente pare (dado um período finito de tempo). Qual é a aplicação do décimo problema de Hilbert, usando a notação apresentada por Chaitin?
— Estável
Boa pergunta. Parece que você pode precisar de mais informações sobre o 10º Problema de Hilbert. Espero que isso não seja um exagero.
O problema pergunta:
Existe um algoritmo que, dado um polinômio diofantino, decida se existe ou não uma configuração de suas variáveis ​​que o torna igual a ?0 00
Isso foi resolvido nos anos 70 como uma conseqüência do MRDP (também chamado de teorema de Matiyasevich, se você quiser pesquisá-lo), que afirma:
Definir: Um conjunto é diofantino se houver um polinômio diofantino em entradas tais que . p k + 1 D = { xD ⊂ ND⊂Nppk + 1k+1D = { x|∃ y∈ Rk+p ( x , y) = 0 }D={x|∃y∈R+kp(x,y)=0 0}
Os conjuntos diofantinos são precisamente aqueles que são reconhecidos pelas máquinas de Turing.
Esse teorema é óbvio em uma direção (todo conjunto diofantino é reconhecível por uma máquina de Turing - na entrada , faça com que sua máquina comece a adivinhar vetores , avalie e interrompa se / quando você achar que ). É muito óbvio na outra direção - por que é verdade que todo conjunto reconhecível de Turing é diofantino? Os esquemas de codificação são nojentos, mas confie em mim, isso pode ser feito.y ∈ R k + p ( x , y ) p ( x , y ) = 0xxy∈ Rk+y∈R+kp ( x , y)p(x,y)p ( x , y) = 0p(x,y)=0 0
De qualquer forma, como o teorema do MRDP resolve o décimo problema de Hilbert? Bem...
Por uma questão de contradição, vamos fingir que temos um algoritmo que, dado um polinômio diofantino , decide se existe ou não um vetor de entrada que causa .y p ( y ) = 0p ( y)p(y)yyp ( y) = 0p(y)=0 0
Agora vou usar esse algoritmo mágico para resolver o problema da parada. Dada uma máquina, usarei a codificação repugnante das equações diofantinas para converter o problema " pára na entrada ?" no problema "O polinômio diofantino possui um conjunto de entradas que o tornam igual a ?" Então usarei meu algoritmo mágico para resolver esse problema e agora resolvi o problema da parada.x p ( y | x ) 0MMxxp( y| x)p(y|x)0 00 0
Obviamente, isso é impossível, portanto, na realidade, não pode haver um algoritmo mágico que procure um vetor de entrada que cause . Da mesma forma, não pode haver um algoritmo que analise dois polinômios diofantinos e decida se eles são iguais. É o que Chaitin está dizendo.p ( y) = 0p(y)=0 0