O que significaria refutar a tese de Church-Turing?

83

Desculpe pelo título cativante. Quero entender, o que se deve fazer para refutar a tese de Church-Turing? Em algum lugar que li, é matematicamente impossível fazê-lo! Por quê?

Turing, Rosser etc usaram termos diferentes para diferenciar entre: "o que pode ser calculado" e "o que pode ser calculado por uma máquina de Turing".

A definição de Turing de 1939 em relação a isso é: "Usaremos a expressão" função computável "para significar uma função calculável por uma máquina e deixamos que" efetivamente calculável "se refira à idéia intuitiva sem identificação particular com qualquer uma dessas definições".

Assim, a tese de Church-Turing pode ser declarada da seguinte forma: Toda função efetivamente calculável é uma função computável.

Então, novamente, como será a prova se alguém refutar essa conjectura?

computability proofs hypercomputation András Salamon
fonte
1
Verifique o apêndice neste ótimo (mas difícil de ler) artigo de L. Levin arxiv.org/PS_cache/cs/pdf/0203/0203029v16.pdf
user2471
ver também aplicabilidade da tese de Church-Turing para modelos interativos de computação
vzn

Respostas:

5

A tese de Church-Turing foi comprovada para todos os fins práticos.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.146.5402

Dershowitz e Gurevich, Boletim de Lógica Simbólica, 2008.

(Esta referência discute a história do trabalho de Church e Turing e defende uma separação entre "Tese da Igreja" e "Tese de Turing" como reivindicações lógicas distintas e, em seguida, prova ambas, dentro de uma axiomatização intuitiva da computabilidade.)

Aaron Sterling
fonte
24
Estou um pouco preocupado com esta resposta. Pode dar a impressão errada às pessoas que a tese de Church-Turing foi provada, quando na verdade não foi (e eu imagino que a maioria das pessoas pensa que não pode ser provada).
Emil
5
Este será o meu último comentário aqui, mas acho que você pode perguntar por que um site como esse é necessário se tudo o que precisamos fazer é olhar para os livros didáticos. Arora e Barak são ótimos pesquisadores, mas não são lógicos ou pesquisadores da teoria da complexidade (escreveram um livro de complexidade de qualquer maneira, mesmo que essa não fosse sua principal área de pesquisa), ou especialistas em semântica da linguagem de programação (que era a motivação original para máquinas de estado abstratas). A sabedoria convencional não é necessariamente verdadeira e, no final do dia, temos que pensar por nós mesmos.
Aaron Sterling
8
Se Dershowitz e Gurevich provaram as teses de Church e Turing, também provaram que, no futuro, não seremos capazes de construir um computador que execute infinitamente várias etapas computacionais em tempo finito, veja, por exemplo, arxiv.org/abs/gr-qc/ 0104023 que discute essas possibilidades.
Andrej Bauer
50
Como normalmente entendido, a tese de Church-Turing não é uma proposição formal que possa ser provada. É uma hipótese científica, portanto pode ser "contestada" no sentido de que é falsificável. Qualquer "prova" deve fornecer uma definição de computabilidade, e a prova é tão boa quanto essa definição. Tenho certeza de que Dershowitz-Gurevich tem uma boa prova, mas o verdadeiro problema é se a definição realmente cobre tudo o que é computável. Respondendo "pode ​​ser refutado?" dizer "está provado" é enganoso. Foi provado sob uma definição razoável (falsificável!) De computabilidade.
Ryan Williams
47
O artigo de Dershowitz-Gurevich não diz nada sobre computação probabilística ou quântica. Ele escreve um conjunto de axiomas sobre computação e prova a tese de Church-Turing assumindo esses axiomas. No entanto, resta justificar esses axiomas. Nem o cálculo probabilístico nem o quantum são cobertos por esses axiomas (eles admitem isso para o cálculo probabilístico, e não mencionam o cálculo quântico); portanto, é bastante claro para mim que esses axiomas são realmente falsos no mundo real, mesmo que Church-Turing tese é provavelmente verdadeira.
Peter Shor
60

