Hält diese Foo-Maschine an?

43

Es ist allgemein bekannt, dass die Entscheidung, ob eine Turing-Maschine anhält, unentscheidbar ist. Dies gilt jedoch nicht unbedingt für einfachere Maschinen.

Eine Foo-Maschine ist eine Maschine mit einem endlichen Band, bei der jede Zelle auf dem Band eine Ganzzahl oder ein Haltesymbol aufweist h, z

2 h 1 -1

Der Anweisungszeiger zeigt zunächst auf die erste Zelle:

2 h 1 -1
^

Bei jedem Schritt bewegt sich der Befehlszeiger um die Nummer vorwärts, auf die er zeigt, und negiert dann diese Nummer. So würde es nach einem Schritt vorwärts 2Zellen bewegen und das 2in ein verwandeln -2:

-2 h 1 -1
     ^

Die Foo-Maschine tut dies so lange, bis der Anweisungszeiger auf das Stoppsymbol ( h) zeigt. Hier ist die vollständige Ausführung dieses Programms:

2 h 1 -1
^

-2 h 1 -1
     ^

-2 h -1 -1
         ^

-2 h -1 1
      ^

-2 h 1 1
   ^

Das Band ist ebenfalls kreisförmig. Bewegt sich der Befehlszeiger von einer Seite des Bandes weg, bewegt er sich zur anderen Seite, z.

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

Eine interessante Sache an diesen Foo-Maschinen ist, dass einige nicht anhalten, zB:

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

Dieses Programm wird in den letzten vier Zuständen für immer weitergeschleift.

Schreiben Sie also ein Programm, das feststellt, ob eine Foo-Maschine anhält oder nicht! Sie können für die Foo-Maschinen jedes (angemessene) Eingabeformat verwenden, das Sie möchten, und Sie können wählen, ob Sie das Stoppsymbol verwenden 0möchten. Sie können zwei unterschiedliche Ausgaben für den Fall verwenden, dass es anhält und für den Fall, dass es nicht anhält. Ihr Programm muss natürlich für alle gültigen Eingaben eine Antwort in endlicher Zeit ausgeben.

Das ist , also versuchen Sie, Ihr Programm so kurz wie möglich zu halten!

Testfälle

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
quelle
5
Nur damit ich sicher bin, über den Algorithmus, um dies zu beheben. Ich bin kein Algorithmus-Meister, also frage ich lieber, bevor ich in die falsche Richtung gehe. Wird eine nicht stoppende Foo-Maschine immer in ihren exakten Originalzustand zurückkehren? Oder gibt es "chaotisch verhaltene" Maschinen, die nicht anhalten?
V. Courtois
5
@ V.Courtois Alle nicht stoppenden Foo-Maschinen werden in einer Schleife von Zuständen enden, da es nur endlich viele mögliche Zustände gibt, in denen sich eine Foo-Maschine befinden kann (es gibt n mögliche Stellen, an denen der Befehlszeiger sein kann, und 2 ^ n mögliche Bandkonfigurationen). Jeder Zustand hat einen und nur einen "nächsten Zustand". Wenn also eine Foo-Maschine wieder in einem Zustand ist, in dem sie bereits war, wird sie einfach weitergeschleift. Da es nur endlich viele Bundesstaaten gibt, kann es nicht immer chaotisch zwischen den Bundesstaaten hin und her springen, da es irgendwann zu einem Bundesstaat führen wird, in dem es bereits war.
Leo Tenenbaum
3
Vorgeschlagener Testfall: 1 2 h 42(hält nicht an)
Arnauld
6
Empfohlene Testfall: 3 2 1 1 4 h. Dieser hält an, erfordert jedoch mehr Iterationen als die doppelte Anzahl von Elementen.
Arnauld
10
Vorgeschlagener überlanger Testfall 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:, der nach 786430 Schritten anhält.
Magma

Antworten:

11

C # (Visual C # Interactive Compiler) , 71 Byte

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

Probieren Sie es online!

Ich weiß nicht, ob das Folgende gültig ist, da es einen benutzerdefinierten Delegaten mit der Signatur von erfordert unsafe delegate System.Action<int> D(int* a); und in einen unsafeBlock eingeschlossen werden muss, um verwendet zu werden, aber hier ist es trotzdem:

C # (.NET Core) , 64 Byte

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

Probieren Sie es online!

