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 2
komórki do przodu i zmieniał 2
w -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 0
jako 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
źródło
1 2 h 42
(nie zatrzymuje się)3 2 1 1 4 h
. Ten zatrzymuje się, ale wymaga więcej iteracji niż dwukrotność liczby elementów.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
który zatrzymuje się po 786430 krokach.Odpowiedzi:
C # (interaktywny kompilator Visual C #) , 71 bajtów
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 wunsafe
blok, aby można go było użyć, ale tutaj tak jest:C # (.NET Core) , 64 bajty
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
źródło
1<<f
z2*f
zapisać bajt.Python 3 ,
6389 bajtówWypró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ę
True
dla zatrzymania iFalse
dla 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.źródło
x+x
wystarczy?[ 3, 2, 1, 1, 4, 0 ]
zatrzymywanie się w ponad 12 iteracjach.len(x)*x
[8,7,6,5,7,4,0,3,6]
2**len(x)
nadal nie jest trochę za mało? Liczę stanów obliczam jakon*(2**n)
(zn=len(x)-1
).Galaretka ,
1511 bajtówWypró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
ÐL
będzie przebiegać w pętli, dopóki nie pojawi się żaden nowy wynik.Dzięki @JonathanAllan za uratowanie bajtu!
Wyjaśnienie
źródło
N1¦ṙ⁸ḢƊÐLḢẸ
Python 3 , 91 bajtów
Wypróbuj online!
-40 bajtów dzięki JoKing i Jitse
źródło
while
warunku.Perl 6 ,
46 4336 bajtówWypróbuj online!
Reprezentuje zatrzymanie przez
0
i zwraca wartość true, jeśli maszyna się zatrzyma. Powtarza to2**(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ą tylkoOkej, 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ę, że2**n
możliwe stany (ignorowanie komórek zatrzymania) dla maszyny Foo, ponieważ każda komórka bez zatrzymania ma tylko dwa stany.Wyjaśnienie
źródło
05AB1E ,
1413 bajtówWypró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!
źródło
ć
! 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·F
do«v
( Wypróbuj online. )©®
zamiastDŠs
:«vć©(š®._}®_
( Wypróbuj online. )«v
sięgoF
.Java 8,
787973 bajtówProsta 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 zero
błąd, gdy można go zatrzymać, lub brak błędu, jeśli nie.Wypróbuj online.
Wyjaśnienie:
źródło
int*
(z codegolf.meta.stackexchange.com/a/13262/84206 )Haskell , 79 bajtów
Wypróbuj online!
Zwroty
True
za maszyny zatrzymujące iFalse
inne. Dane wejściowe w postaci listy0
przedstawiającej stan zatrzymania.Przyjmuje wersję GHC większą niż 8.4 (wydaną w lutym 2018 r.).
źródło
JavaScript (Node.js) ,
7167 bajtówZasadniczo taki sam, jak odpowiedź C # .NET w @EmbodimentOfIgnorance
4 bajty oszczędzaj dzięki @Arnaud
Wypróbuj online!
JavaScript (Node.js) , 61 bajtów
Ta wersja używa
undefined
jako symbol zatrzymania i rzuca,TypeError: Cannot read property 'f' of undefined
gdy maszyna zatrzymuje się i kończy cicho, gdy maszyna się nie zatrzymuje.Wypróbuj online!
źródło
Scala , 156 bajtów
Nadal jestem w grze w IMO, ale na razie nie mam nic przeciwko. Powroty
0
dla non-wstrzymywaniaFoo
s oraz1
do wstrzymywaniaFoo
s. Przyjmuje dane wejściowea
jakoArray[Int]
, więch
jest traktowane jako0
.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,
.deep
które tworzą kopie ... Ale nadal możesz spróbować online.źródło
Perl 5
-ap
, 88 bajtówWypróbuj online!
źródło
Attache , 40 bajtów
Wypróbuj online!
Wyjaśnienie
Wykonuje to pojedynczą iterację maszyny Foo; neguje pierwszy element, a następnie obraca tablicę o (oryginalny, niez negowany) pierwszy element tablicy.
Periodic
zastosuje 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.&N
jest golfowym sposobem na uzyskanie pierwszego elementu tablicy numerycznej. NastępnieNot
zwracatrue
0 (maszyny zatrzymujące) ifalse
cokolwiek innego (maszyny nie zatrzymujące).źródło
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ł.
źródło
Stax , 11 bajtów
Uruchom i debuguj
Pobiera dane wejściowe w postaci liczby całkowitej z
0
reprezentacją zatrzymania.Wyprowadza
1
dla maszyny zatrzymującej i0
nie zatrzymującej maszyny.źródło
Pyth , 12 bajtów
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ę,
0
ponieważ tam kończy się rekurencja. W przypadku programów, które się nie zatrzymują, lista nie zaczyna się od0
, ale raczej znajduje się w stanie, w którym proces byłby okresowy i dlatego maszyna Foo nie zatrzymywałaby się.źródło