Há um ponto sutil que raramente vejo mencionado nesses tipos de discussões e que acho que merece mais atenção.

Suponha que, como Andrej sugere, alguém construa um dispositivo que calcule de forma confiável uma função que não pode ser calculada por nenhuma máquina de Turing. Como saberíamos que a máquina está de fato computando ?fff

Obviamente, nenhum número finito de valores de entrada / saída seria suficiente para demonstrar que a máquina está computando em oposição a alguma outra função computável de Turing que concorda com nesse conjunto finito. Portanto, nossa crença de que a máquina está computando teria que se basear em nossas teorias físicas de como a máquina está operando. Se você olhar algumas das propostas concretas para hipercomputadores, descobrirá que, com certeza, o que elas fazem é adotar uma teoria física de ponta sofisticada e extrapolar essa teoria para o infinitof ffff. OK, tudo bem, mas agora suponha que construamos o hipercomputador e perguntemos se uma máquina de Turing que procura uma contradição no ZFC será interrompida. Suponha ainda que o hipercomputador responda "Não". O que concluímos? Concluímos que o hipercomputador "computou" a consistência do ZFC? Como podemos descartar a possibilidade de o ZFC ser realmente inconsistente e termos acabado de realizar um experimento que falsificou nossa teoria física?

Uma característica crucial da definição de Turing é que suas suposições filosóficas são muito fracas. Pressupõe, como é óbvio, certas características simples de nossa experiência cotidiana, como a estabilidade básica do mundo físico e a capacidade de executar operações finitas de maneira confiável, repetível e verificável. Essas coisas todo mundo aceita (fora de uma sala de aula de filosofia, é isso!). A aceitação de um hipercomputador, no entanto, parece exigir que aceitemos uma extrapolação infinitade uma teoria física, e toda a nossa experiência com a física nos ensinou a não ser dogmático sobre a validade de uma teoria em um regime que está muito além do que podemos verificar experimentalmente. Por esse motivo, parece-me altamente improvável que algum tipo de consenso esmagador venha a acontecer de que qualquer hipercomputador específico esteja simplesmente computando em oposição ao hipercomputador , ou seja, fazendo algo que pode ser chamado de "computação" somente se você aceitar algum argumento filosófico ou controverso. suposições físicas sobre extrapolações infinitas.

Outra maneira de dizer isso é que a desaprovação da tese de Church-Turing exigiria não apenas a construção do dispositivo que Andrej descreve, mas também a satisfação de todos que o dispositivo está funcionando como anunciado. Embora não seja inconcebível, essa é uma tarefa difícil. Para os computadores de hoje, a natureza finitária da computação significa que, se não acredito no resultado da "computação" de um computador em particular, posso, em princípio, executar uma sequência finita de etapas de uma maneira totalmente diferente para verificar o resultado. Esse tipo de "retorno" ao senso comum e à verificação finita não estará disponível se tivermos dúvidas sobre um hipercomputador.

