Entendendo mal a tese de Church-Turing?

Minha compreensão da tese de Church-Turing é a:

• Ele limita o que pode ser calculado por qualquer processo discreto e finito.
• Embora ainda seja uma tese, não um teorema, se fosse refutada, isso não significaria apenas uma atualização para nossos modelos atuais de computação. Seria um resultado de mudança de paradigma para a matemática e a física em geral.

No entanto, muitas discussões sobre a Filosofia SE (onde eu costumo sair) se voltam para a possibilidade de computação "Super-Turing", e os argumentos na questão da filosofia da mente são frequentemente baseados na proposição de que Church-Turing é apenas uma tese e que existe. Existem várias propostas para computação super-Turing ou hipercomputação.

A fonte mais frequentemente citada para isso é o artigo da Stanford Encyclopedia of Philosophy (SEP) sobre a tese de Church-Turing .

Em particular, o artigo possui uma seção intitulada "Incompreensões da tese" , que afirma o seguinte:

Parece ter surgido um mito em relação ao artigo de Turing de 1936, a saber, que ele tratou os limites do mecanismo e estabeleceu um resultado fundamental para o efeito de que a máquina universal de Turing pode simular o comportamento de qualquer máquina. O mito passou para a filosofia da mente, geralmente com efeito pernicioso.

[...] Turing não mostrou que suas máquinas podem resolver qualquer problema que possa ser resolvido "por instruções, regras ou procedimentos explícitos", nem provou que a máquina universal de Turing "pode ​​calcular qualquer função que qualquer computador, com qualquer arquitetura, pode calcular ". Ele provou que sua máquina universal pode calcular qualquer função que qualquer máquina de Turing possa calcular; e ele apresentou, e avançou argumentos filosóficos em apoio à tese aqui chamada tese de Turing. Mas uma tese sobre a extensão de métodos efetivos - ou seja, sobre a extensão de procedimentos de um certo tipo que um ser humano não auxiliado por máquinas é capaz de realizar - não implica nenhuma implicação quanto à extensão dos procedimentos que as máquinas são capazes de realizar, até máquinas agindo de acordo com 'regras explicitamente declaradas'. Entre o repertório de operações atômicas de uma máquina, pode haver aquelas que nenhum ser humano não auxiliado por máquinas pode executar.

A seção acima mencionada e, especialmente, as passagens citadas parecem descaradamente erradas para mim, como se o autor nem sequer entendesse o conceito de uma máquina de Turing ou o que é a tese de Church-Turing. E, no entanto, o artigo é constantemente citado como fonte por aqueles que argumentam contra a tese de Church-Turing, não apenas no Philosophy SE, mas também por filósofos relativamente conhecidos como Massimo Pigliucci . As principais razões pelas quais o artigo tem tanto peso são que o SEP é considerado uma fonte respeitável na comunidade filosófica, e os artigos ali sujeitos a revisão e que o autor do artigo, Jack Copeland , é um filósofo estabelecido que publicou extensivamente em Turing e em AI.

E, no entanto, a meu ver, o artigo está fundamentalmente errado em sua apresentação da tese, não obstante a reputação da fonte e o autor.

Minhas perguntas:

1. Minha interpretação da tese de Church-Turing está correta?

2. Como refutar aqueles que usam a seção "Incompreensões" desse artigo como justificativa para a idéia de que a computação além do limite de Turing é uma perspectiva realista?

3. A hiper-computação é levada a sério pelos principais teóricos da computabilidade, ou é o equivalente do CS à fusão a frio e ao movimento perpétuo?

Os campos da filosofia e da CS aparentemente têm diferentes definições / interpretações da tese. Em CS, acredito que é padrão / aceito definir a tese de Church-Turing como a seção "Tese M" da seção "Incompreensões" do artigo (sob a visão estreita / mundana). No entanto, o artigo afirma que esta é uma definição incorreta de Church-Turing. Então, simplesmente discordamos. (E vamos tentar evitar iniciar uma discussão com eles sobre isso ... afinal, argumentos sem sentido são o seu forte .)

