Ustalenie, czy maszyna Turinga zatrzymuje się, jest dobrze znane jako nierozstrzygalne, ale niekoniecznie dotyczy to prostszych maszyn.

Urządzenie Foo jest maszyną o skończonej taśmy, w którym każda komórka na taśmie ma całkowitą lub symbol, powstrzymanie h, np

2 h 1 -1

Wskaźnik instrukcji zaczyna się od wskazania pierwszej komórki:

2 h 1 -1
^

Na każdym kroku wskaźnik instrukcji przesuwa się do przodu o liczbę, na którą wskazuje, a następnie neguje tę liczbę. Tak więc, po jednym kroku, przesuwałby 2komórki do przodu i zmieniał 2w -2:

-2 h 1 -1
     ^

Maszyna Foo robi to dalej, dopóki wskaźnik instrukcji nie wskaże symbolu zatrzymania ( h). Oto pełna realizacja tego programu:

2 h 1 -1
^

-2 h 1 -1
     ^

-2 h -1 -1
         ^

-2 h -1 1
      ^

-2 h 1 1
   ^

Taśma jest również okrągła, więc jeśli wskaźnik instrukcji przesunie się z jednej strony taśmy, przejdzie na drugą stronę, np .:

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

Jedną interesującą rzeczą w tych maszynach Foo jest to, że niektóre się nie zatrzymują, np .:

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

Ten program będzie kontynuował zapętlanie w tych czterech ostatnich stanach na zawsze.

Napisz więc program, który określa, czy maszyna Foo zatrzymuje się, czy nie! Możesz użyć dowolnego (rozsądnego) formatu wejściowego, który ci się podoba dla maszyn Foo, i możesz użyć go 0jako symbolu zatrzymania. Możesz użyć dowolnych dwóch różnych danych wyjściowych dla przypadku, w którym się zatrzymuje, i przypadku, w którym się nie zatrzymuje. Twój program musi oczywiście udzielić odpowiedzi w skończonym czasie na wszystkie prawidłowe dane wejściowe.

To jest golf golfowy , więc postaraj się, aby twój program był jak najkrótszy!

Przypadki testowe

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

C # (interaktywny kompilator Visual C #) , 71 bajtów

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

Wypróbuj online!

Nie wiem, czy poniższe informacje są poprawne, ponieważ wymagają niestandardowego delegata z podpisem unsafe delegate System.Action<int> D(int* a); i muszą być owinięte w unsafeblok, aby można go było użyć, ale tutaj tak jest:

C # (.NET Core) , 64 bajty

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

Wypróbuj online!

Ta funkcja przyjmuje int * i zwraca akcję; innymi słowy, jest to funkcja curry. Jedynym powodem, dla którego używam wskaźników, jest kodegolf.meta.stackexchange.com/a/13262/84206, który pozwala mi zapisywać bajty, ponieważ posiadam już zmienną już zdefiniowaną o długości tablicy.

Zaoszczędzono 9 bajtów dzięki @someone

Python 3 , 63 89 bajtów

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

Wypróbuj online!

Działa również dla Python 2; bajt można zapisać w Pythonie 2 przez zamianę return na print i włączenie funkcji print na standardowe wyjście zamiast powrotu. R obraca się Truedla zatrzymania i Falsedla zatrzymania.

Dzięki @Neil i @Arnauld za zauważenie, że muszę dłużej sprawdzać, czy się zatrzymałem. Dzięki @Jitse za wskazanie problemu z [2,0]. Dzięki @mypetlion za zauważenie, że absolut wartości taśm może przekraczać długość taśmy.

Galaretka , 15 11 bajtów

N1¦ṙ⁸ḢƊÐLḢẸ

Wypróbuj online!

Łącze monadyczne, które przyjmuje dane wejściowe jako listę liczb całkowitych, w których wartość 0 oznacza zatrzymanie. Zwraca 0 dla wejść zatrzymanych i 1 dla tych, które się nie zatrzymują.

Zapobiega problemowi z obliczaniem liczby iteracji, ponieważ użycie ich ÐLbędzie przebiegać w pętli, dopóki nie pojawi się żaden nowy wynik.

Dzięki @JonathanAllan za uratowanie bajtu!

Wyjaśnienie

      ƊÐ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

Python 3 , 91 bajtów

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

Wypróbuj online!

-40 bajtów dzięki JoKing i Jitse

Perl 6 , 46 43 36 bajtów

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

Wypróbuj online!

Reprezentuje zatrzymanie przez 0i zwraca wartość true, jeśli maszyna się zatrzyma. Powtarza to 2**(length n)czasy logiki , w których jeśli wskaźnik znajdzie się na komórce zatrzymania, pozostanie tam, w przeciwnym razie będzie na komórce bez zatrzymania. Działa to, ponieważ istnieją tylko 2**nmożliwe stany (ignorowanie komórek zatrzymania) dla maszyny Foo, ponieważ każda komórka bez zatrzymania ma tylko dwa stany. Okej, są stany więcej niż to, ale z powodu ograniczonych możliwych przejść między wskaźnikami (i dlatego stanów) będzie mniej niż 2 ** stany $ _ ... myślę, że