Timothy Chow
fonte
1
Tim, claramente, a tese de Church-Turing pode ser refutada pela demonstração bem-sucedida de um modelo de computação eficaz que transcende o escopo comum dos modelos equivalentes que Church e Turing identificaram. Pode-se argumentar quão inconcebível isso possa ser, mas acredito que ainda é o que seria necessário. (Observe que eu evito "provar" e "refutar" neste contexto.)
orcmid
2
@ Neel: Você está entendendo mal o meu ponto. Estou dizendo que, se o Computador Físico X executar uma computação envolvendo n etapas, então, em princípio, eu posso verificar a computação executando n etapas de alguma maneira que não se baseie em teorias físicas sofisticadas. É verdade que não posso executar etapas, mas nem o Computador Físico X, o que é irrelevante para o meu ponto. 22250
Timothy Chow
6
@ Neel: Pelo contrário, meu argumento é precisamente que é perfeitamente razoável duvidar da física sofisticada subjacente a um computador, seja o que existe hoje ou um hipercomputador do futuro. Um dos principais motivos pelos quais toleramos os computadores de hoje é que eles são encarregados de cálculos finitos que, em princípio, podemos imitar sem uma física sofisticada. Mas construa um hipercomputador cuja exatidão depende inerentemente de extrapolar teorias físicas infinitamente além de regimes experimentalmente acessíveis, e não temos como saber se a computação está correta ou se nossas teorias deram errado.
Timothy Chow
6
@ orcmid: A física deve inserir a imagem em algum lugar; caso contrário, o que nos impedirá de declarar que todas as funções são computáveis? Para merecer o nome, uma "computação" deve ser algo que possamos imaginar realmente realizando. É por isso que as propostas de hipercomputadores se esforçam para explicar como elas podem ser fisicamente construídas. O que quero dizer é que devemos levar o experimento mental um passo adiante: diante de um suposto hipercomputador, como saberíamos que ele realmente funciona como anunciado? Se não pudéssemos saber, seria realmente legítimo referir-se a seus resultados como "cálculos"?
Timothy Chow
1
Isso é interessante, talvez não possamos realmente saber que a máquina está computando f, porque estamos apenas concluindo Turing. Talvez levaria um observador hypercomputating para verificar se um objeto hypercomputing é realmente hypercomputing oO
guillefix
58

Embora pareça muito difícil provar a tese de Church-Turing por causa da natureza informal da "função efetivamente calculável", podemos imaginar o que significaria refutá-la. Ou seja, se alguém construísse um dispositivo que (confiavelmente) calculasse uma função que não pode ser calculada por nenhuma máquina de Turing, isso desmentiria a tese de Church-Turing porque estabeleceria a existência de uma função efetivamente calculável que não é computável por uma máquina de Turing.

Andrej Bauer
fonte
1
Em que sentido alguém deve "construir" a máquina? Vivemos em um mundo finito, que só pode conter computadores estritamente mais fracos que as máquinas de Turing. Talvez ele deva inventar uma nova caracterização lógica intuitivamente atraente? Como pode ser?
Vag
2
E nosso universo é cada vez mais restrito do que as máquinas de estado finito teóricas devido à delimitação de massa / energia pela constante de concreto e pelo limite de Bremmermann pespmc1.vub.ac.be/ASC/Bremer_limit.html, para que existam cálculos que FSMs imaginários maiores podem fazer, exceto computadores físicos não pode (problemas transcomputacionais).
Vag
2
Seria necessário, é claro, que um ser humano fosse capaz de simular a máquina, a fim de refutar a tese original de Turing que identifica calculabilidade efetiva com calculabilidade humana.
Carl Mummert
35

Desprovar a tese de Church-Turing parece realmente extremamente improvável e conceitualmente muito difícil de imaginar. Existem vários "mundos físicos hipotéticos" que estão em certa tensão com a tese de Church-Turing (mas se eles contradizem isso é por si só uma questão filosófica interessante). Um artigo de Pitowsky " A Tese da Igreja Física e a Complexidade Computacional Física", Iyun 39, 81-99 (1990) lida com esses mundos físicos hipotéticos. Veja também o artigo de Itamar Pitowsky e Oron Shagrir: " The Church-Turing Thesis and Hyper Computation ", Minds and Machines 13, 87-101 (2003). Oron Shagrir ter escrito vários artigos filosóficos sobre a tese de Church-Turing ver sua página web . (Veja também esta postagem do blog .)

