Conjectures mathématiques équivalentes à l'arrêt d'une machine de Turing

Cette question est de savoir si chaque théorème mathématique peut être réduit à la question de savoir si une seule machine de Turing s'arrête. En particulier, je m'intéresse aux conjectures qui ne sont actuellement pas prouvées.

Par exemple: Wikipedia dit qu'il est actuellement inconnu s'il existe des nombres parfaits impairs. Puisqu'il est possible de décider si un nombre donné est parfait, on pourrait écrire une machine de Turing qui vérifie tour à tour chaque nombre impair et s'arrête s'il en trouve un qui est parfait. (Cette machine de Turing ne prend aucune entrée.) Si nous savions si cette machine de Turing s'arrête, alors nous saurions si la conjecture est vraie, et vice versa.

Cependant, comme autre exemple, qu'en est-il de la conjecture des nombres premiers jumeaux ? Il est possible de décider si un nombre donné est le premier nombre premier d'une paire jumelle, mais dans ce cas, nous ne pouvons pas simplement nous arrêter lorsque nous trouvons le premier, car la question est de savoir s'il existe un nombre infini. Il n'est pas clair pour moi s'il est possible de fabriquer une machine de Turing qui s'arrête si et seulement si la conjecture des nombres premiers jumeaux est vraie.

Nous pouvons sûrement fabriquer une machine de Turing qui s'arrête si et seulement si la conjecture des nombres premiers jumeaux est prouvable dans l'arithmétique Peano ou un autre système formel, mais c'est une question différente, car elle pourrait être vraie mais non prouvable dans le système particulier que nous choisissons.

Donc mes questions sont

• Est-il possible de fabriquer une machine de Turing qui s'arrête si et seulement si la conjecture des nombres premiers jumeaux est vraie? (Et si oui, comment?)
• Est-il possible, en général, de faire une machine de Turing qui s'arrête si et seulement si une affirmation mathématique donnée est vraie? Cette machine de Turing peut-elle être construite algorithmiquement à partir de la déclaration formelle?
• Si ce n'est pas possible en général, existe-t-il un moyen de classer les énoncés mathématiques en fonction de leur équivalence à l'arrêt d'une seule machine de Turing, ou d'une machine de Turing avec un oracle , etc.? Si oui, cette classification est-elle décidable pour une déclaration donnée?

Votre hiérarchie arithmétique répond à votre question . L'existence d'un nombre parfait impair est une déclaration , et vous pouvez donc le tester à l'aide d'une machine Σ 1 , ce qui s'arrête si la déclaration est vraie. La conjecture principale jumelle est une déclaration Π 2 , et vous pouvez donc construire une MT avec accès à l'oracle d'arrêt qui s'arrête si la déclaration est fausse.$\Sigma_1$$\Sigma_1$$\Pi_2$

Dans un sens strict logique, vous pouvez toujours faire une machine de Turing qui arrête IFF déclaration est vérifiée:$\phi$

1. Si tient, alors prenez une machine qui s'arrête.$\phi$
2. Si ne tient pas, prenez une machine qui ne s'arrête pas.$\phi$

Pour voir que cette construction est valide, considérez la forme logique de votre déclaration:

Vous pouvez dissiper cette confusion en posant des questions légèrement différentes:

Qu'est - ce qu'un ensemble d'instructions tel qu'il existe une machine de Turing qui arrête sur φ ∈ & phiv ssi φ est valide?$\Phi$$\phi \in \Phi$$\phi$

Au- dessus je l' ai indiqué que déclarations forment un tel ensemble.$\Sigma_1$

$f(1)=2$$f(2)=4$$f(n+1)=f(n)!$$n \geq 2$$n$$\Theta_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}$

$\Theta_{16}$$f(16)+3$$W \subseteq \mathbb{N}$$W$$W$$W$

$\Theta_{16}$$0'$