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

39

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

user1561358
fonte
5
Perguntas como "X é uma característica definidora do universo externo ( sic )?" é uma questão de física, já que a física é exatamente o estudo das "leis do universo". A ciência da computação trata de objetos matemáticos que às vezes são implementáveis ​​por meios físicos.
Bakuriu
2
Eu recomendo olhando em "super máquinas de Turing", especialmente aqueles como proposto por Tem Siegelmann: umass.edu/newsoffice/article/... e binds.cs.umass.edu/papers/1995_Siegelmann_Science.pdf
nobillygreen
1. Pedimos que você faça apenas uma pergunta por post, por favor. Se você tiver outras perguntas, poderá publicá-las separadamente, depois de ver as respostas para isso. Além disso, perguntas sobre as características definidoras do nosso universo são questões de física e estão fora de tópico aqui. Estou editando as perguntas complementares, para ajudar você a se concentrar em uma única pergunta. Você pode publicá-las separadamente (consulte o histórico de revisões para encontrá-las novamente). 2. Que pesquisa você fez? Quais são seus pensamentos? Uma pergunta de uma frase é muito curta. Tente editá-lo para aperfeiçoá-lo; isso ajudará a fornecer respostas melhores.
DW
3. "Podemos assumir que ..." - não, claro que não. Por que você acha que pode assumir isso? Você não pode simplesmente assumir algo porque seria bom se fosse verdade, ou parece que pode ser verdade, ou porque não vemos imediatamente uma razão pela qual isso seria falso. A ciência da computação tem a ver com prova, não apenas com a suposição de coisas. Qual é a sua verdadeira pergunta?
DW

Respostas:

26

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.

Yuval Filmus
fonte
Na verdade, eu tenho o blog Scotts já marcado. :) De qualquer forma, uma vez que a tese da TC ainda é válida hoje (a menos que algo tenha acontecido, eu desconheço) tudo o que resta é falar sobre a definição de computável ou procurar uma máquina que de alguma forma desaprove a TC.
precisa saber é o seguinte
3
"Como discutido neste ensaio, a teoria da complexidade já se ramificou muito além das máquinas determinísticas de Turing, para incorporar (por exemplo) a mecânica quântica, a computação paralela e distribuída e processos estocásticos, como a evolução darwiniana". ( Por Filósofos deve se preocupar com Complexidade Computacional , por Scott Aaronson , p 49.)
reinierpost
1
Também acho digno de nota que os computadores quânticos não aceleram uma tarefa arbitrária do AFAIK. E eles "apenas" a aceleram em no máximo 2 ^ N, onde N é o número de bits quânticos.
que você
13

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".

reinierpost
fonte
por "computação por um único processador executando etapas estritamente sequencialmente sem interferência externa", você quer dizer que, se um computador tiver interferência externa ou puder trabalhar em paralelo, é muito mais poderoso que uma máquina de turing?
kate
1
Nem tanto. Se tudo o que você deseja saber é quais mapeamentos de entradas finitas para saídas finitas podem ser calculados, então adicionar esses dados não lhe dará mais poder: você não poderá calcular mais mapeamentos do que antes.
Reinierpost
5

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. )

Π20 0 Essa desculpa surgiu de uma conversa com outro Thomas, a saber Thomas Chust.)

Thomas Klimpel
fonte