Est-ce que cette machine Foo s'arrête?

43

Il est notoire que déterminer si une machine de Turing s'arrête est indécidable, mais ce n'est pas nécessairement le cas pour les machines plus simples.

Une machine Foo est une machine avec une bande finie, où chaque cellule de la bande a un entier ou le symbole d’arrêt h, par exemple:

2 h 1 -1

Le pointeur d'instruction commence par pointer vers la première cellule:

2 h 1 -1
^

A chaque étape, le pointeur d'instruction avance du nombre indiqué, puis annule ce nombre. Ainsi, après une étape, les 2cellules avancent et se transforment 2en -2:

-2 h 1 -1
     ^

La machine Foo continue ainsi jusqu'à ce que le pointeur d'instruction pointe vers le symbole d'arrêt ( h). Alors, voici la pleine exécution de ce programme:

2 h 1 -1
^

-2 h 1 -1
     ^

-2 h -1 -1
         ^

-2 h -1 1
      ^

-2 h 1 1
   ^

La bande est également circulaire. Par conséquent, si le pointeur d’instruction se déplace d’un côté à l’autre de la bande, il passe de l’autre côté, par exemple:

3 h 1 3
^
-3 h 1 3
       ^
-3 h 1 -3
     ^
-3 h -1 -3
         ^
-3 h -1 3
 ^
3 h -1 3
  ^

Une chose intéressante à propos de ces machines Foo est que certaines ne s’arrêtent pas, par exemple:

1 2 h 2
^
-1 2 h 2
   ^
-1 -2 h 2
        ^
-1 -2 h -2
    ^
-1 2 h -2
        ^
-1 2 h 2
   ^

Ce programme continuera à boucler dans ces quatre derniers états pour toujours.

Alors, écrivez un programme qui détermine si une machine Foo s'arrête ou non! Vous pouvez utiliser n’importe quel format d’entrée (raisonnable) que vous aimez pour les machines Foo, et vous pouvez choisir d’utiliser0 comme symbole d’arrêt. Vous pouvez utiliser deux sorties distinctes pour le cas où cela s’arrête et le cas où ce n’est pas le cas. Votre programme doit bien sûr générer une réponse dans un délai déterminé pour toutes les entrées valides.

C'est du , alors essayez de rendre votre programme aussi court que possible!

Cas de test

2 h 1 -1
Halts
3 h 1 3
Halts
h
Halts
1 1 1 1 h
Halts
2 1 3 2 1 2 h
Halts
3 2 1 1 4 h
Halts
1 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 h -20 -21 -22 -23 -24 -25 -26 -27 -28 -29 -30 -31 -32 -33 -34 -35 -36
Halts