Diese Funktion nimmt ein int * auf und gibt eine Aktion zurück. Mit anderen Worten, es ist eine Curry-Funktion. Der einzige Grund, warum ich Zeiger verwende, ist codegolf.meta.stackexchange.com/a/13262/84206, mit dem ich Bytes speichern kann, wenn bereits eine Variable mit der Länge des Arrays definiert ist.

9 Bytes dank @someone gespeichert

Verkörperung der Ignoranz
quelle
Golf Ihren Code um 2 Bytes: tio.run/…
IQuick 143
@ IQuick143 Schöner Fang, danke
Verkörperung der Ignoranz
Ich bin sicher nicht , wenn es irgendwelche Randfälle , für die es nicht funktionieren wird, aber ohne Sie könnte ersetzen einem der aktuellen Testfälle zu brechen 1<<fmit 2*feinem Byte zu speichern.
Kevin Cruijssen
1
77 Bytes mit schrecklicher LINQ-Magie und Arnauld's Fix . Ich habe keine Ahnung, wie diese Lösung funktioniert, daher habe ich sie möglicherweise beschädigt.
Jemand
1
63 Bytes über ein normales, normales 1-Byte-Golf und Ändern von E / A in Fehler / kein Fehler. Link zu Link
jemand
7

Python 3 , 63 89 Bytes

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

Probieren Sie es online!

Funktioniert auch für Python 2; Ein Byte kann in Python 2 gespeichert werden, indem return durch print ersetzt und die Funktion statt return auf stdout gedruckt wird. R dreht sich Truezum Anhalten und Falsezum Nichtanhalten.

Vielen Dank an @Neil und @Arnauld für die Feststellung, dass ich länger nach dem Anhalten suchen musste. Vielen Dank an @Jitse für den Hinweis auf ein Problem mit [2,0]. Vielen Dank an @mypetlion für die Feststellung, dass der absolute Wert des Bandes die Bandlänge überschreiten kann.

Nick Kennedy
quelle
5
OK, ich werde beißen: Woher weißt du, x+xist genug?
Neil
4
@Neil Es ist eigentlich nicht genug. Ein Gegenbeispiel ist [ 3, 2, 1, 1, 4, 0 ], das in mehr als 12 Iterationen anhält.
Arnauld
1
len(x)*x[8,7,6,5,7,4,0,3,6]92
2
Ist es nicht 2**len(x)immer noch ein bisschen zu kurz für das Maximum? Ich berechne die Anzahl der Zustände als n*(2**n)(mit n=len(x)-1).
OOBalance
1
@OOBalance Ich verstehe, was Sie meinen, da jeder Zustand in jeder Zelle einen Zeiger haben kann ... Ich glaube jedoch, dass es eine andere Grenze gibt, die durch die Tatsache bedingt ist, dass jede Zelle möglicherweise nur zu zwei anderen Zellen übergehen kann. Als Randbemerkung: nichts in der Herausforderung , sagt , es hat einen Haltezustand , in dem Eingang zu sein
Jo König
6

Jelly , 15 11 Bytes

N1¦ṙ⁸ḢƊÐLḢẸ

Probieren Sie es online!

Ein monadischer Link, der die Eingabe als Liste von Ganzzahlen aufnimmt, wobei 0 für Halt steht. Gibt 0 für das Anhalten von Eingaben und 1 für diejenigen zurück, die nicht angehalten werden.

Vermeidet das Problem, dass die Anzahl der Iterationen ermittelt werden muss, da bei deren Verwendung ÐLeine Schleife ausgeführt wird, bis kein neues Ergebnis mehr zu sehen ist.

Vielen Dank an @ JonathanAllan für das Speichern eines Bytes!

Erläuterung

      ƊÐ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
quelle
Speichern Sie ein Byte, indem Sie alle Einträge rotieren und dann das erste Ergebnis N1¦ṙ⁸ḢƊÐLḢẸ
Jonathan Allan
5

Python 3 , 91 Bytes

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

Probieren Sie es online!

-40 Bytes dank JoKing und Jitse

HyperNeutrino
quelle
@JoKing 109 Bytes durch Ausführen der Variablenzuweisungen in der ersten Zeile.
Jitse
92 Bytes durch Ändern der Tupelkonvertierung in eine markierte Erweiterung, wobei nicht mit einer leeren Menge begonnen und die whileBedingung umformuliert wird.
Jitse
@JoKing Verdammt, ich lerne nie: p. 93 Bytes dann.
Jitse
91 Bytes
Jitse
@JoKing danke!
HyperNeutrino
5

