Tese Estendida de Church-Turing

Uma das perguntas mais discutidas no site foi O que significaria refutar a tese de Church-Turing . Isso ocorre em parte porque Dershowitz e Gurevich publicaram uma prova da tese de Church-Turing é o Boletim da Lógica Simbólica em 2008. (Não discutirei isso aqui, mas para obter um link e comentários extensos, consulte a pergunta original, ou - - autopromoção vergonhosa - uma entrada de blog que escrevi.)

Esta pergunta é sobre a Tese Estendida de Church-Turing, que, conforme formulada por Ian Parberry, é:

O tempo em todos os modelos de máquinas "razoáveis" é relacionado por um polinômio.

Graças a Giorgio Marinelli, eu aprendi que um dos co-autores do documento anterior, Dershowitz, e um estudante de PhD da sua, Falkovich, ter publicado uma prova da extensa tese de Church-Turing, que só apareceu na oficina Developments de Modelos Computacionais 2011 .

Acabei de imprimir o jornal hoje de manhã e passei os olhos por ele, nada mais. Os autores afirmam que as máquinas de Turing podem simular qualquer dispositivo computacional seqüencial com no máximo sobrecarga polinomial. A computação quântica e a computação paralela em larga escala não são explicitamente abordadas. Minha pergunta está relacionada à seguinte declaração no documento.

Mostramos - como já se supôs e é amplamente aceito - que toda implementação eficaz, independentemente de quais estruturas de dados ela usa, pode ser simulada por uma máquina de Turing, com no máximo sobrecarga polinomial na complexidade do tempo.

Então, minha pergunta: isso é realmente "amplamente aceito", mesmo no caso de computação sequencial "verdadeiramente" sem randomização? E se as coisas forem aleatórias? A computação quântica seria um contra-exemplo provável, se na verdade puder ser instanciada, mas existem possibilidades "mais fracas" que o quantum que também seriam contra-exemplos?

Rant preparatório

Eu tenho que lhe dizer, eu não vejo como falar sobre "provas" do CT ou ECT acrescenta alguma luz a esta discussão. Tais "provas" tendem a ser exatamente tão boas quanto as suposições em que se apóiam - em outras palavras, como significam o que consideram palavras como "computação" ou "computação eficiente". Então, por que não prosseguir imediatamente para uma discussão das suposições e dispensar a palavra "prova"?

Isso já estava claro com o TC original, mas é ainda mais claro com a ECT - já que a ECT não é apenas "filosoficamente improvável", mas hoje é amplamente considerada falsa! Para mim, a computação quântica é o enorme e flagrante exemplo que deve ser o ponto de partida para qualquer discussão moderna sobre a ECT, e não algo desviado para o lado. No entanto, o artigo de Dershowitz e Falkovich nem toca em CQ até o último parágrafo:

O resultado acima não cobre a computação paralela em larga escala, como a computação quântica, pois propõe que há um limite fixo no grau de paralelismo, com o número de termos críticos fixados pelo algoritmo. A questão da complexidade relativamente [sic] dos modelos paralelos será abordada em um futuro próximo.

Eu achei o acima altamente enganador: QC não é um "modelo paralelo" em nenhum sentido convencional. Na mecânica quântica, não há comunicação direta entre os "processos paralelos" - apenas interferência de amplitudes - mas também é fácil gerar um número exponencial de "processos paralelos". (De fato, alguém poderia pensar em todo sistema físico do universo como o fazemos enquanto falamos!) De qualquer forma, o que você pensa sobre a interpretação da mecânica quântica (ou mesmo sua verdade ou falsidade), fica claro que isso requer uma discussão!

Agora, vamos às suas perguntas (interessantes)!

Não, não conheço nenhum contra-exemplo convincente da ECT que não seja a computação quântica. Em outras palavras, se a mecânica quântica fosse falsa (de uma maneira que ainda mantivesse o universo mais "digital" do que "analógico" na escala de Planck - veja abaixo), então o ECT como eu o entendo ainda não seria "provável" (já que ainda dependeria de fatos empíricos sobre o que é eficientemente computável no mundo físico), mas seria uma boa hipótese de trabalho.