A abordagem adotada pelos filósofos é lamentável, pois o leigo comum provavelmente está interessado na tese de CS Church-Turing, e não na filosofia adotada no artigo. Portanto, eles citarão o artigo enquanto pensam que se refere à nossa definição prática / razoável, quando não o faz.

Então, minhas respostas para suas perguntas específicas:

1. Sim, até onde eu sei.

2. Eu diria a eles que o artigo se refere a uma definição de filosofia altamente especializada de Church-Turing. Mas, independentemente do que se chama de "verdadeira" tese de Church-Turing, a tese a seguir é quase universalmente aceita entre os cientistas da computação: "Qualquer máquina utilizável de computação que possa ser construída neste universo pode ser simulada por uma máquina de Turing".

3. Se por hipercomputação você quer dizer fisicamente possível / realizável, não, não é levado a sério. Mas é interessante estudar modelos de hipercomputação, mesmo que não possam aparecer no mundo real, e fazemos isso o tempo todo. Por exemplo, podemos considerar uma máquina de Turing que tem acesso a um oráculo que resolve o problema da parada. Este objeto é estudado o tempo todo na teoria e é incontroverso, mas ninguém acredita que um possa realmente ser construído.

O artigo da Stanford Encyclopedia of Philosophy parece estar perdendo um ponto muito importante. Não havia computadores quando Turing escreveu seu artigo de 1936. Acredito que ele já estava pensando nelas, mas para explicar suas teorias ao matemático de rua, que nunca sonhou com máquinas de computação com capacidades além das relativamente limitadas máquinas de escritório construídas por empresas como a IBM, ele teve que enquadrá-las em termos de um procedimento eficaz realizado por um ser humano.

O artigo de Gandy "Teses e princípios da Igreja para mecanismos", no The Kleene Symposium (1980), afirma que a tese de Church-Turing não se aplica a máquinas. Em seguida, fornece o que pretende ser uma prova disso para uma classe muito limitada de máquinas. Entre as coisas que Gandy afirma é que a tese original de Church-Turing não levou em consideração o paralelismo.

As máquinas de Gandy não levam em conta a possibilidade de aleatoriedade, de física não mecânica, de ação à distância, de assincronicidade, de variáveis ​​contínuas e outras coisas que podem ser usadas para construir máquinas físicas reais.

Então, a tese original de Church-Turing pretendia que Church ou Turing se aplicasse às máquinas? Andrew Hodges tem um artigo considerando esta questão, no qual cita a revisão de Church do artigo de Turing:

O autor [Turing] propõe como critério que uma sequência infinita de dígitos 0 e 1 seja “computável” para que seja possível conceber uma máquina de computação, ocupando um espaço finito e com partes funcionais de tamanho finito, que anotem as sequência para qualquer número desejado de termos, se for permitido a execução por um tempo suficientemente longo. Por uma questão de conveniência, certas restrições adicionais são impostas no caráter da máquina, mas são de natureza que obviamente não causam perda de generalidade - em particular, uma calculadora humana, fornecida com lápis e papel e instruções explícitas, pode ser considerado como um tipo de máquina de Turing.

Por isso, Church pensou claramente que a tese de Church-Turing se estendia às máquinas.

Por outro lado, parece não ter havido nenhum esforço feito por Church ou Turing para considerar as ramificações da física quântica (ou outra não elementar) na computação, portanto era claramente uma classe muito limitada de máquinas que eles estavam considerando.

As passagens citadas estão corretas. Eles destacam a distinção entre a Tese de Church-Turing (uma afirmação improvável sobre a natureza da computação) e a existência de uma Máquina Universal de Turing (um teorema matemático).

A existência da Universal Turing Machine era um fato não trivial na época em que Turing escreveu seu artigo. Atualmente, é considerado trivial e, no campo da programação, a Universal Turing Machine é chamada de intérprete , ou seja, um programa que pode executar qualquer outro programa escrito em um idioma específico.

O que as passagens citadas dizem com razão é que a existência de intérpretes não pode provar a Tese de Church-Turing.