Perl 6 , 46 43 36 Bytes

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

Probieren Sie es online!

Stellt halt by dar 0und gibt true zurück, wenn der Computer anhält. Dies wiederholt die logischen 2**(length n)Zeiten, in denen der Zeiger, wenn er auf der Haltezelle endet, dort bleibt, sonst befindet er sich auf einer nicht-Haltezelle. Dies funktioniert, weil es nur 2**nmögliche Zustände (ohne Berücksichtigung der angehaltenen Zellen) für die Foo-Maschine gibt, da jede nicht angehaltene Zelle nur zwei Zustände hat. Okay ja, es gibt Zustände als das, aber aufgrund der begrenzten möglichen Übergänge zwischen Zeigern (und daher Zuständen) wird es weniger als 2 ** $ _ Zustände geben ... Ich denke

Erläuterung

{                                  }  # 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
Scherzen
quelle
2
Der Status der Foo-Maschine enthält auch die Position des Zeigers und nicht nur die Vorzeichen jeder Zelle.
Magma
1
Skizze eines Proofs für eine Foo-Maschine mit Band a_1 ... a_n 0. Betrachten Sie einen n-Würfel der Vorzeichen jeder Zelle mit gerichteten Kanten (= eine Iteration von Foo) zwischen Scheitelpunkten (= Zuständen). Wenn Sie denselben Scheitelpunkt über eine beliebige Schleife von Kanten besuchen, befindet sich die IP an derselben Position, mit der sie begonnen hat . Beweis: In einer Schleife bewegt sich die IP in jeder Dimension eine gerade Anzahl von Malen, dh die IP ändert sich für jede Dimension um k × (a_j + (-a_j))% n ≡ 0, daher kehrt sie immer an dieselbe Position zurück. Es wird immer nur 1 Zustand von n Zuständen für jeden Scheitelpunkt angezeigt, dh insgesamt maximal 2 ^ n Zustände (= Anzahl der Scheitelpunkte eines Würfels).
Kritixi Lithos
n2n.log(n)/n
3

05AB1E , 14 13 Bytes

goFć©(š®._}®_

Probieren Sie es online!

Übernimmt die Eingabe als eine Liste von Ganzzahlen mit 0 als Halteanweisung. Gibt 1 zum Anhalten und 0 zum Nichtanhalten zurück.

Vielen Dank an @KevinCruijssen für das Speichern von 2 Bytes!

Nick Kennedy
quelle
Oh, schön, das ist es, was deine Gelee-Antwort tut! Großartige Nutzung der drehen und ć! Ich habe auf eine Erklärung gewartet, in der Hoffnung, meine Antwort zu finden, aber Sie haben mich geschlagen, haha. ; p -1 Byte für den gleichen Golf wie meine Antwort tut aber: g·Fzu «v( Versuchen Sie es online. )
Kevin Cruijssen
Und eine zusätzliche -1 mit ©®anstelle von DŠs: «vć©(š®._}®_( Versuchen Sie es online. )
Kevin Cruijssen
Wie Arnauld in Ihrer Python-Antwort vermerkt hat, reicht es nicht aus, zwei Mal die Länge einer Schleife zu verwenden. So können Sie die Änderung «vzu goF.
Kevin Cruijssen
@ KevinCruijssen Dank
Nick Kennedy
3

Java 8, 78 79 73 Bytes

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

Einfacher Port der C # .NET-Antwort von @EmbodimentOfIgnorance. Stellen Sie also sicher, dass Sie ihn unterstützen!
Vielen Dank an @Arnauld für das Auffinden von zwei Fehlern (was auch für einige andere Antworten gilt).

Führt zu einem java.lang.ArithmeticException: / by zeroFehler, wenn er angehalten werden kann, oder zu keinem Fehler, wenn nicht.

Probieren Sie es online aus.

Erläuterung:

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
quelle
2
Ich frage mich nur, dürfen Sie die Länge als zusätzliches Argument nehmen? Die Standardeinstellung für E / A- Posts auf Meta sagt dies nicht aus, und der einzige Grund, warum meine zweite Antwort länger dauert, ist, dass sie eine int*(von codegolf.meta.stackexchange.com/a/13262/84206 )
Verkörperung von Ignoranz
@EmbodimentofIgnorance Ah, als ich Ihre Antwort sah, ging ich davon aus, dass es eine Art Metaregel gibt, die es erlaubt, die Länge als zusätzliche Eingabe zu verwenden, aber das gilt nur für Zeiger. Danke für die Information. Ich habe den Längenparameter entfernt (benutze aber immer noch den error / no-error, um das Ergebnis zu bestimmen).
Kevin Cruijssen
3