Wyjaśnienie

{                                  }  # 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

05AB1E , 14 13 bajtów

goFć©(š®._}®_

Wypróbuj online!

Pobiera dane wejściowe jako listę liczb całkowitych z 0 jako instrukcją zatrzymania. Zwraca 1 za zatrzymanie i 0 za nie zatrzymanie.

Dzięki @KevinCruijssen za oszczędność 2 bajtów!

Java 8, 78 79 73 bajtów

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

Prosta port @EmbodimentOfIgnorance „s C # .NET odpowiedzi , więc upewnij się, aby go upvote!
Dzięki @Arnauld za znalezienie dwóch błędów (dotyczy to również niektórych innych odpowiedzi).

Powoduje java.lang.ArithmeticException: / by zerobłąd, gdy można go zatrzymać, lub brak błędu, jeśli nie.

Wypróbuj online.

Wyjaśnienie:

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

Haskell , 79 bajtów

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

Wypróbuj online!

Zwroty Trueza maszyny zatrzymujące i Falseinne. Dane wejściowe w postaci listy 0przedstawiającej stan zatrzymania.

Przyjmuje wersję GHC większą niż 8.4 (wydaną w lutym 2018 r.).

JavaScript (Node.js) , 71 67 bajtów

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

Zasadniczo taki sam, jak odpowiedź C # .NET w @EmbodimentOfIgnorance

4 bajty oszczędzaj dzięki @Arnaud

Wypróbuj online!

JavaScript (Node.js) , 61 bajtów

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

Ta wersja używa undefinedjako symbol zatrzymania i rzuca, TypeError: Cannot read property 'f' of undefinedgdy maszyna zatrzymuje się i kończy cicho, gdy maszyna się nie zatrzymuje.

Wypróbuj online!

Scala , 156 bajtów

Nadal jestem w grze w IMO, ale na razie nie mam nic przeciwko. Powroty 0dla non-wstrzymywania Foos oraz 1do wstrzymywania Foos. Przyjmuje dane wejściowe ajako Array[Int], więc hjest traktowane jako 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

Jego uruchomienie jest dość długie (około 4 sekund dla wszystkich przypadków testowych), ponieważ wykonałem wiele pełnych tablic, a także te, .deepktóre tworzą kopie ... Ale nadal możesz spróbować online.

Perl 5 -ap , 88 bajtów

for(;$F[$i]&&!$k{"$i|$F[$i]"};$i=($i+$F[$i])%@F){$k{"$i|$F[$i]"}=1;$F[$i]*=-1}$_=!$F[$i]

Wypróbuj online!

Attache , 40 bajtów

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

Wypróbuj online!

Wyjaśnienie

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

Wykonuje to pojedynczą iterację maszyny Foo; neguje pierwszy element, a następnie obraca tablicę o (oryginalny, niez negowany) pierwszy element tablicy.

Periodiczastosuje tę funkcję, aż do uzyskania podwójnego wyniku. Maszyna albo zatrzymuje się, albo przechodzi w trywialną nieskończoną pętlę. Jeśli się zatrzyma, pierwszy element będzie wynosił 0. W przeciwnym razie będzie niezerowy.

&Njest golfowym sposobem na uzyskanie pierwszego elementu tablicy numerycznej. Następnie Notzwraca true0 (maszyny zatrzymujące) i falsecokolwiek innego (maszyny nie zatrzymujące).

Węgiel drzewny , 28 bajtów

≔⁰ηＦＸ²Ｌ諧≔θ籧θη≧⁻§θη绬§θη

Wypróbuj online! Link jest do pełnej wersji kodu. Dane wyjściowe przy użyciu domyślnego wyniku logicznego Charcoala, który jest -prawdą, a nic nie fałszem. Wyjaśnienie:

≔⁰η

Zainicjuj wskaźnik instrukcji.

ＦＸ²Ｌθ«

Zapętlaj tyle razy, ile są teoretycznie możliwe stany.

§≔θ籧θη

Neguj wartość we wskaźniku instrukcji.

≧⁻§θηη

Odejmij nową wartość ze wskaźnika instrukcji. Dostęp do tablicy węglowej jest cykliczny, więc automatycznie emuluje okrągłą taśmę Foo.

»¬§θη

Na końcu pętli wypisz, czy program się zatrzymał.

Stax , 11 bajtów

Ç₧┬òE▐tµ|⌡1

Uruchom i debuguj

Pobiera dane wejściowe w postaci liczby całkowitej z 0reprezentacją zatrzymania.

Wyprowadza 1dla maszyny zatrzymującej i 0nie zatrzymującej maszyny.

Pyth , 12 bajtów

!hu.<+_hGtGh

Zestaw testowy!

Wykorzystuje proste podejście. Powtarzaj, dopóki nie zobaczymy listy dwa razy w identycznym stanie. W przypadku programów, które się zatrzymały, lista ostatecznie będzie miała wiodącą pozycję, 0ponieważ tam kończy się rekurencja. W przypadku programów, które się nie zatrzymują, lista nie zaczyna się od 0, ale raczej znajduje się w stanie, w którym proces byłby okresowy i dlatego maszyna Foo nie zatrzymywałaby się.