Quels sont les exemples les plus simples de programmes dont nous ne savons pas s'ils se terminent?

Le problème d'arrêt indique qu'aucun algorithme ne déterminera si un programme donné s'arrête. En conséquence, il devrait y avoir des programmes sur lesquels nous ne pouvons pas dire s'ils se terminent ou non. Quels sont les exemples les plus simples (les plus petits) connus de tels programmes?

Un exemple assez simple pourrait être un programme testant conjecture de Collatz :

Il est connu qu'il s'arrête pour $n$ jusqu'à au moins $5 × 2^{60} ≈ 5.764 × 10^{18}$ , mais en général c'est un problème ouvert.

Le problème d'arrêt indique qu'aucun algorithme ne déterminera si un programme donné s'arrête. En conséquence, il devrait y avoir des programmes sur lesquels nous ne pouvons pas dire s'ils se terminent ou non.

"Nous" ne sommes pas un algorithme =) Il n'y a pas algorithme général qui pourrait déterminer si un programme donné s'arrête pour chaque programme .

Quels sont les exemples les plus simples (les plus petits) connus de tels programmes?

Considérez le programme suivant:

n = 3
while true:
    if is_perfect(n):
            halt()
    n = n + 2

La fonction is_perfect vérifie si n est un nombre parfait . On ne sait pas s'il existe des nombres impairs parfaits, nous ne savons donc pas si ce programme s'arrête ou non.

Vous écrivez:

Le problème d'arrêt indique qu'aucun algorithme ne déterminera si un programme donné s'arrête. En conséquence, il devrait y avoir des programmes sur lesquels nous ne pouvons pas dire s'ils se terminent ou non.

Il s'agit d'un non-sequitur, dans les deux sens. Vous succombez à une erreur commune qui mérite d'être abordée.

$P$$P$$P$ problème de asphaltage.

Ce n'est que si vous exigez que l'algorithme résout le problème de l'arrêt de tous les programmes¹ que vous puissiez montrer qu'aucun tel algorithme ne peut exister.

Maintenant, savoir que le problème de l'arrêt est indécidable n'implique pas qu'il existe des programmes dont personne ne peut prouver l'arrêt ou la boucle. Même si vous n'êtes pas plus puissant qu'une machine de Turing (ce qui n'est qu'une hypothèse, un fait non prouvé), tout ce que nous savons, c'est qu'aucun algorithme / personne ne peut fournir une telle preuve pour tous les programmes. Une personne différente peut décider pour chaque programme.

Quelques lectures plus connexes:

• $\pi$
• Puissance de calcul humaine: les humains peuvent-ils décider du problème d'arrêt des machines de Turing?
• Algorithme pour résoudre le "problème d'arrêt de Turing"
• Synthèse du programme, décidabilité et problème d'arrêt
• Est-il possible de résoudre le problème d'arrêt si vous avez une entrée contrainte ou prévisible?
• Pourquoi les fonctions totales ne sont-elles pas énumérables?

Vous voyez donc que votre question réelle (comme répété ci-dessous) n'a rien à voir avec le fait que le problème d'arrêt soit calculable. Du tout.

Quels sont les exemples les plus simples (les plus petits) connus de [programmes que nous ne savons pas arrêter ou boucler]?

C'est en soi une question valable; d'autres ont donné de bonnes réponses. Fondamentalement, vous pouvez transformer chaque déclaration$S$avec une valeur de vérité inconnue dans un exemple, à condition qu'il n'avoir une valeur de vérité:

$\qquad\displaystyle g(n) = \begin{cases}1, &S \text{ true},\\ g(n+1), &\text{else}.\end{cases}$

Certes, ce ne sont pas très «naturels».

1. Pas nécessairement tous , mais "beaucoup" dans un certain sens. Infiniment, au moins.

Tout problème ouvert concernant l'existence d'un nombre ayant des propriétés particulières donne lieu à un tel programme (celui qui recherche un tel nombre). Par exemple, prenez la conjecture de Collatz; puisque nous ne savons pas si c'est vrai, nous ne savons pas non plus si le programme suivant se termine:

    n:=1;
    found:=false;
    while not found do
      s:={};
      i:=n;
      while i not in s do
        add i to s;
        if i even then i:=i/2 else i:=3i+1
      if 1 not in s then found:=true;
      n:=n+1  

Étant donné que le problème de Castor occupé n'est pas résolu pour une machine de Turing à 5 états et 2 symboles, il doit y avoir une machine de Turing avec seulement cinq états et seulement deux symboles dont il n'a pas été démontré qu'elle s'arrête ou non lorsqu'elle est démarrée pour une bande vide . Il s'agit d'un programme très court, concis et clos.

la question est délicate car la décidabilité (l'équivalent CS formalisation / généralisation du problème d'arrêt) est associée aux langues et doit donc être refondue dans ce format. cela ne semble pas être souligné, mais de nombreux problèmes ouverts en mathématiques / CS peuvent être facilement convertis en problèmes (langues) de décidabilité inconnue. cela est dû à une correspondance étroite entre la démonstration du théorème et l'analyse de la (non) décidabilité. par exemple (un peu comme l'autre réponse par rapport à des nombres impairs parfaits), prenons la conjecture des nombres premiers jumeaux qui date des Grecs (il y a plus de 2 millénaires) et qui est soumise à d'importantes avancées de recherche récentes, par exemple par Zhang / Tao. le convertir en un problème algorithmique comme suit:

Entrée: n . Sortie: Y / N il existe au moins n nombres premiers jumeaux.

l'algorithme recherche les nombres premiers jumeaux et s'arrête s'il en trouve n . on ne sait pas si cette langue est décidable. la résolution du problème des nombres premiers jumeaux (qui demande s'il existe un nombre fini ou infini) résoudrait également la décidabilité de ce langage (s'il est également prouvé / découvert combien il y en a, s'il est fini).

un autre exemple, prenons l' hypothèse de Riemann et considérons ce langage:

Entrée: n . Sortie: O / N il existe au moins n zéros non triviaux de la fonction zêta de Riemann.

l'algorithme recherche des zéros non triviaux (le code n'est pas particulièrement complexe, son semblable à la recherche de racine, et il existe d'autres formulations équivalentes qui sont relativement simples, qui calculent essentiellement des sommes de "parité" de tous les nombres premiers inférieurs à x, etc.) et s'arrête si il en trouve n et encore une fois, on ne sait pas si ce langage est décidable et la résolution est "presque" équivalente à la résolution de la conjecture de Riemann.

maintenant, que diriez-vous d'un exemple encore plus spectaculaire? ( mise en garde, probablement plus controversée également)

Entrée: c: Sortie: Y / N il existe un algorithme O (n ^c ) pour SAT.

de même, la résolution de la décidabilité de ce langage est presque équivalente au problème P vs NP . cependant, il existe un cas moins évident pour un code "simple" pour le problème dans ce cas.

Écrivez un programme simple qui vérifie si pour chaque n, $1 ≤ n ≤ 10^{50}$, the Collatz sequence starting with n will reach the number 1 in less than a billion iterations. When it has the answer, let the program stop if the answer is "Yes", and let it loop forever if the answer is "No".

We cannot tell whether this program terminates or not. (Who is we? Let's say "we" is anyone who could add a comment to my answer). However, someone with an incredibly powerful computer might tell. Some genius mathematician might be able to tell. There might be a rather small n, say n ≈ $10^{20}$ where a billion iterations are needed; that would be in reach of someone with a lot of determination, a lot of time, and a lot of money. But right now, we cannot tell.