A tese eficaz ou eficiente de Church-Turing é uma afirmação infinitamente mais forte do que a afirmação original de Church-Turing, que afirma que todo cálculo possível pode ser simulado com eficiência por uma máquina de Turing. Computadores quânticos realmente mostrarão que a tese eficiente de Church-Turing é inválida (módulo algumas conjecturas matemáticas de complexidade computacional e módulo a "interpretação assintótica"). Penso que a conjectura eficiente de Church-Turing foi formulada pela primeira vez em 1985 por Wolfram, o artigo é citado no artigo de Pitowsky acima. De fato, você nem precisa de computadores quânticos universais para refutar a eficiente tese de TC, e é interessante a linha de pesquisa (que Aaronson, entre outros estudos), propõe a demonstração o mais simples possível da superioridade computacional dos sistemas quânticos.

Também é um problema interessante se existem maneiras mais simples de demonstrar a superioridade computacional dos computadores quânticos na presença de ruído, em vez de ter uma tolerância total a falhas quânticas (que permite o cálculo quântico universal). (Scott A. está realmente interessado também neste problema.)

Gil Kalai
fonte
Eu pensei que as máquinas de Turing poderiam simular computadores quânticos? (Com grande perda de eficiência, é claro.) (Edit: ah, eu aviso que você disse que o "Effective CT tese" - esta é a tese de que TMs pode simular qualquer dispositivo de computação de forma eficiente?)
Emil
5
Penso que Gil está falando da tese "extensa" de Church-Turing (que ele chama de tese "eficaz" de Church-Turing) de que tudo o que é eficientemente computável na natureza também é computável em uma máquina de Polytime Turing.
Ryan Williams
2
Eu adicionei uma frase para esclarecer.
Gil Kalai
Gil, obrigado por este ótimo post! Para expressar um ponto de vista da engenharia de sistemas quânticos, nós humanos existimos em um universo barulhento, no qual (correção de erros ausentes) a ECT é empiricamente verdadeira - na medida em que processos dinâmicos quânticos podem ser simulados com eficiência - por meio de formalismos nos quais (efetivamente) a superposição quântica é uma aproximação local, no mesmo sentido em que a geometria euclidiana é uma aproximação local à geometria Riemanniana. A natureza adota fluxos quânticos semelhantes, para se calcular de maneira eficiente? Essa é uma pergunta em aberto ... e uma IMHO muito interessante.
precisa saber é o seguinte
Inspirado no post de Gil e no post de Timothy Chow (abaixo), promovai o comentário acima para uma pergunta formal do TCS: "Qual é o papel adequado da validação em amostragem quântica, simulação e teste de Church-Turing (ECT) estendido? " Obrigado Gil e Timothy.
John Sidles
24

Até onde eu entendo, a "impossibilidade" de provar ou refutar a tese é que não existe uma definição formal de "efetivamente calculável". Hoje, consideramos que é precisamente "computável por uma máquina de Turing", mas isso sugere a pergunta.

Modelos de computação que são estritamente mais poderosos do que uma máquina de Turing foram estudados, consulte http://en.wikipedia.org/wiki/Hypercomputation para alguns exemplos. Ou simplesmente pegue uma máquina de Turing com um oráculo para o Problema da Parada de Máquinas de Turing. Essa máquina terá seu próprio Problema de Parada, mas poderá resolver o Problema de Parada original muito bem. É claro que não temos esse oráculo, mas não há nada matematicamente impossível nessa ideia.

Evgenij Thorstensen
fonte
Obrigado pela resposta. Portanto, apresentar uma função que seja matematicamente realizável (mas não fisicamente) por algum modelo, mas não por uma máquina de Turing, não desmente a tese?
1
Dershowitz e Gurevich 2008 axiomatizam "efetivamente calculável" usando máquinas de estados abstratos.
Aaron Sterling
4
Então, eles estão definindo outro modelo de computação e provando que é equivalente aos modelos existentes, não é? Por que esse modelo computacional é mais confiável do que os existentes?
Blaisorblade 9/09/10
Poderíamos usar o poder humano como tal oráculo, criando uma prova formal para (não) rescisão. No entanto, o mau tempo de execução ...
Raphael
10

