Máquina de Turing + dilatação do tempo = resolver o problema da parada?

Existem espaços-tempo relativísticos (por exemplo, espaços-tempo MH; ver Hogarth 1994) em que uma linha do mundo de duração infinita pode estar contida no passado de um observador finito. Isso significa que um observador normal pode ter acesso a um número infinito de etapas de computação.

Supondo que seja possível que um computador funcione perfeitamente por um período infinito de tempo (e eu sei que isso é uma grande pergunta): alguém poderia construir um computador HM que viaja por essa infinita linha do mundo, calculando o problema de parada para um dado M. Se M parar , HM envia um sinal para o observador finito. Se, após um número infinito de etapas, o observador não recebe sinal, o observador sabe que M faz um loop, resolvendo o problema de parada.

Até agora, isso parece bom para mim. Minha pergunta é: se o que eu disse até agora está correto, como isso altera a prova de Turing de que o problema da parada é indecidível? Por que sua prova falha nesses momentos ?

Observe que a prova de Turing é de matemática, não de física. Dentro do modelo de uma máquina de Turing definido por Turing, a indecidibilidade do problema de parada foi comprovada e é um fato matemático. Portanto, a prova de Turing não falhará no espaço de tempo, simplesmente não provará nada sobre a relação entre o problema da parada e a dilatação do tempo.

No entanto, o que você provavelmente desejará saber é se uma 'máquina de Turing com dilatação do tempo' pode resolver o problema da parada.

Se você quiser estudar isso sobre a influência da 'dilatação do tempo' em uma máquina de Turing, precisará especificar um modelo formal pelo qual possamos entender formalmente o que significa para uma máquina de Turing fazer uso da dilatação do tempo. Infelizmente, esse formato não é adequado para fornecer um modelo formal (a menos que alguém tenha escrito um artigo sobre ele), pois a criação do modelo é muito ampla.

No entanto, não é improvável que alguma formalização seja capaz de resolver o problema da interrupção. Este artigo de Scott Aaronson, Mohammad Bavarian e Giulio Gueltrini analisa modelos computacionais sob o pressuposto de que existem os chamados ciclos fechados de tempo fechado e conclui que o problema de parada é realmente computável nesse modelo.

A máquina de Turing é um modelo matemático formal de computação, não responde a nenhuma limitação física e não se importa com efeitos relativísticos. Isso significa que a prova de Turing não falha, uma vez que a definição padrão de máquina de Turing nem sequer contém a noção de "espaço-tempo".

O que você pode tentar e fazer é definir um modelo diferente de computação inspirado na relatividade. Novamente, esse será apenas um objeto formal, e a questão de saber se ele pode ou não resolver o problema da parada pertence ao domínio da matemática e depende da sua definição específica. No entanto, a verdadeira questão agora é se esse novo modelo realmente captura corretamente os efeitos relativísticos, ou seja, ele realmente reflete nossa física e pode ser implementado em nosso mundo?

Você pode ver uma discussão sobre computação quântica. Temos uma definição formal de "máquinas quânticas de Turing", e seu poder computacional exato permanece um problema em aberto na matemática (embora nem mesmo perto do problema da parada). Ainda assim, você pode argumentar que essa definição não reflete realmente nossa compreensão da física quântica, e é necessária uma melhor. Existem argumentos que sugerem que tais máquinas nem sequer podem ser construídas, portanto seu poder exato não tem efeito na (forte) tese de Church-Turing.

Voltar à sua pergunta. Existe uma noção formal de uma máquina de Turing com tempo infinito , mas para que ela tenha algum efeito na tese de Church-Turing, é necessário que ela exista na prática. Você pode estar interessado em Scott papel , que tem uma seção sobre cálculos utilizando efeitos relativísticos, embora pareça que os argumentos ingênuos são impossíveis (no sentido de que eles são impraticáveis, como custo de tempo é substituído pelo custo de energia).

A prova de Turing mostra que nenhuma máquina de Turing pode resolver o problema da parada, não importa quanto tempo você dedique. Se sua espaçonave usava a dilatação do tempo para dar a um computador um bilhão de anos para funcionar, ainda assim não seria capaz de lhe dizer algo mais definitivo do que "Ainda não".

