Computadores quânticos e máquinas de Turing: as máquinas de Turing ainda são uma medida precisa?

Na aula da semana passada, meu professor comentou e disse que as máquinas de Turing são usadas como uma medida / modelo padrão do que é computável e são uma base útil de discussão para esse assunto. Ela também disse que todas as variantes de máquinas de Turing são comprovadamente equivalentes em termos computacionais - lidas, tão poderosas - quanto uma a outra. W

Comentei e disse ontem que, com relação à capacidade de computação, notei que algumas máquinas de turing podem levar incrivelmente grandes quantidades de tempo para calcular algo muito simples, enquanto uma máquina de turing com mais fitas pode calcular algo com uma complexidade assintótica mais baixa em relação ao número das etapas necessárias.

Ela disse que, com relação ao discurso de classe, o tempo de execução de um algoritmo específico em uma máquina de turing não altera a definição de computabilidade, nem o poder com o qual medimos a computabilidade. "Estamos preocupados com o que é computável, não com o que é computável com eficiência neste momento". Portanto, não importa se as máquinas de turing têm mais e mais fitas, e mais e mais fitas implica que ele pode calcular em etapas menores. Ok, entendo que estamos realmente focados no que é computável, não na velocidade com que podemos computá-lo.

Algo sobre isso me incomoda, porque até esse momento, algoritmos com complexidade assintótica anormalmente grande de tempo e espaço realmente definem os limites do que é, talvez eu deva dizer, praticamente computável.

Então, eu tenho algumas perguntas:

1. Suponha que tenhamos um modelo para uma máquina de turbulência quântica , isso deve ser equivalente a uma máquina de turing "regular", certo?

Então, a resposta para essa pergunta, eu acho, realmente está indo na minha razão de escrever este post. A tecnologia de computação quântica antiqua as definições clássicas do que é computável através de uma máquina de turing?

2. Isso está acima da minha cabeça e devo excluir esta postagem? Não pretendo ser precoce, apenas não vi uma pergunta semelhante à minha.

Você está misturando a teoria da computabilidade (também conhecida como teoria da recursão ) e a teoria da complexidade (ou complexidade computacional ). A teoria da computabilidade é um vasto assunto matemático que estuda as ramificações do conceito de computação . Não lida com a complexidade da computação. Como seu professor menciona, todos os modelos de computação (completos em Turing) são os mesmos do ponto de vista da teoria da computabilidade. A teoria da computabilidade, embora seja um assunto matemático interessante, não é um bom modelo para a computação no mundo real por esse motivo, como você mencionou.

$T(n)$$S(n)$$T(n)^c$$S(n)^c$$n$$c$$O(1)$$O(n\log n)$$\Omega(n^2)$ou mova até para ordenar números inteiros. Portanto, na área de algoritmos , outros modelos, como a máquina de RAM, substituem as máquinas de Turing.

Finalmente, os computadores quânticos podem ser modelados de várias maneiras diferentes, como a máquina quântica de Turing. Tudo computável usando computadores quânticos também é computável usando computadores clássicos e, portanto, do ponto de vista da teoria da computabilidade, as máquinas quânticas de Turing são apenas outro modelo equivalente. No entanto, as máquinas quânticas de Turing são amplamente conjecturadas para não serem polinomialmente equivalentes às máquinas clássicas de Turing: por exemplo, fatorar e logaritmo discreto são "fáceis" para máquinas quânticas de Turing (solucionáveis ​​em tempo polinomial), enquanto é conjecturado que sejam "difíceis" para máquinas de Turing clássicas (não podem ser resolvidas no tempo polinomial; embora algumas pessoas pensem que o fatoramento inteiro pode ser solucionável no tempo polinomial). Então, do ponto de vista da teoria da complexidade, diferente das máquinas de Turing clássicas.