Quels sont les programmes très courts avec un statut d'arrêt inconnu?

32

Ce programme de 579 bits dans le calcul binaire Lambda a un état d'arrêt inconnu:

01001001000100010001000101100111101111001110010101000001110011101000000111001110
10010000011100111010000001110011101000000111001110100000000111000011100111110100
00101011000000000010111011100101011111000000111001011111101101011010000000100000
10000001011100000000001110010101010101010111100000011100101010110000000001110000
00000111100000000011110000000001100001010101100000001110000000110000000100000001
00000000010010111110111100000010101111110000001100000011100111110000101101101110
00110000101100010111001011111011110000001110010111111000011110011110011110101000
0010110101000011010

Autrement dit, on ne sait pas si ce programme se termine ou non. Pour le déterminer, vous devez résoudre la conjecture de Collatz - ou, au moins, pour tous les nombres jusqu'à 2 ^ 256. Sur ce dépôt, il y a une explication complète de la façon dont ce programme a été obtenu.

Existe-t-il des programmes BLC (beaucoup) plus courts qui ont également un statut d'arrêt inconnu?

MaiaVictor
la source
6
Question très liée . Votes de la communauté, veuillez: dupliquer?
Raphael
9
La tâche d'exprimer programme un en aussi peu de bits possible semble être une question de code Golf , moins l' ordinateur la science .
Raphael
2
Je pense que la réponse de Ricky sur les MT à 5 états est meilleure que celle sur la question d'origine. Si celui-ci est fermé comme dupe, la réponse peut-elle être déplacée?
David Richerby
6
Il vous manque un détail clé: vous n'avez pas spécifié dans quelle langue le programme doit être écrit. Votre exemple utilise le calcul lambda binaire - est-ce la seule langue qui vous intéresse? Nous pouvons voir qu'il est trivial de développer un programme 1 bit dont l'état d'arrêt est inconnu, simplement en incorporant le corps de l'algorithme directement dans le langage lui-même. C'est une faille, mais vous devez y faire attention lorsque vous demandez des solutions de golf. Ils adorent leurs failles! La complexité de Kolmogov peut être un sujet important à explorer ici.
Cort Ammon - Rétablir Monica le

Réponses:

30

Oui. Cette page indique qu'il ya 98 5 état des machines de Turing dont les statuts ne sont pas connus arrêt. Chose ennuyeuse, elle ne donne aucun exemple de telles machines, mais cette page de 26 ans donne 2 machines Turing à 5 états dont les états d'arrêt étaient apparemment inconnus à l'époque. (La recherche de "simple compteur" vous amènera directement entre ces 2.) Je les ai copiés ici au cas où ce lien tomberait:

Input Bit   Transition on State     Steps            Comment
             A   B   C   D   E

    0       B1L C1R D0R A1L H1L   > 2*(10^9)       ``chaotic''
    1       B1R E0L A0L D0R C0L

    0       B1L A0R C0R E1L B0L       ?        complex ``counter''
    1       A1R C0L D1L A0R H1L

la source
Le bas de la page dit: $ Date: 2007/11/03, alors comment il a 26 ans?
Falaque
1
@Falaque Le haut de la page indique "Cette page est la réécriture HTML de l'auteur de ... février 1990". Le texte a 26 ans, le rendu en HTML date de (ou dernière mise à jour) en 2007.
IMSoP
5

Conjecture de Collatz:

Le programme suivant s'arrête toujours:

void function( ArbitraryInteger input){
     while( input > 1){
            if(input % 2 == 0)
                input /= 2;
            else
                input = (input*3) + 1;
     }

     // Halt here
}

Légère variation (toujours une conjecture, car elle est basée sur un résultat de celui de Collatz):

Pour certaines entrées, le programme suivant n'entrera jamais deux fois dans le même état (où l'état est déterminé par la valeur détenue par "input"):

void function( ArbitraryInteger input){
     while( input >= 1){ // notice the "="
            if(input % 2 == 0)
                input /= 2;
            else
                input = (input*3) + 1;
     }
}

Notez que le deuxième programme ne s'arrête jamais, que le premier programme s'arrête ou non.

On pense que le premier programme se termine toujours pour toute entrée, cependant, nous n'en avons pas la preuve, et il peut toujours exister un entier pour lequel le programme ne s'arrête pas (il y a aussi un prix de 100 $ pour le prouver) .

Le deuxième programme est également intéressant: il indique que le programme n'entrera jamais deux fois dans le même état pour une entrée, ce qui nécessite essentiellement que le premier programme ait une séquence connue pour diverger sans se répéter. Il ne requiert pas seulement que la conjecture de Collatz soit fausse, mais elle exige qu'elle soit fausse et sans boucles , en dehors de la boucle évidente 1,4,2,1.

  • Si Collatz n'a que des contre-exemples en boucle, la variation de la conjecture est fausse

  • Si Collatz est faux sans boucles, la variation de la conjecture est vraie

  • Si Collatz est vrai, la variation est fausse

  • Si Collatz est faux à la fois parce qu'il a des boucles et parce qu'il a un nombre pour lequel il diverge, la variation de la conjecture est vraie (il suffit d'un nombre pour lequel il diverge sans entrer dans une boucle)

Je pense que la variation est plus intéressante (pas seulement parce que je l'ai trouvée par accident et que je l'ai remarquée grâce à @LieuweVinkhuijzen), mais parce qu'elle nécessite en fait une vraie preuve. En forçant brutalement, nous pourrons peut-être trouver une boucle un jour ou l'autre (et ce sera une boucle de plus de 70 nombres: l'état actuel de la technique est qu'il ne peut pas y avoir de boucles infinies plus courtes que 68 environ), et brute le forçage n'est pas intéressant: c'est juste un calcul de nombres. Cependant nous ne pouvons pas forcer brutalement une séquence infinie divergente, nous ne savons pas si elle se terminera vraiment sans une preuve réelle.

EDIT: J'ai sauté la partie sur Collatz Conjecture désolé, j'ai vraiment répondu par cœur avec un algorithme que j'ai lu il y a quelques années, je ne m'attendais pas à ce que cela soit déjà mentionné.

EDIT2: Un commentaire m'a fait remarquer que j'ai écrit l'algorithme avec une erreur, cependant, cette erreur rend en effet ma réponse différente de la conjecture de Collatz (mais une variation directe de celle-ci).

Développeur de jeu
la source
1
input > 1input >= 11421
Vous avez raison, je voulais mettre un >, cependant tant que nous n'avons pas de preuve d'arrêt avec >nous ne pouvons pas être sûrs que nous atteindrons la 1 -> 4 -> 2 -> 1boucle (par exemple si elle ne se termine pas pour >cela, ne le faites pas ) t atteindre >=)
GameDeveloper
1
>=14211421>=>
2
n<1n=1n4n>1n11
1
C'est vrai :) Vous avez raison, j'aurais dû ajouter «si la conjecture de Collatz est vraie» à mon premier commentaire. Je vois ton montage, très bien. Vous n'avez pas besoin du deuxième programme, car la conjecture `` ce programme ne passe jamais deux fois dans le même état '' n'est pas non plus résolue du premier programme: il est possible qu'il y ait un nombre qui ne diverge pas à l'infini, mais se retrouve coincé dans un grande boucle quelque part en nombre très élevé.
Lieuwe Vinkhuijzen