Aparentemente, (Obrigado, @DiscreteLizard!) Se você tiver uma viagem no tempo que não possa causar paradoxos, poderá configurar um loop de tempo que causaria um paradoxo se o computador não puder provar se a máquina de Turing pára. Ou recebe a resposta do futuro e a transmite de volta para si mesma, ou corre para sempre (e, inteligentemente, retorna uma superposição quântica que se resolve em um ciclo de tempo estável). Mas, antes de tentar isso, tenha muita certeza de que é seguro causar um paradoxo na viagem no tempo.

Uma objeção é que você definiu um processo que pode produzir entropia infinita em uma região compacta e que parece fazê-lo em um segmento finito do passado do observador. Isso significa algumas coisas

• A entropia computacional na região compacta excede a de Bekensteinligado à entropia (que é proporcional à área da superfície da região), de modo que entra em colapso em um buraco negro (instantaneamente) e nenhum sinal pode chegar até você a partir de seu interior. (A métrica Kerr descreve um espaço-tempo MH. O processo infinito só é observado como concluído quando o observador passa para o horizonte interno de eventos. Desconsiderando a incerteza atual sobre a física dessa passagem, nenhum observador remoto jamais tem acesso ao resultado da computação - apenas o observador que desapareceu no buraco negro tem o resultado. Esta não é uma descrição de um processo computacional útil. Parafraseando: "Temos um oráculo que produz a resposta correta para qualquer pergunta que você faça em tempo constante em tais de uma maneira que a resposta exista apenas no instante em que é destruída, jogando-a em um buraco negro. ")
• Uma máquina de Turing destrói informações toda vez que sobrescreve um símbolo em uma fita; portanto, pelo princípio de Landauer , um cálculo finito em uma infinita linha do mundo compactada em um segmento finito no cone de luz passado do observador deve ser observado para exigir potência infinita e emitir calor infinito durante o tempo infinitesimal é observado para operar. Ou seja, como uma interrupção é alcançada em tempo finito, é alcançada instantaneamente do ponto de vista do observador externo, de modo que toda a energia é consumida instantaneamente e todo o calor é evoluído instantaneamente. Como alternativa, se o cálculo não parar, a região compacta consome continuamente energia infinita e emite calor infinito. Resultado líquido: um buraco negro, novamente.
• Alternativamente, o princípio Landauer não se aplica a computação reversível e não são ( universais ) máquinas de Turing reversíveis . No entanto, essa máquina de Turing exige a capacidade de representar todo o espaço de estados computacionais em potencial, que é exponencial no tamanho da quantidade de fita usada, e corre rapidamente para o limite de Bekenstein. Acabamos sendo capazes de evitar o problema do calor apenas restringindo as fitas de comprimento limitado. Equivalentemente, temos um limite superior no comprimento da fita utilizável controlado pela área da superfície da região que possui uma linha mundial infinita. Se você não explica isso e seu cálculo usa muita fita, você recebe um buraco negro novamente.

É uma questão em aberto interessante se e como essas restrições se aplicam aos computadores quânticos. Pode muito bem ser que a complexidade de uma computação executável por um computador quântico seja limitada pela área de superfície do computador. Portanto, podemos ter que dobrar a área de superfície de um computador quântico extremal para obter mais um qubit de computação utilizável. Isso rapidamente leva a computadores impraticamente grandes.

Citação de Bangs, Crunches, Whimpers e Shrieks:

$\pi$

$(\exists x_1)(\exists x_2)\dots(\exists x_n)F(x_l,x_2,\dots,x_n)$$\gamma_1$$n$$\gamma_1$colhe desses trabalhos um conhecimento do valor verdadeiro da afirmação. Mas assim que os quantificadores mistos estão envolvidos, o método falha. No entanto, Hogarth (1994) mostrou como arranjos mais complicados no espaço-tempo relativístico geral podem, em princípio, ser usados ​​para verificar o valor verdadeiro de qualquer afirmação aritmética de complexidade quantitativa arbitrária. Nesse espaço-tempo, é difícil ver como manter a atitude de que não temos uma noção clara da verdade na aritmética.