As reprovações de hipercomputação geralmente assumem a validade do limite de Bekenstein, que afirma um limite específico à quantidade de informações que uma quantidade finita de espaço pode conter. Há controvérsia sobre esse limite, mas acho que a maioria dos físicos o aceita.

Se o limite de Bekenstein for gravemente violado e não houver limite para a quantidade de informações contidas em uma região específica (por exemplo, um buraco negro ou uma gravura infinitamente fina e robusta), e existem mecanismos arbitrariamente refináveis ​​para examinar o conteúdo daquele região (digamos, examinando cuidadosamente a radiação emitida quando um objeto cuidadosamente construído cai no buraco negro ou passando uma caneta sobre as ranhuras da gravura), pode-se supor que já existe um artefato que codifica um oráculo de parada .

Tudo muito improvável, mas mostra que a afirmação de que a hipercomputação é impossível não é uma verdade matemática, mas baseada na física. O que significa dizer que Andrej está certo quando diz que podemos imaginar o que significaria refutar [a tese de Church-Turing]. Ou seja, se alguém construísse um dispositivo que (confiavelmente) calculasse uma função que não pode ser calculada por nenhuma máquina de Turing .

Charles Stewart
fonte
O limite de Bekenstein pode se manter, mas a hipercomputação ainda é possível.
András Salamon
@ András: Em princípio, sim: precisamos de muito mais teoria física para que um argumento negativo funcione. Mas as tentativas de "descrever" máquinas de hipercomputação que eu vi violam tudo.
Charles Stewart
Os que envolvem loops fechados próximos a buracos negros violam o limite?
András Salamon
@ András: Não sei qual deles você quer dizer. A teoria das cordas é geralmente compatível com o limite de Bekenstein.
Charles Stewart
Quero dizer coisas como arxiv.org/abs/gr-qc/0209061 que, em vez de confiar na teoria das cordas, "apenas" pressupõe que se possa enviar cálculos para o passado.
András Salamon
9

Em relação à Tese Estendida de Church-Turing (entendida como "Uma máquina de Turing probabilística pode simular com eficiência qualquer função fisicamente computável"):

Uma possibilidade é a diferença entre computadores clássicos e quânticos. Especificamente, a pergunta: "Existe uma tarefa que os computadores quânticos possam executar que os computadores clássicos não podem?" Um relatório recente do ECCC de Scott Aaronson (ver Conjectura 9 na página 5) destaca uma conjectura que, se comprovada, forneceria fortes evidências contra a Tese Estendida de Church-Turing.

Se alguém contestasse a Tese Estendida de Church-Turing, poderia parecer assim - especificamente, demonstrando uma tarefa eficientemente computável que uma máquina de Turing (clássica) não pode computar com eficiência.

Daniel Apon
fonte
2
Para esclarecer, a computação quântica apenas põe em questão a tese eficiente / estendida / forte de Church-Turing, que afirma que todos os modelos de computação realizáveis ​​podem ser simulados em uma máquina de Turing em tempo polinomial. A tese normal de Church-Turing não impõe restrições à eficiência. Computadores quânticos não têm esperança de derrubar esta versão porque uma máquina de Turing pode simplesmente simular todos os ramos exponencialmente numerosos de uma computação quântica em tempo finito.
Ian
Sim, obrigado por isso - eu corrigi meu uso desleixado dos dois termos.
Daniel Apon
Hmmm ... mas de acordo com as definições padrão, o ECT já não foi conclusivamente refutado? Alice: "Aqui está uma amostra de dígitos binários verdadeiramente aleatórios calculados pela minha rede óptica quântica (de um modo)". Bob: "Aqui está uma amostra de dígitos pseudo-aleatórios calculados por uma máquina de Turing clássica". Alice: "Desculpe, Bob ... sua amostra é algorítmica compressível e a minha não. Portanto, meus dados demonstram que o ECT é falso!" Formalmente falando, o raciocínio de Alice é impecável. No entanto, nos testes de validação ausentes das alegações de Alice, devemos ficar satisfeitos?
precisa saber é o seguinte
4

