Máquinas teóricas mais poderosas que as máquinas de Turing

Existem máquinas teóricas que excedem a capacidade das máquinas de Turing em pelo menos algumas áreas?

A tese de Church-Turing (em uma formulação) afirma que tudo o que pode ser fisicamente computável também pode ser computado em uma máquina de Turing. Supondo que você acredite nessas teses e tendo em vista que está interessado em funções que essas máquinas possam computar (e não em, digamos, na computação interativa), nenhuma hipercomputação é possível.

A tese de Church-Turing se preocupa apenas com o que é computável, mas não com a eficiência da computação. Sabe-se que as máquinas de Turing não são tão eficientes, embora simulem polinomialmente computadores clássicos. Acredita-se que os computadores quânticos sejam exponencialmente mais eficientes do que as máquinas de Turing. Nesse sentido, você pode vencer as máquinas de Turing (se você pudesse construir apenas um computador quântico escalável).

Scott Aaronson provavelmente tem mais a dizer sobre isso - vou deixar você procurar por conta própria.

Sim, existem máquinas teóricas que excedem as máquinas de Turing em potência computacional, como máquinas Oracle e máquinas de tempo infinito de Turing . A palavra-chave que você deve alimentar para o Google é hipercomputação .

A tese de Church-Turing não precisa ser tomada como um artigo de fé; provavelmente faz mais sentido considerá-lo como declarando uma descrição, uma definição , do que queremos dizer com o termo "computação", e também é uma noção bastante restrita de computação: computação por um único processador executando etapas estritamente sequencialmente sem externa interferência. Certos aspectos da computação sobre os quais precisamos raciocinar não são cobertos por essa noção, e muitas peças adicionais de teoria matemática foram desenvolvidas na ciência da computação para abordar essas preocupações.

Portanto, a tese de Church-Turing não é tanto uma característica definidora de nosso universo, mas é uma característica definidora de uma maneira particular de fazer certas coisas em nosso universo.

A esse respeito, pode ser comparado à geometria euclidiana. Nosso universo é inerentemente euclidiano? Por que nossos métodos de medir terras são limitados por seus princípios? Não podemos ter uma hipergeometria que permita uma medição mais poderosa da terra? A resposta é: podemos e fazemos, mas nem sempre chamamos os resultados de "medição da terra" ou "geometria".

Da mesma forma, nossa teoria e prática em relação à computação se estendem além do que as máquinas de Turing podem descrever (por exemplo, existem cálculos de processo para descrever sistemas concorrentes), mas não chamamos necessariamente essas extensões de "computação".

Uma fraqueza teórica de uma máquina de Turing é sua previsibilidade. Um oponente todo poderoso e onisciente poderia explorar essa fraqueza ao jogar algum jogo contra a máquina de Turing. Portanto, se uma máquina teórica tivesse acesso a uma fonte aleatória que seu oponente não poderia prever (e pudesse ocultar seu estado interno do oponente), essa máquina teórica seria mais poderosa que uma máquina de Turing.

O problema com esse tipo de máquina teórica na vida real não é se a fonte aleatória é perfeitamente aleatória ou não (supor que ela seja perfeitamente aleatória é uma idealização inofensiva), mas que nunca podemos ter certeza se fomos bem-sucedidos em ocultar nossos recursos internos. estado do nosso oponente. Portanto, no caso concreto, nunca se pode ter certeza se é válido idealizar a instância atual de uma situação por essa máquina. Isso é apenas um pouco melhor do que a situação para a maioria dos tipos de hipercomputação, onde não está claro para mim quais situações idealizadas devem ser modeladas por elas (uma vez eu respondi: então, preciso de algum tipo de máquina milagrosa que sabe tudo para resolver "ER", Eu não sabia que essas máquinas existem. )

$\Pi_2^0$ Essa desculpa surgiu de uma conversa com outro Thomas, a saber Thomas Chust.)