A randomização provavelmente não desafia a ECT como é convencionalmente entendida, devido à forte evidência hoje de que P = BPP. (Embora note que, se você estiver interessado em diferentes problemas de decisão idioma configurações --- por exemplo, problemas de relacionamento, árvores de decisão, ou a complexidade de comunicação --- então randomização comprovadamente pode fazer uma enorme diferença. E essas configurações são perfeitamente razoável sobre o que falar; eles não são os que as pessoas normalmente têm em mente quando discutem a ECT.)

A outra classe de "contra-exemplos" para a ECT, frequentemente levantada, envolve computação analógica ou "hiper". Minha opinião é de que, em nosso melhor entendimento atual da física, a computação analógica e a hipercomputação não podem ser dimensionadas, e a razão pela qual elas não podem, ironicamente, é a mecânica quântica! Em particular, embora ainda não tenhamos uma teoria quântica da gravidade, o que é conhecido hoje sugere que existem obstáculos fundamentais para executar mais de 10 ⁴³ etapas de computação por segundo ou resolver distâncias menores que 10 a ³³ cm.

Finalmente, se você quiser assumir fora de discussão qualquer coisa que possa ser um desafio plausível ou interessante para a ECT, e apenas permitir computação serial, discreta e determinística, então eu concordo com Dershowitz e Falkovich que a ECT possui! :-) Mas mesmo lá, é difícil imaginar uma "prova formal" aumentando minha confiança nessa afirmação - a questão real, novamente, é exatamente o que chamamos de palavras como "serial", "discreta" e "determinística" para média .

Quanto à sua última pergunta:

A computação quântica seria um contra-exemplo provável, se na verdade puder ser instanciada, mas existem possibilidades "mais fracas" que o quantum que também seriam contra-exemplos?

Hoje, existem muitos exemplos interessantes de sistemas físicos que parecem capazes de implementar parte da computação quântica, mas não toda (produzindo classes de complexidade que podem ser intermediárias entre BPP e BQP). Além disso, muitos desses sistemas podem ser mais fáceis de realizar do que um CQ universal completo. Veja, por exemplo, este artigo de Bremner, Jozsa e Shepherd, ou este de Arkhipov e eu.

Esta resposta pretende complementar a resposta de Scott Aaronson (com a qual concordo principalmente).

Do ponto de vista da engenharia, é surpreendente que o artigo de Dershowitz / Falkovich use a palavra "aleatório" apenas no sentido de "memória de acesso aleatório" e, além disso, o artigo não usa a palavra "amostra" (ou qualquer uma de suas variantes). Pelo contrário, o foco da análise de Dershowitz / Falkovic é exclusivamente restrito ao cálculo de funções numéricas.

Essa limitação é impressionante porque a grande maioria dos recursos computacionais modernos de STEM (eu me atreveria a dizer) não respeitam a restrição às funções numéricas, mas são dedicados a gerar amostras de distribuições (por exemplo, dinâmica molecular, fluxo de fluido turbulento, propagação de fraturas) , sistemas de spin ruidosos tanto clássicos quanto quânticos, ondas propagando-se por meios aleatórios etc.).

Assim, se a "Tese Estendida de Church-Turing" (ECT) tiver relevância substancial para os cálculos de STEM definidos de maneira ampla, talvez a restrição exclusiva às funções numéricas deva ser levantada e seja fornecida uma declaração generalizada da ECT, que inclua a amostragem cálculos (e sua validação e verificação).

Essa versão generalizada para amostragem da ECT ainda se enquadra no âmbito do TCS como tradicionalmente concebido? A resposta aparentemente é "sim", de acordo com as Perguntas frequentes do TCS Stack Exchange :

Nós o referimos à descrição do Grupo de Interesse Especial da ACM sobre Algoritmos e Teoria da Computação (SIGACT) ... O TCS abrange uma ampla variedade de tópicos, incluindo o cálculo probabilístico ... O trabalho neste campo [TCS] é frequentemente distinguido por sua ênfase na matemática. técnica e rigor.