Os seguintes artigos de Selim Akl podem ser interessantes e relevantes para a discussão:

Akl, SG, "Três contra-exemplos para dissipar o mito do computador universal", Parallel Processing Letters, vol. 16, nº 3, setembro de 2006, pp. 381 - 403.

Akl, SG, "Mesmo máquinas de aceleração não são universais", International Journal of Unconventional Computing, vol. 3, n. 2, 2007, pp. 105 - 121.

Nagy, M. e Akl, SG, "Paralelismo no processamento quântico de informações derrotam o Computador Universal", Parallel Processing Letters, Edição Especial sobre Problemas Computacionais Não Convencionais, vol. 17, nº 3, setembro de 2007, pp. 233 - 262.

Aqui está o resumo do primeiro:

É mostrado que o conceito de um computador universal não pode ser realizado. Especificamente, são exibidas instâncias de uma função computável F que não podem ser computadas em nenhuma máquina U que é capaz de apenas um número finito e fixo de operações por etapa. Isso permanece verdadeiro mesmo que a máquina U seja dotada de uma memória infinita e a capacidade de se comunicar com o mundo exterior enquanto tenta calcular F. Também permanece verdadeira se, além disso, for concedido um tempo indeterminado de tempo a U para calcular F. Este resultado se aplica não apenas a modelos idealizados de computação, como a Máquina de Turing e similares, mas também a todos os computadores de uso geral conhecidos, incluindo computadores convencionais existentes (sequenciais e paralelos), bem como aos não convencionais contemplados, como como computadores biológicos e quânticos.

Massimo Cafaro
fonte
Você pode fornecer um link para o primeiro artigo que não esteja atrás de um paywall? Qual é a definição deles de "função computável"? Sob a definição padrão (há uma máquina de Turing que calcula a função de) sua alegação é, por definição falsa ...
Christopher Monsanto
Acabei de enviar o artigo por e-mail.
Massimo Cafaro
Aqui está um destes artigos: research.cs.queensu.ca/home/akl/techreports/even.pdf . Mais aqui: research.cs.queensu.ca/Parallel/projects.html . Não existe uma definição real de "computador" no artigo, apenas uma descrição ondulada à mão. Presumivelmente, essa descrição ondulada à mão pode ser formalizada com um pouco de trabalho, usando o modelo da máquina de Turing ou algo semelhante como base.
Sasho Nikolov
Matematicamente, o principal teorema é uma trivialidade: você define a tarefa computacional para exigir que as operações sejam executadas pelo tempo . Então, como o número de operações executadas pelo computador por etapa de tempo é definido como no máximo alguma constante , defina . Portanto, o que está à mão é definir um "problema" incomum. Depois, há um monte de filosofar por que isso é supostamente interessante. Eu acho que não é. Mas as pessoas são livres para desperdiçar suas vidas como quiserem. Só espero que essa pessoa não esteja supervisionando os alunos para trabalhar nisso. t c W ( t ) > c tW(t)tcW(t)>ct
Sasho Nikolov
-6

Como isso pode ser verdade? Um computador clássico não pode simular com eficiência um computador quântico. Existem algoritmos quânticos que fornecem velocidade exponencial em computadores clássicos executando algoritmos clássicos: o algoritmo de Shor sendo um.

Robert McGwier
fonte
3
1) Pode haver um algoritmo de fatoração polytime clássico. Não conhecemos um, mas sua existência é totalmente consistente com o estado da teoria da complexidade. 2) A tese original de Church-Turing é sobre computabilidade, não sobre computabilidade eficiente .
Sasho Nikolov