Haskell , 79 Bytes

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

Probieren Sie es online!

Rückgabe Truefür das Anhalten von Maschinen und Falseansonsten. Eingabe in Form einer Liste mit 0Darstellung eines Haltezustands.

Nimmt eine Version von GHC größer als 8.4 an (veröffentlicht im Februar 2018).

B. Mehta
quelle
2

JavaScript (Node.js) , 71 67 Byte

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

Grundsätzlich identisch mit der C # .NET-Antwort von @EmbodimentOfIgnorance

4 Byte sparen dank @Arnaud

Probieren Sie es online!

JavaScript (Node.js) , 61 Byte

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

Diese Version wird undefinedals Haltesymbol verwendet und wirft ein, TypeError: Cannot read property 'f' of undefinedwenn die Maschine anhält, und wird leise beendet, wenn die Maschine nicht anhält.

Probieren Sie es online!

IQuick 143
quelle
1

Scala , 156 Bytes

IMO immer noch golffähig, aber im Moment bin ich damit einverstanden. Gibt 0für nicht haltende Foos und 1für haltende Foos zurück. Nimmt die Eingabe aals ein Array[Int], so hwird als genommen 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

Die Laufzeit ist ziemlich lang (etwa 4 Sekunden für alle Testfälle), da ich mehrere vollständige Array-Suchvorgänge durchgeführt habe und .deepKopien erstellt habe. Sie können sie jedoch weiterhin online testen .

V. Courtois
quelle
1

Attache , 40 Bytes

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

Probieren Sie es online!

Erläuterung

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

Dies führt eine einzelne Iteration der Foo-Maschine durch. Es negiert das erste Element und dreht dann das Array um das (ursprüngliche, nicht negierte) erste Element des Arrays.

PeriodicWendet diese Funktion an, bis sich ein doppeltes Ergebnis angesammelt hat. Eine Maschine hält an oder geht in eine triviale Endlosschleife. Wenn es anhält, ist das erste Element 0. Andernfalls ist es ungleich Null.

&Nist eine einfache Methode, um das erste Element eines numerischen Arrays zu erhalten. Dann Notkehrt truefür 0 (Anhalten Maschinen) und falsefür alles andere (nicht stockend Maschinen).

Conor O'Brien
quelle
1

Kohle , 28 Bytes

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

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Die Ausgabe erfolgt mit der booleschen Standardausgabe von Charcoal, die -für true und nichts für false steht. Erläuterung:

≔⁰η

Initialisieren Sie den Anweisungszeiger.

FX²Lθ«

Schleife so oft es theoretisch mögliche Zustände gibt.

§≔θ籧θη

Negieren Sie den Wert am Befehlszeiger.

≧⁻§θηη

Subtrahieren Sie den neuen Wert vom Anweisungszeiger. Die Array-Zugriffe von Charcoal sind zyklisch, sodass das kreisförmige Band von Foo automatisch emuliert wird.

»¬§θη

Geben Sie am Ende der Schleife aus, ob das Programm angehalten wurde.

Neil
quelle
0

Stax , 11 Bytes

Ç₧┬òE▐tµ|⌡1

Führen Sie es aus und debuggen Sie es

Die Eingabe erfolgt in Form eines Integer-Arrays, wobei 0halt dargestellt wird.

Es gibt 1für eine stoppende und 0für eine nicht stoppende Maschine aus.

rekursiv
quelle
0

Pyth , 12 Bytes

!hu.<+_hGtGh

Testsuite!

Verwendet den direkten Ansatz. Wiederholen Sie den Vorgang, bis die Liste zweimal in identischem Zustand angezeigt wird. Bei Programmen, die angehalten werden, wird die Liste irgendwann einen Vorsprung haben, 0da an dieser Stelle die Rekursion endet. Bei Programmen, die nicht angehalten werden, beginnt die Liste nicht mit dem 0, sondern befindet sich in einem Zustand, in dem der Prozess regelmäßig abläuft und die Foo-Maschine daher nicht angehalten wird.

Mr. Xcoder
quelle