Czy ta maszyna Foo zatrzymuje się?

43

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 , 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
Leo Tenenbaum
źródło
5
Jestem pewien, że algorytm rozwiązuje ten problem. Nie jestem mistrzem algorytmu, więc wolę pytać przed pójściem w złym kierunku. Czy nie zatrzymująca się maszyna Foo zawsze powróci do swojego pierwotnego stanu? A może istnieją nie zatrzymujące się „chaotyczne” maszyny?
V. Courtois,
5
@ V.Courtois Wszystkie nie zatrzymujące się maszyny Foo kończą się w pętli stanów, ponieważ istnieje tylko skończenie wiele możliwych stanów, w których może znajdować się maszyna Foo (jest n możliwych miejsc, w których może znajdować się wskaźnik instrukcji, i 2 ^ n możliwe konfiguracje taśm). Każdy stan ma jeden i tylko jeden „następny stan”. Tak więc, jeśli maszyna Foo powróci do stanu, w którym już była, po prostu będzie się zapętlać. Ponieważ jest tylko wiele stanów, nie może ciągle chaotycznie przeskakiwać między stanami, ponieważ ostatecznie skończy się na jednym, w którym już był.
Leo Tenenbaum,
3
Sugerowany przypadek testowy: 1 2 h 42(nie zatrzymuje się)
Arnauld
6
Sugerowana przypadek testowy: 3 2 1 1 4 h. Ten zatrzymuje się, ale wymaga więcej iteracji niż dwukrotność liczby elementów.
Arnauld
10
Sugerowany wyjątkowo długi przypadek testowy: 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 -36który zatrzymuje się po 786430 krokach.
Magma,

Odpowiedzi:

11

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

Wcielenie ignorancji
źródło
Kod w golfa o 2 bajty: tio.run/…
143
@ IQuick143 Niezły chwyt, dzięki
of Ignorance
Nie jestem pewien, czy istnieją przypadki brzegowe, dla których to nie będzie działać, ale bez złamania któregokolwiek z dotychczasowych przypadków testowych można zastąpić 1<<fz 2*fzapisać bajt.
Kevin Cruijssen
1
77 bajtów z okropną magią LINQ i poprawką Arnaulda . Nie mam pojęcia, jak działa to rozwiązanie, więc mogłem je zepsuć.
ktoś
1
63 bajty za pomocą normalnego 1-bajtowego golfa i zmiana IO na error / no error. Link do linku
ktoś
7

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.

Nick Kennedy
źródło
5
OK, ugryzę: skąd wiesz, że x+xwystarczy?
Neil
4
@Neil W rzeczywistości to za mało. Przeciwnym przykładem jest [ 3, 2, 1, 1, 4, 0 ]zatrzymywanie się w ponad 12 iteracjach.
Arnauld
1
len(x)*x[8,7,6,5,7,4,0,3,6]92
2
Czy 2**len(x)nadal nie jest trochę za mało? Liczę stanów obliczam jako n*(2**n)(z n=len(x)-1).
OOBalance,
1
@OOBalance Rozumiem, co masz na myśli, ponieważ każdy stan może mieć wskaźnik w każdej komórce ... czuję jednak, że istnieje jakiś inny limit nałożony przez fakt, że każda komórka może tylko przejść do dwóch innych komórek. Na marginesie: nic w wyzwaniu nie mówi, że wejście musi być w stanie zatrzymania
Jo King
6

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
Nick Kennedy
źródło
Zapisz bajt, obracając wszystkie wpisy, a następnie zachowując pierwszy wynik:N1¦ṙ⁸ḢƊÐLḢẸ
Jonathan Allan
5

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

HyperNeutrino
źródło
@JoKing 109 bajtów , wykonując przypisania zmiennych w pierwszym wierszu.
Jitse,
92 bajty , zmieniając konwersję krotki na rozszerzenie oznaczone gwiazdką, nie rozpoczynając od pustego zestawu i nie zmieniając whilewarunku.
Jitse
@JoKing Cholera, nigdy się nie uczę: str. 93 bajty .
Jitse
91 bajtów
Jitse
@JoKing dzięki!
HyperNeutrino
5

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
Jo King
źródło
2
Stan maszyny Foo obejmuje również lokalizację wskaźnika, a nie tylko znaki każdej komórki.
Magma,
1
Szkic dowodu na maszynę Foo z taśmą a_1 ... a_n 0. Rozważ n-sześcian znaków każdej komórki z ukierunkowanymi krawędziami (= iteracja Foo) między wierzchołkami (= stany), odwiedzając ten sam wierzchołek przez dowolną pętlę krawędzi spowoduje, że adres IP będzie w tej samej pozycji, od której zaczął . Dowód: w pętli IP przesuwa się w każdym wymiarze parzystą liczbę razy, tj. IP zmienia się o k × (a_j + (-a_j))% n ≡ 0 dla każdego wymiaru, dlatego zawsze powraca do tej samej pozycji, tylko zawsze widział 1 stan spośród n stanów dla każdego wierzchołka, tj. łącznie maksimum 2 ^ n stanów (= liczba wierzchołków sześcianu).
Kritixi Lithos
n2n.log(n)/n
3

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!

Nick Kennedy
źródło
Och, fajnie, więc to właśnie robi twoja odpowiedź na galaretkę! Świetne wykorzystanie obracania i ć! Czekałem na wyjaśnienie w nadziei, że zagram w moją odpowiedź, ale pobiłaś mnie, haha. ; p -1 bajt, wykonując ten sam golf, co moja odpowiedź: g·Fdo «v( Wypróbuj online. )
Kevin Cruijssen
I jeden dodatkowy -1, używając ©®zamiast DŠs: «vć©(š®._}®_( Wypróbuj online. )
Kevin Cruijssen
Jak zauważył Arnauld w odpowiedzi na Pythona, zapętlenie dwa razy długość nie wystarcza. Więc można zmienić «vsię goF.
Kevin Cruijssen
@KevinCruijssen dzięki
Nick Kennedy
3

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
Kevin Cruijssen
źródło
2
Zastanawiam się, czy możesz wziąć tę długość za dodatkowy argument? Domyślne ustawienie postu we / wy w meta tego nie mówi, a jedynym powodem, dla którego moja druga odpowiedź jest długa, jest to, że przyjmuje int*(z codegolf.meta.stackexchange.com/a/13262/84206 )
of Ignorance
@EmbodimentofIgnorance Ah, kiedy zobaczyłem twoją odpowiedź, założyłem, że istnieje pewna meta reguła, która pozwalała brać długość jako dodatkowe dane wejściowe, ale dotyczy to tylko wskaźników. Dzięki, że dałeś mi znać. Usunąłem parametr długości (ale nadal używam błędu / braku błędu do ustalenia wyniku).
Kevin Cruijssen
3

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.).

B. Mehta
źródło
2

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!

IQuick 143
źródło
1

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.

V. Courtois
źródło
1

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).

Conor O'Brien
źródło
1

Węgiel drzewny , 28 bajtów

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

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.

FX²Lθ«

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ł.

Neil
źródło
0

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.

rekurencyjny
źródło
0

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ę.

Pan Xcoder
źródło