Antes de tudo, ao contrário de algumas fontes, afirmo que o pode ser absolutamente entendido como um axioma matemático ou, pelo menos, como uma proposição matemática se duvidarmos de sua verdade. Introduzir em nossa linguagem de trabalho um novo símbolo de predicado definido em modelos de computação com o significado pretendido de que um modelo é razoável. Esta é essencialmente a mesma situação que Peano e outros enfrentaram: já temos um significado pretendido para os símbolos , mesmo antes de escrever os axiomas que os envolvem. Pelo menos até axiomatizá-la, nossa teoria permanece sólida sob a interpretação do novo símbolo, seja o que for que isso signifique, porque os únicos fatos que podemos provar são tautologias. O que é razoável é razoável, por exemplo. Agora adicione um axioma, o$\text{ECTT}$$\{0,1,+,\times\}$$\text{ECTT}$ , que diz que esse predicado de razoabilidade é satisfeito exatamente por esses modelos que possuem uma tradução polinomial no tempo para uma máquina de Turing. Como axioma, não é falsificável no sentido de nossa teoria ser capaz de contradizê-la, desde que a teoria seja consistente, mas a solidez de nossa teoria é falsificável: é possível que exista um modelo razoável de computação que não esteja relacionado a Máquinas de Turing por uma tradução polinomial do tempo. Permitir que essa descoberta hipotética possa envolver uma mudança no pensamento sobre o que é razoável, é assim que vejo o lado formal. Parece trivial em retrospecto, mas acho que é um ponto importante para delinear a matemática de todo o resto.

No geral, vejo o como um princípio e axioma sólidos. Mas temos computadores em funcionamento que são bem descritos por , e há problemas como a localização privilegiada e o teste de identidade polinomial que não se sabe estarem em , então por que isso não viola o ? Até que possamos realmente provar : enquanto isso, em vez de mudar nosso foco para , não é pior manter o como está e dizendo o que é o teste de identidade polinomial, na verdade, está em$\text{ECTT}$$\text{BPP}$$\text{P}$$\text{ECTT}$$\text{P} \neq \text{BPP}$$\text{BPP}$$\text{ECTT}$$\text{P}$. Essa abordagem também permite isolar problemas específicos nos quais estamos interessados, como fatoração. É uma suposição sutilmente diferente do que equipar nosso modelo com um oráculo, já que na verdade não mudamos o modelo, mas o efeito é o mesmo. Deste ponto de vista utilitário, o é suficiente até que possamos provar qualquer separação. A situação é a mesma para a computação quântica, exceto que precisamos construir um computador quântico funcional e provar para realmente tirar o fôlego do . Se apenas construirmos um sem a prova, talvez o universo seja uma simulação em execução em um computador clássico e o$\text{ECTT}$$\text{P} \neq \text{BQP}$$\text{ECTT}$$\text{ECTT}$ainda é válido, ou se o provarmos sem a construção de um, talvez não seja realmente um modelo razoável. Para tornar o argumento realmente rígido, precisamos de problemas completos para e com relação a , mas podemos nos contentar em escolher os problemas que sabemos resolver.$\text{BPP}$$\text{BQP}$$\text{P}$

Por exemplo, suponha que afirmo ter construído uma máquina que fatora números e que seu tempo de execução satisfaz um limite polinomial específico. A máquina está em uma caixa, você alimenta o número escrito em uma fita de papel e imprime os fatores. Não há dúvida de que funciona, já que eu o usei para vencer os desafios da RSA, confiscar criptomoeda, fatorar um grande número de sua escolha, etc. O que há na caixa? É um novo tipo incrível de computador ou é um computador comum executando um novo tipo incrível de software?

Ao assumir o , estamos dizendo que deve ser um software ou, pelo menos, que a mesma tarefa possa ser realizada pelo software. E até que possamos abrir a caixa provando separações de classes de complexidade, nenhuma generalidade é perdida sob essa suposição. Isso ocorre porque, mesmo que a operação da máquina seja explicada bem por algum modelo não clássico ou não determinístico razoável e não explicado pelo determinístico clássico, ainda precisaríamos provar que esses modelos são realmente diferentes para interromper nossa interpretação do modelo. e torne nossa teoria doentia.$\text{ECTT}$$\text{ECTT}$

Para desafiar o de uma direção totalmente extra-matemática, parece que precisaremos de uma máquina ou, pelo menos, de um princípio físico plausível para resolver um problema completo de em tempo polinomial. Mesmo uma máquina do tempo implementando não é poderosa o suficiente para derrotar o sem uma prova de , embora possa nos ajudar a produzir um.$\text{ECTT}$$\text{EXPTIME}$$\text{P}_\text{CTC} = \text{PSPACE}$$\text{ECTT}$$\text{P} \neq \text{PSPACE}$

