Conjecturas matemáticas equivalentes à parada de uma máquina de Turing

11

Esta questão é sobre se todo teorema matemático pode ser reduzido à questão de uma única máquina de Turing parar. Em particular, estou interessado em conjecturas que atualmente não são comprovadas.

Por exemplo: a Wikipedia diz que atualmente não se sabe se existem números perfeitos ímpares. Como é decidido se um determinado número é perfeito, pode-se escrever uma máquina de Turing que verifique cada número ímpar por vez e pára se encontrar um que seja perfeito. (Esta máquina de Turing não recebe nenhuma entrada.) Se soubéssemos se essa máquina de Turing parou, saberíamos se a conjectura é verdadeira e vice-versa.

No entanto, como outro exemplo, o que dizer das conjeturas dos primos gêmeos ? É decidível se um determinado número é o primeiro primo em um par gêmeo, mas neste caso não podemos parar quando encontramos o primeiro, porque a questão é se existe um número infinito. Não está claro para mim se é possível fazer uma máquina de Turing que pare se e somente se a conjectura dos primos gêmeos for verdadeira.

Nós certamente pode fazer uma máquina de Turing que pára se e somente se a conjectura de primos gémeos é demonstrável dentro de aritmética de Peano ou algum outro sistema formal, mas isso é uma questão diferente, uma vez que pode ser verdade, mas não demonstrável no sistema particular que nós escolhemos.

Então, minhas perguntas são

É possível fazer uma máquina de Turing que pare se e somente se a conjectura dos primos gêmeos for verdadeira? (E se sim, como?)
É possível, em geral, fabricar uma máquina de Turing que interrompe se e somente se alguma afirmação matemática é verdadeira? Esta máquina de Turing pode ser construída algoritmicamente a partir da declaração formal?
Se não for possível, em geral, existe alguma maneira de classificar as afirmações matemáticas como equivalentes à interrupção de uma única máquina de Turing ou de uma máquina de turing com um oráculo , etc.? Em caso afirmativo, essa classificação é decidível para uma determinada afirmação?

formal-languages computability mathematical-foundations Nathaniel
fonte

O que significa "verdadeiro"? Com que tipo de modelos estamos avaliando essa verdade em relação? Você terá que definir isso primeiro, eu acho.

Jake

Acho que todas essas máquinas de Turing podem apenas testar a provabilidade. Mesmo se você não estiver explicitamente iterando sobre declarações verdadeiras no PE, ainda estará procurando uma prova de outra forma. A diferença é que a existência ímpar e perfeita de números obviamente não pode ser verdadeira e improvável, enquanto primos gêmeos podem.

usar o seguinte código

Qualquer conjectura sobre conjuntos incontáveis não pode ser expressa usando máquinas de Turing.

Raphael

12

$\Sigma_1$ $\Sigma_1$ $\Pi_2$

$\phi$

$\phi$
$\phi$

Para verificar se essa construção é válida, considere a forma lógica da sua declaração:

\forall ϕ \exists T . ϕ \Leftrightarrow T halts .

$\forall \phi \exists T . \phi \Leftrightarrow T\text{ halts}.$

$\Phi$ $\phi \in \Phi$ $\phi$

$\Sigma_1$

Yuval Filmus
fonte

Obrigado, acho que a hierarquia aritmética é exatamente o que eu estava pedindo. Penso que o que realmente pretendia perguntar era "existe uma função computável total de (algum subconjunto de) instruções matemáticas para máquinas de Turing que não recebem entrada, de modo que a máquina correspondente a uma determinada instrução seja interrompida se a afirmação for verdadeira?" Mas é claro que isso é equivalente à versão que você propôs.

Nathaniel #

0

$f(1)=2$ $f(2)=4$ $f(n+1)=f(n)!$ $n \geq 2$ $n$ $\Theta_n$

S \subseteq {x_{i}! = x_{k} : i, k \in {1, \dots, n}} \cup {x_{i} \cdot x_{j} = x_{k} : i, j, k \in {1, \dots, n}}

$S \subseteq \{x_i! = x_k: i,k \in \{1,\ldots,n\}\} \cup \{x_i \cdot x_j=x_k: i,j,k \in \{1,\ldots,n\}\}$

$x_1,\ldots,x_n$ $1$ $(x_1,\ldots,x_n)$ $\min(x_1,\ldots,x_n) \leq f(n)$ $\Theta_1,\ldots,\Theta_{16}$

A declaração prova a implicação: se existe um primo gêmeo maior que , existem infinitos primos gêmeos, consulte este artigo de A. Tyszka ( nos conjuntos modo que o infinito de seja equivalente à existência em de um elemento que seja maior que um número limite calculado com a definição de ) $\Theta_{16}$ $f(16)+3$ $W \subseteq \mathbb{N}$ $W$ $W$ $W$

Ou seja, assumindo a instrução , uma única consulta para decide o problema dos gêmeos primos. $\Theta_{16}$ $0'$

Apoloniusz Tyszka
fonte

Conjecturas matemáticas equivalentes à parada de uma máquina de Turing

Respostas: