Impossibilidade em Computabilidade e Complexidade: sempre em última análise, devido a argumentos diagonais?

Em Computabilidade, se quisermos provar que um problema não é recursivo ou não recursivamente enumerável, podemos usar, por exemplo, reduções de outros problemas não recursivos ou não re, o teorema de Rice, o teorema de Rice-Shapiro, etc. Essas técnicas funcionam graças a , ou se baseiam diretamente na existência de algum argumento diagonal (ou seja, algum programa se comporta de maneira oposta ao seu programa de entrada M ' , então M = M ' é contraditório). Em Complexidade, se queremos provar que algum problema não pode ser calculado em algum tempo (independentemente de reivindicações não comprovadas, como por exemplo, P ≠ N $M$$M'$$M = M'$$P \neq NP$), Usamos os argumentos que são, em última análise, com base em algumas argumento diagonal (por exemplo, o tempo de hierarquia teorema prova problemas -completo não estão em P , mas que o teorema também é comprovado por meio de um argumento diagonal).$EXPTIME$$P$

Então, minha pergunta é a seguinte. São todos importantes resultados impossibilidade Computabilidade e Complexidade (impossibilidade real, não a impossibilidade até algum resultado unproved) em última análise, devido a algum argumento diagonal? Ou seja, todo o nosso importante "conhecimento da impossibilidade" em Computabilidade e Complexidade vem do fato de que os programas são poderosos o suficiente para executar programas?

O único resultado de impossibilidade importante que me vem à mente e que não se deve a um argumento diagonal é que a função de Ackermann não é recursiva primitiva. Estou perdendo outros contra-exemplos importantes dessa aparente "regra"?

Edição (18 de novembro): Desculpe por sugerir que minha pergunta estava focada particularmente no argumento diagonal, mas estou mais interessado em todos os argumentos que se baseiam na auto-referência de programas (incluindo o argumento diagonal, paradoxo de Berry, etc.). Para linguagens mais simples (por exemplo, regulares ou sem contexto), temos argumentos de impossibilidade "estruturais" com base em como essas linguagens são construídas (por exemplo, lemas de bombeamento). No entanto, para linguagens recursivas ou re, a maioria dos resultados de impossibilidade depende fortemente da auto-referência dos programas. Foi isso que eu quis dizer.

Limites inferiores em modelos de computação não uniformes, como fórmulas e circuitos booleanos, são comprovados usando argumentos combinatórios. Alguns exemplos são o método de Krapchenko usando medidas formais de complexidade, o método de aproximações de Razborov para circuitos monótonos, o método de restrição aleatória, incluindo restrição aleatória + o lema de comutação e limites inferiores de profundidade usando a complexidade da comunicação através dos jogos de Karchmer-Wigderson. Você pode encontrar notas de aula sobre este material de Sudão , Kopparty , Buss , Zwick , entre outros.

O limite inferior do modelo de comparação padrão para classificação e a maioria dos limites inferiores do modelo de sonda de célula para estruturas de dados são incondicionais (para computação no modelo, mas você poderia dizer o mesmo sobre os limites inferiores da máquina de Turing) e dependem da teoria da informação e não da diagonalização.

Uma ferramenta que pode ser usada para provar resultados negativos / impossíveis é o método de incompressibilidade :

$c$$y$$A$$m$$m(1-2^{-c})+1$$X$$C(x \mid y) \geq \log m - c$

$O(n^2)$$\{ ww^R\}$$a^n b^n$

Em última análise, o teorema acima baseia-se no Princípio do Pombo, que possui algumas boas aplicações diretas; por exemplo:

$d > 0$$d$

$d$$d$

Na verdade, o problema de parada pode ser provado sem o uso de diagonalização. (E todo teorema ZFC válido tem uma prova ZFC que usa diagonalização ... pense nisso.)

A prova usa o paradoxo de Berry e prossegue da seguinte maneira:

Indexe todas as máquinas de Turing de maneira razoável. Suponha, por uma questão de contradição, que o problema da parada possa ser resolvido. Em seguida, considere este algoritmo:

f (N) retorna a máquina de Turing menos indexada X st X (X) não para e X não é a saída de nenhuma máquina de Turing M e a entrada I é inserida em N caracteres (ou seja, M (I) produz X -> | M | + | I |> = N).

Agora, selecionamos que N st f (N) suficientemente grande deve retornar uma descrição de X descrita precisamente pelo cálculo de f (N). Se f é computável, então M = f e I = N. Por exemplo, poderíamos deixar N = um googol (10 ^ 100).

Isso sugere que f (N) não é uma função total, porque para f (10 ^ 100), não há saída satisfatória. Isso contradiz a suposição de que o problema de parada pode ser resolvido. Considere o seguinte pseudocódigo (que é muito menor que 10 ^ 100 caracteres quando expandido para o código-fonte verdadeiro em C ++ ou mesmo gravado como uma máquina de Turing) para f:

f (N)

{

for (int i = 1;; i ++)

{

  if (simulate DoesHalt(UTM(i,i)) == false)

  {

         (simulate all machines and inputs M(I) with |M|+|I|<N)

         if all such inputs do not output i

                 return i;

  }

}

}

Claramente, f pára em todas as entradas e funciona corretamente, assumindo que a interrupção do problema possa ser resolvida. Pelo exposto, temos que o problema da parada não pode ser resolvido.

Essa prova não usa nenhuma forma de diagonalização. De fato, você deveria dar uma olhada na minha pergunta:

Uma definição da palavra paradoxo é "algo que pode ser usado para provar indecidível o problema da parada?"

... para alguma discussão do fato de que muitos paradoxos podem ser usados ​​no lugar do paradoxo do mentiroso ou do paradoxo de Russell para provar que o problema da parada não pode ser resolvido. Alguns desses paradoxos de argumento não diagonal incluem o paradoxo suspenso inesperado e (como acabamos de descrever) o paradoxo de Berry.