Para ilustrar, Doctor Who passou os fios de telefone por um buraco de minhoca e construiu uma engenhoca que ele usa para descobrir uma prova formal de um gigabyte de comprimento . Ele ganhou o prêmio Millenium e também invalidou o , porque o resultado implica em . Se sua engenhoca encontrar uma prova de , ou uma prova da hipótese de Riemann, ele ainda ganha o prêmio, mas é isso - nenhuma violação de . No entanto, a engenhoca do médico parece ser uma ferramenta melhor para atacar o$\text{P} \neq \text{NP}$$\text{ECTT}$$\text{P} \neq \text{P}_\text{CTC}$$\text{P} = \text{NP}$$\text{ECTT}$$\text{ECTT}$do que minha incrível caixa de fatoração, já que não sei como fatorar números magicamente em tempo polinomial pode me ajudar a provar que não é possível fazer a mesma coisa sem mágica. Para estar em pé de igualdade, teria que ser o fato de que o fatoração é completo e também que (de alguma forma) conheço uma redução a partir de - então eu poderia codificar a busca por uma prova esse fatoração não está em como uma série de problemas de fatoração e tem uma chance de encontrá-lo antes que o buraco de minhoca reabra.$\text{NP}$$\text{3SAT}$$\text{P}$

No outro canto, fica o Deep Blue, um robô gigante projetado por uma corporação para resolver problemas completos de . Seu desafio é jogar xadrez perfeito rapidamente em todos os tamanhos de tabuleiro e convencer-nos de que ele realmente pode fazer isso com um orçamento de marketing ilimitado. Mas ele não precisa justificar a exclusividade de seus métodos para nos fazer reescrever o , pois já sabemos que . Isso é mais trivial do que parece: se o robô é razoavelmente construído, e o que o robô faz é incrível, o modelo razoável que o descreve é ​​capaz de fazer coisas incríveis e podemos redirecionar o para polir suas engrenagens.$\text{EXPTIME}$$\text{ECTT}$$\text{EXPTIME} \neq \text{P}$$\text{ECTT}$

Na minha opinião, a resposta de Scott Aaronson é matematicamente incoerente, porque não é compatível com nenhuma formalização do que posso identificar. Devemos pesar evidências a favor e contra , mas acho que devemos exigir provas e não apenas evidências antes de abandonar toda a idéia do ou modificá-la sem prática. benefício (deixa de lado o negócio desagradável de estender o conceito de conversão de tempo para modelos não determinísticos). E, como argumentei acima, a discussão sobre se a computação quântica é real é um arenque vermelho sem uma prova de .$\text{ECTT}$$\text{P} = \text{BPP}$$\text{ECTT}$$\text{P} \neq \text{BQP}$

Aqui está um resumo da situação. Para qualquer modelo de cálculo, é inconsistente acreditar simultaneamente nessas três instruções: o ; que o modelo é razoável ou fisicamente possível; e que o modelo é mais poderoso que uma máquina de Turing. Somente a última afirmação está no idioma de nossa teoria original,$\text{ECTT}$$\{\in\}$. Se ainda não está resolvido, estamos apostando com consistência assumindo-o como um axioma ou assumindo as duas primeiras afirmações juntas, o que implica sua negação. Portanto, nossa única opção de incorporar qualquer uma dessas idéias que preservará a consistência é entre uma definição do que meios razoáveis ​​e uma afirmação de que esse modelo específico é razoável (que por si só, sem a definição, não nos dá muito a trabalhar com). Obviamente, podemos ter os dois e ainda ser consistente se o$\text{ECTT}$para outra coisa, mas isso terá sido um esforço desperdiçado se a separação de classes for estabelecida do lado oposto ao esperado. Independentemente disso, axiomatizando nosso símbolo de predicado de razoabilidade sob uma interpretação tão nebulosa, estamos apostando com firmeza. Antes, com nosso idioma igual a , tínhamos apenas uma preocupação aritmética com a qual nos preocupamos, e agora devemos concordar com o que é razoável também.$\{\in\}$

Tendo folheado o artigo vinculado de Dershowitz e Falkovich, acredito que seus autores também sustentam uma visão incoerente ou talvez apenas tautológica do .$\text{ECTT}$