2 h
Does not halt
1 2 h 2
Does not halt
8 1 2 3 3 4 8 4 3 2 h
Does not halt
1 2 4 3 h 2 4 5 3
Does not halt
3 1 h 3 1 1
Does not halt
1 2 h 42
Does not halt
Leo Tenenbaum
la source
5
Juste pour en être sûr, à propos de l'algorithme permettant de résoudre ce problème. Je ne suis pas un expert en algorithme, donc je préfère demander avant de prendre la mauvaise direction. Est-ce qu'une machine Foo qui ne s'arrête pas retrouve toujours son état d'origine? Ou y a-t-il des machines "à comportement chaotique" qui ne bougent pas?
V. Courtois
5
@ V. Courtois Toutes les machines Foo qui ne s'arrêtent pas se retrouvent dans une boucle d'états, car il n'y a que très peu d'états possibles dans lesquels une machine Foo peut être (il y a n endroits possibles où le pointeur d'instruction peut être, et 2 ^ n possible configurations de bande). Chaque état a un et un seul "état suivant". Donc, si une machine Foo finit par revenir dans un état dans lequel elle était déjà, elle restera en boucle. Parce qu’il n’ya que très peu d’États, il ne peut pas continuer à se déplacer de façon chaotique, car il finira par aller à un état dans lequel il se trouve déjà.
Leo Tenenbaum
3
Cas de test suggéré: 1 2 h 42(ne s’arrête pas)
Arnauld
6
Cas de test suggéré: 3 2 1 1 4 h. Celui-ci s'arrête mais nécessite plus d'itérations que le double du nombre d'éléments.
Arnauld
10
Cas de test très long suggéré 1 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 h -20 -21 -22 -23 -24 -25 -26 -27 -28 -29 -30 -31 -32 -33 -34 -35 -36:, qui s'arrête après 786430 étapes.
Magma

Réponses:

11

C # (compilateur interactif Visual C #) , 71 octets

x=>{for(int i=0,k=0,f=x.Count;i++<1<<f;k%=f)k-=(x[k]*=-1)%f-f;i/=x[k];}

Essayez-le en ligne!

Je ne sais pas si ce qui suit est valide, car il nécessite un délégué personnalisé avec une signature de unsafe delegate System.Action<int> D(int* a); et doit être encapsulé dans un unsafebloc pour pouvoir être utilisé, mais le voici quand même:

C # (.NET Core) , 64 octets

x=>f=>{for(int i=0,k=0;i++<1<<f;k%=f)k-=(x[k]*=-1)%f-f;k/=x[k];}

Essayez-le en ligne!

Cette fonction prend un int * et retourne une action; en d'autres termes, c'est une fonction au curry. La seule raison pour laquelle j'utilise des pointeurs est due à codegolf.meta.stackexchange.com/a/13262/84206, ce qui me permet d'économiser des octets en ayant déjà une variable déjà définie avec la longueur du tableau.

Sauvegardé 9 octets grâce à @quelqu'un

Incarnation de l'ignorance
la source
Golfé votre code par 2 octets: tio.run/…
IQuick 143
@ IQuick143 Belle prise, merci
Incarnation de l'Ignorance
Je ne sais pas s'il existe des cas extrêmes pour lesquels cela ne fonctionnera pas, mais sans rompre aucun des cas de test actuels, vous pouvez le remplacer 1<<fpar 2*fpour sauvegarder un octet.
Kevin Cruijssen
1
77 octets avec l'horrible magie LINQ et le correctif d'Arnauld . Je ne sais pas du tout comment cette solution fonctionne, alors je l’ai peut-être cassée.
quelqu'un
1
63 octets via un golf normal de 1 octet et en changeant IO en error / no error. Lien vers le lien
quelqu'un
7

Python 3 , 63 89 octets

def f(x):
 for i in range(2**len(x)):a=x[0];x[0]=-a;b=a%len(x);x=x[b:]+x[:b]
 return a==0

Essayez-le en ligne!

Fonctionne également pour Python 2; un octet peut être sauvegardé dans Python 2 en remplaçant return par print et en ayant la fonction print sur stdout au lieu de return. R se tourne Truepour s'arrêter etFalse pour ne pas s'arrêter.

Merci à @Neil et @Arnauld d'avoir noté que je devais vérifier plus longtemps avant de m'arrêter. Merci à @Jitse pour avoir signalé un problème avec [2,0]. Merci à @mypetlion pour avoir noté que les valeurs absolues des bandes pourraient dépasser la longueur de la bande.

Nick Kennedy
la source
5
OK, je vais mordre: comment savez-vous que x+xc'est assez?
Neil
4
@ Neil, ce n'est pas assez. Un contre-exemple est [ 3, 2, 1, 1, 4, 0 ], qui s'arrête dans plus de 12 itérations.
Arnauld
1
len(x)*x[8,7,6,5,7,4,0,3,6]92
2
N'est-ce pas 2**len(x)encore un peu court du maximum? Je calcule le nombre d'états comme n*(2**n)(avec n=len(x)-1).
OOBalance
1
@OOBalance Je vois ce que vous voulez dire, car chaque état peut avoir un pointeur dans chaque cellule ... Cependant, je pense qu'il y a une autre limite appliquée par le fait que chaque cellule ne peut que passer en transition à deux autres cellules. En remarque: rien dans le défi ne dit qu’il doit y avoir un état d’arrêt dans l’entrée
Jo King
6

Gelée , 15 à 11 octets

N1¦ṙ⁸ḢƊÐLḢẸ

Essayez-le en ligne!

Un lien monadique qui prend l’entrée sous forme de liste d’entiers en utilisant 0 pour indiquer un arrêt. Renvoie 0 pour arrêter les entrées et 1 pour celles qui ne s’arrêtent pas.

Evite la nécessité de calculer le nombre d’itérations à cause de l’utilisation de ÐL celle-ci en boucle jusqu'à ce qu'aucun nouveau résultat ne soit vu.

Merci à @JonathanAllan pour la sauvegarde d'un octet!

Explication

      ƊÐL   | Loop the following as a monad until the result has been seen before:
N1¦         | - Negate the first element
   ṙ⁸       | - Rotate left by each of the elements
     Ḣ      | - Take just the result of rotating by the first element
         Ḣ  | Finally take the first element
          Ẹ | And check if non-zero
Nick Kennedy
la source
Économisez un octet en effectuant une rotation de toutes les entrées et en ne conservant que le premier résultat:N1¦ṙ⁸ḢƊÐLḢẸ
Jonathan Allan
5

Python 3 , 91 octets

def f(a):
	s={0,};i=0
	while{(*a,)}-s:s|={(*a,)};a[i]*=-1;i-=a[i];i%=len(a)
	return a[i]==0

Essayez-le en ligne!

-40 octets grâce à JoKing et Jitse

HyperNeutrino
la source
@JoKing 109 octets en effectuant les affectations de variables de la première ligne.
Jitse
92 octets en changeant la conversion de tuple en extension étoilée, sans commencer par un ensemble vide et en reformulant la whilecondition.
Jitse
@JoKing Zut, je n'ai jamais appris: p. 93 octets alors.
Jitse
91 octets
Jitse
@JoKing merci!
HyperNeutrino
5

Perl 6 , 46 43 36 octets

{$_.=rotate(.[0]*=-1)xx 2**$_;!.[0]}

Essayez-le en ligne!

Représente stop by 0et renvoie true si la machine s'arrête. Cela répète les 2**(length n)temps logiques , où si le pointeur se termine sur la cellule d’arrêt, il y reste, sinon il sera sur une cellule sans arrêt. Cela fonctionne car il n'y a que 2**ndes états possibles (en ignorant les cellules d'arrêt) pour la machine Foo, étant donné que chaque cellule non-stop n'a que deux états.D'accord, il y a des États que cela, mais en raison des transitions possibles limitées entre les pointeurs (et donc les États), il y aura moins de 2 ** $ _ États ... Je pense

Explication

{                                  }  # Anonymous codeblock
                     xx 2**$_         # Repeat 2**len(n) times
            .[0]*=-1                  # Negate the first element
 $_.=rotate(        )                 # Rotate the list by that value
                             ;!.[0]   # Return if the first element is 0
Jo King
la source
2
L'état de la machine Foo comprend également l'emplacement du pointeur, pas seulement les signes de chaque cellule.
Magma
1
Esquisse d'une épreuve pour une machine Foo avec du ruban adhésif a_1 ... a_n 0. Considérez un n-cube des signes de chaque cellule avec des arêtes dirigées (= une itération de Foo) entre les sommets (= états), visiter le même sommet via n'importe quelle boucle d'arêtes aura pour résultat que l'IP sera dans la même position que celle avec laquelle il a commencé . Preuve: dans une boucle, l’IP se déplace dans chaque dimension un nombre pair de fois, c’est-à-dire que l’IP change de k × (a_j + (-a_j))% n 0 pour chaque dimension et revient donc toujours à la même position, ne jamais voir qu'un seul état sur n pour un sommet, c'est-à-dire un maximum de 2 ^ n états (= nombre de sommets du cube).
Kritixi Lithos
n2n.log(n)/n
3

05AB1E , 14 à 13 octets

goFć©(š®._}®_

Essayez-le en ligne!

Prend l’entrée sous forme de liste d’entiers avec 0 comme instruction d’arrêt. Retourne 1 pour arrêter et 0 pour ne pas arrêter.

Merci à @KevinCruijssen pour la sauvegarde de 2 octets!

Nick Kennedy
la source
Oh bien, alors c'est ce que votre réponse à la gelée fait! Grand usage de la rotation et ć! J'attendais une explication dans l'espoir de jouer ma réponse au golf, mais vous m'y êtes battu, haha. ; p -1 octet en faisant le même golf que ma réponse cependant: g·Fto «v( Essayez-le en ligne. )
Kevin Cruijssen Le
Et un -1 supplémentaire en utilisant à la ©®place de DŠs: «vć©(š®._}®_( Essayez-le en ligne. )
Kevin Cruijssen Le
Comme Arnauld l'a noté dans votre réponse à Python, boucler deux fois la longueur n'est pas suffisant. Donc, vous pouvez changer le «và goF.
Kevin Cruijssen
@KevinCruijssen merci
Nick Kennedy
3

Java 8, 78 79 73 octets

a->{int k=0,l=a.length,i=0;for(;i++<1<<l;k%=l)k-=(a[k]*=-1)%l-l;k/=a[k];}

Port direct de la réponse C # .NET de @EmbodimentOfIgnorance , assurez-vous donc de le réévaluer!
Merci à @Arnauld d' avoir trouvé deux bogues (ce qui s'applique également à d'autres réponses).

Il en résulte une java.lang.ArithmeticException: / by zeroerreur lorsqu'il est capable de s'arrêter ou aucune erreur si ce n'est pas le cas.

Essayez-le en ligne.

Explication:

a->{                   // Method with integer-array as parameter and no return-type
  int k=0,             //  Index integer, starting at 0
      l=a.length,      //  The length `l` of the input-array
  i=0;for(;i++<1<<l;   //  Loop 2^length amount of times:
          k%=l)        //    After every iteration: take mod `l` of `k`
    k-=                //   Decrease `k` by:
       (a[k]*=-1)      //    Negate the value at index `k` first
                 %l    //    Then take modulo `l` of this
                   -l; //    And then subtract `l` from it
                       //  (NOTE: the modulo `l` and minus `l` are used for wrapping
                       //  and/or converting negative indices to positive ones
  k/=a[k];}            //  After the loop: divide `k` by the `k`'th value,
                       //  which will result in an division by 0 error if are halting
Kevin Cruijssen
la source
2
Vous vous demandez simplement si vous êtes autorisé à prendre la longueur comme argument supplémentaire? La valeur par défaut pour IO post sur meta ne le dit pas, et la seule raison pour laquelle ma deuxième réponse prend une longueur est parce qu'elle prend un int*(de codegolf.meta.stackexchange.com/a/13262/84206 )
Incarnation de Ignorance
@EmbodimentofIgnorance Ah, quand j'ai vu votre réponse, j'ai supposé qu'il existait une sorte de méta-règle qui permettait de prendre la longueur en tant qu'entrée supplémentaire, mais cela ne s'applique qu'aux pointeurs. Merci de me le faire savoir. J'ai supprimé le paramètre de longueur (mais utilisez quand même l'erreur / pas d'erreur pour déterminer le résultat).
Kevin Cruijssen
3

Haskell , 79 octets

s x|m<-length x,let g(n:p)=(drop<>take)(mod n m)(-n:p)=iterate g x!!(2^m)!!0==0

Essayez-le en ligne!

Retours Truepour arrêter les machines et Falseautres. Saisie sous forme de liste, avec 0représentation d'un état d'arrêt.

Suppose une version de GHC supérieure à 8,4 (publiée en février 2018).

B. Mehta
la source
2

JavaScript (Node.js) , 71 à 67 octets

x=>{for(p=l=x.length,i=2**l;i--;)p+=l-(x[p%l]*=-1)%l;return!x[p%l]}

Fondamentalement identique à la réponse C # .NET de @EmbodimentOfIgnorance

Sauvegarde de 4 octets grâce à @Arnaud

Essayez-le en ligne!

JavaScript (Node.js) , 61 octets

x=>{for(p=l=x.length,i=2**l;i--;p+=l-(x[p%l]*=-1)%l)x[p%l].f}

Cette version utilise undefinedcomme symbole d’arrêt et jette a TypeError: Cannot read property 'f' of undefinedlorsque la machine s’arrête et se termine silencieusement lorsque la machine ne s’arrête pas.

Essayez-le en ligne!

IQuick 143
la source
1

Scala , 156 octets

OMI encore golfable, mais ça me va pour le moment. Retours 0pour non-arrêt Fooet s 1pour arrêt Foo. Prend l'entrée en atant que Array[Int], donc hest pris en tant que 0.

var u=Seq[Array[Int]]()//Keep track of all states
var i=0//Index
while(u.forall(_.deep!=a.deep)){if(a(i)==0)return 1//Check if we are in a previously encountered step ; Halt
u:+=a.clone//Add current state in the tracker
var k=i//Stock temp index
i=(a(i)+i)%a.length//Move index to next step
if(i<0)i+=a.length//Modulus operator in Scala can return a negative value...
a(k)*=(-1)}//Change sign of last seen index
0//Returns 0 if we met a previous step

Il est assez long à exécuter (environ 4 secondes pour tous les cas de test) en raison des multiples recherches sur un tableau complet que j'ai effectuées, ainsi .deepque de la création de copies ... Mais vous pouvez toujours l' essayer en ligne.

V. Courtois
la source
1

Attaché , 40 octets

Not@&N@Periodic[{On[0,`-,_]&Rotate!_@0}]

Essayez-le en ligne!

Explication

{On[0,`-,_]&Rotate!_@0}

Ceci effectue une seule itération de la machine Foo; il annule le premier membre, puis fait pivoter le tableau en fonction du premier élément (d'origine, non négatif) du tableau.

Periodicappliquera cette fonction jusqu'à ce qu'un résultat en double soit accumulé. Une machine s'arrête ou entre dans une boucle infinie triviale. S'il s'arrête, le premier élément sera 0. Sinon, il sera différent de zéro.

&Nest une manière amusante d’obtenir le premier élément d’un tableau numérique. Ensuite, Notretourne truepour 0 (machines à l'arrêt) et falsepour toute autre chose (machines à l'arrêt).

Conor O'Brien
la source
1

Charbon de bois , 28 octets

≔⁰ηFX²L諧≔θ籧θη≧⁻§θη绬§θη

Essayez-le en ligne! Le lien est vers la version verbeuse du code. Sorties utilisant la sortie booléenne par défaut de Charcoal, qui est -pour true et rien pour false. Explication:

≔⁰η

Initialise le pointeur d'instruction.

FX²Lθ«

Boucle autant de fois qu'il y a d'états théoriquement possibles.

§≔θ籧θη

Annulez la valeur au pointeur d'instruction.

≧⁻§θηη

Soustrayez la nouvelle valeur du pointeur d'instruction. Les accès à la matrice de charbon de bois sont cycliques et émulent automatiquement le ruban circulaire de Foo.

»¬§θη

À la fin de la boucle, indiquez si le programme s'est arrêté.

Neil
la source
0

Stax , 11 octets

Ç₧┬òE▐tµ|⌡1

Exécuter et déboguer

Il prend les entrées sous la forme d'un tableau entier, avec la 0représentation de stop.

Il sort 1pour une 0machine à l' arrêt et pour une machine qui ne s'arrête pas.

récursif
la source
0

Pyth , 12 octets

!hu.<+_hGtGh

Suite de tests!

Utilise l'approche directe. Recurse jusqu'à ce que nous voyions la liste deux fois dans un état identique. Pour les programmes qui s’arrêtent, la liste finira par prendre la tête 0car c’est là que s’arrête la récursivité. Pour les programmes qui ne s’arrêtent pas, la liste ne commence pas par le 0, mais se trouve dans un état dans lequel le processus serait périodique et, par conséquent, la machine Foo ne s’arrêterait pas.

M. Xcoder
la source