Celem tego wyzwania jest (ostatecznie) wygenerowanie każdego możliwego programu zatrzymania w wybranym języku. Na początku może się to wydawać niemożliwe, ale możesz to zrobić, bardzo ostrożnie wybierając kolejność wykonywania.
Poniżej znajduje się schemat ASCII ilustrujący to. Niech kolumny reprezentują numerację każdego możliwego programu (każdy program jest skończoną liczbą symboli ze skończonego alfabetu). Niech każdy wiersz reprezentuje pojedynczy krok w wykonaniu tego programu. X
Stanowią wykonanie wykonaniu tego programu w tym czasie kroku.
step# p1 p2 p3 p4 p5 p6
1 X X X X X X
2 X X X X X
3 X X X X
4 X X X X
5 X X X
6 X X
7 X X
8 X X
9 X X
∞ X X
Jak widać, programy 2 i 4 się nie zatrzymują. Jeśli miałbyś je wykonać pojedynczo, twój kontroler utknąłby w nieskończonej pętli, którą jest program 2 i nigdy nie wyprowadzałby programów 3 i późniejszych.
Zamiast tego stosujesz podejście typu „ jaskółczy ogon” . Litery przedstawiają możliwą kolejność wykonania dla pierwszych 26 kroków. Są *
to miejsca, w których program został zatrzymany i jest generowany. Są .
to kroki, które nie zostały jeszcze wykonane.
step# p1 p2 p3 p4 p5 p6
1 A C F J N R V
2 B E I M Q * Z
3 D H * P U
4 G L T Y
5 K O X
6 * S .
7 W .
8 . .
9 . .
∞ . .
Wymagania dotyczące języka docelowego
Język docelowy (ten interpretowany równolegle) musi być kompletny w Turingu. Poza tym może to być dowolny język, który jest kompletny z Turinga, w tym kompletne podzbiory Turinga dla znacznie większych języków. Możesz także dowolnie interpretować takie zasady, jak reguły systemu tagów cyklicznych. Możesz także utworzyć język do testowania, o ile możesz pokazać, dlaczego jest on kompletny w Turingu.
Na przykład, jeśli zdecydujesz się na test pieprzenia mózgu, najlepiej przetestować tylko []-+<>
podzbiór, ponieważ dane wejściowe nie są obsługiwane, a dane wyjściowe są po prostu wyrzucane (patrz poniżej).
Jeśli chodzi o program „kontrolera” (w który grasz), nie ma specjalnych wymagań. Obowiązują normalne ograniczenia językowe.
Jak stworzyć nieskończoną listę programów
Większość języków programowania może być reprezentowana jako seria symboli ze skończonego alfabetu. W takim przypadku stosunkowo łatwo jest wymienić listę każdego możliwego programu w kolejności rosnącej długości. Używany alfabet powinien być reprezentatywny dla wymagań języka docelowego. W większości przypadków jest to drukowany kod ASCII. Jeśli twój język obsługuje Unicode jako dodatkową funkcję, nie powinieneś testować każdej możliwej kombinacji znaków Unicode, tylko ASCII. Jeśli używasz tylko Twojego języka []-+<>
, nie testuj różnych kombinacji „komentujących” znaków ASCII. Języki takie jak APL miałyby własne specjalne alfabety.
Jeśli Twój język najlepiej jest opisać w jakiś sposób niealfabetyczny, np. Fractran lub Turing Machines, istnieją inne równie poprawne metody generowania listy wszystkich możliwych prawidłowych programów.
Interpretacja stale rosnącej listy programów
Kluczową częścią tego wyzwania jest napisanie równoległego interpretera dla rosnącej listy programów. Oto kilka podstawowych kroków:
- Dodaj skończoną liczbę programów do listy
- Interpretuj każdy program na liście indywidualnie przez określony czas. Można to osiągnąć, wykonując jeden krok instrukcji dla każdego. Zapisz wszystkie stany.
- Usuń wszystkie programy kończące / zgłaszające błędy z listy
- Wyjście czysto zatrzymanych * programów
- Dodaj więcej programów do listy
- Symuluj kolejno każdy program, pobierając wykonanie starszych programów tam, gdzie je przerwał
- Usuń wszystkie programy kończące / zgłaszające błędy z listy
- Wyjście czysto zatrzymanych * programów
- powtarzać
* Powinieneś wypisywać tylko programy, które zatrzymują się w sposób czysty. Oznacza to, że podczas wykonywania nie zgłoszono żadnych błędów składniowych ani nieprzechwyconych wyjątków. Programy, które proszą o wejście, również powinny zostać zakończone bez ich wysyłania. Jeśli program produkuje dane wyjściowe, nie powinieneś ich kończyć, po prostu wyrzuć dane wyjściowe.
Więcej zasad
- Nie wolno odradzać nowych wątków zawierających testowane programy, ponieważ odciąża to pracę równoległą do systemu operacyjnego hosta / innego oprogramowania.
- Edycja: Aby zamknąć potencjalne przyszłe luki, nie możesz
eval
(ani żadnej pokrewnej funkcji) części kodu testowanego programu. Państwo możeeval
bloku kodu z kodem tłumacza. (Odpowiedź BF-in-Python jest nadal ważna zgodnie z tymi zasadami). - To jest golf golfowy
- Język, w którym piszesz zgłoszenie , nie musi być taki sam, jak język, w którym testujesz / publikujesz.
- Należy założyć, że dostępna pamięć jest nieograniczona.
- Udowadniając kompletność Turinga, możesz założyć, że dane wejściowe są zakodowane na stałe w programie, a dane wyjściowe można odczytać ze stanu wewnętrznego programu.
- Jeśli twój program sam się wypisuje, prawdopodobnie jest to błąd lub poliglota.
źródło
"If your program outputs itself, it is probably wrong or a polyglot."
Odpowiedzi:
subleq OISC w Pythonie,
317269 bajtówhttps://esolangs.org/wiki/Subleq
Program podrzędny jest rozszerzalną listą liczb całkowitych (p) i wskaźnika instrukcji (i). Ten wariant subleq wykorzystuje adresowanie względne, które według strony dyskusji wiki jest wymagane do uzyskania kompletności z ograniczonymi wartościami. W każdym tiku operacja
p[i+p[i+1]]-=p[i+p[i]]
jest wykonywana, ai+=p[i+2]
jeśli wynik operacji był <= 0, w przeciwnym raziei+=3
. Jeśli i jest kiedykolwiek ujemne, program zatrzymuje się.Ta implementacja testuje każdy program, którego stan początkowy składa się z jednocyfrowych liczb całkowitych nieujemnych (0–9) ze wskaźnikiem instrukcji początkowej równym 0.
Wyjście jest odwrócone z powodów golfowych. Powyższa specyfikacja może być przekształcona w odwrotnej kolejności, ale wtedy nie będzie pasować do kodu użytego w implementacji, więc nie opisałem tego w ten sposób.
EDYCJA: Pierwszym programem, który wykazuje prosty nieograniczony wzrost, jest 14283, który zmniejsza wartość w miejscu pamięci 6 i zapisuje wyraźne 0 (w przeciwieństwie do niejawnego 0 w każdej komórce) do następnej ujemnej komórki, co trzy tiki.
źródło
Bitowy cykliczny znacznik w CJam,
98878477 bajtówPonieważ jest to nieskończona pętla, nie można tego bezpośrednio przetestować w tłumaczu online. Jednak tutaj jest alternatywna wersja, która odczytuje liczbę iteracji ze STDIN, z którymi możesz się bawić. Aby przetestować pełny program, potrzebujesz interpretera Java .
BCT to minimalistyczna odmiana cyklicznych systemów tagów . Program jest zdefiniowany przez dwa ciągi binarne: (cykliczną) listę instrukcji i stan początkowy. Aby ułatwić sobie życie podczas drukowania programów, zdefiniowałem własną notację: każdy ciąg jest podany jako tablica liczb całkowitych w stylu CJam, a cały program jest otoczony
[[...]]
, np.Nie zezwalam również na puste stany początkowe lub puste listy instrukcji.
Instrukcje w BCT są interpretowane w następujący sposób:
0
, usuń bit wiodący z bieżącego stanu.1
, przeczytaj kolejny bit z listy instrukcji, wywołaj toX
. Jeśli bitem wiodącym z bieżącego stanu jest1
, dołączX
do bieżącego stanu, w przeciwnym razie nic nie rób.Jeśli aktualny stan zostanie kiedykolwiek pusty, program się zatrzyma.
Pierwsze kilka programów zatrzymujących to
Jeśli chcesz zobaczyć więcej, sprawdź wersję w internetowym tłumaczu, który zamieściłem powyżej.
Wyjaśnienie
Oto jak działa kod. Aby śledzić dovetailing, zawsze będziemy mieć stos na tablicy zawierającej wszystkie programy. Każdy program jest parą wewnętrznej reprezentacji kodu programu (podobnego
[[0 1 0] [1 0]]
), a także bieżącego stanu programu. Tego drugiego użyjemy tylko do obliczeń, ale musimy pamiętać o tym pierwszym, aby wydrukować program, gdy się zatrzyma. Ta lista programów jest po prostu inicjowana do pustej tablicy przy pomocyL
.Reszta kodu to nieskończona pętla,
{...1}g
która najpierw dodaje jeden lub więcej programów do tej listy i oblicza jeden krok dla każdego programu. Zatrzymane programy są drukowane i usuwane z listy.Wyliczam programy, licząc liczbę binarną. Cyfra wiodąca jest usuwana, abyśmy mogli uzyskać wszystkie programy z wiodącymi zerami. Dla każdej takiej obciętej reprezentacji binarnej pcham jeden program dla każdego możliwego podziału między instrukcjami i stanem początkowym. Np. Jeśli licznik jest obecnie w
42
, jego reprezentacja binarna to101010
. Pozbywamy się wiodących1
i wypychamy wszystkie niepuste podziały:Ponieważ nie chcemy pustych instrukcji ani stanów, licznik rozpoczynamy od 4, co daje
[[[0] [0]]]
. To wyliczenie odbywa się za pomocą następującego kodu:Reszta kodu odwzorowuje blok na listę programów, która wykonuje jeden krok obliczeń BCT na drugiej połowie tych par i usuwa program, jeśli się zatrzyma:
źródło
Brainfuck in Python, 567 bajtów
Stosunkowo proste rozwiązanie, ponieważ Brainfuck nie jest najtrudniejszym językiem do napisania tłumacza.
Ta implementacja Brainfuck ma wskaźnik danych zaczynający się od 0, może przyjmować tylko wartość dodatnią (uważany za błąd, jeśli próbuje przejść na lewo od 0). Komórki danych mogą przyjmować wartości od 0 do 255 i zawijać. 5 prawidłowych instrukcji jest
><+[]
(-
jest niepotrzebnych ze względu na opakowanie).Myślę, że dane wyjściowe są teraz poprawne, jednak trudno jest mieć pewność, że wypisuje wszystkie możliwe rozwiązania, więc może mi brakować niektórych.
Pierwsze kilka wyjść:
I lista pierwszych 2000: http://pastebin.com/KQG8PVJn
I wreszcie lista pierwszych 2000 wyników z
[]
nimi: http://pastebin.com/iHWwJprs(cała reszta jest banalna, o ile są ważne)
Zauważ, że dane wyjściowe nie są posortowane, chociaż może się tak wydawać dla wielu z nich, ponieważ programy, które trwają dłużej, zostaną wydrukowane później.
źródło
[-]
i[+]
zdecydowanie powinny się pojawić, ponieważ zawartość pętli jest po prostu pomijana (bez zawijania).[-]
I[+]
był błędem, który powinien teraz zostać naprawiony, a ja zaktualizowałem ustawienia.
? Nie jest to konieczne dla kompletnego podzbioru BF Turinga, a dane wyjściowe i tak należy zignorować. Ponadto, ponieważ zawijasz wartości komórek, myślę, że potrzebujesz tylko jednego z-
i+
.ukośniki w Pythonie,
640498 bajtówhttps://esolangs.org/wiki////
Program ukośnik jest ciągiem znaków, w tym tłumaczu ograniczony do znaków „/” i „\”. W tej implementacji / to „1”, a \ to „0”, aby pozwolić na grę w golfa przy użyciu bin (x) pythona. Gdy interpreter napotka znak \, wyprowadzany jest następny znak i oba znaki są usuwane. Gdy napotka znak /, szuka wzorców wyszukiwania i zamienia je jako / search / replace / włączając w to znaki specjalne (\\ reprezentuje \ i \ / reprezentuje /). Ta operacja zamiany jest następnie wykonywana wielokrotnie na łańcuchu, aż łańcuch wyszukiwania nie będzie już obecny, a następnie interpretacja będzie kontynuowana od początku. Program zatrzymuje się, gdy jest pusty. Program zostanie zabity, jeśli istnieje niezamknięty zestaw / wzorców lub \ bez znaku po nim.
źródło
Treehugger w Javie,
12991257125112071203120111931189 bajtówźródło
Brachylog → Problem z korespondencją pocztową , 10 bajtów
Wypróbuj online!
Funkcja, która jest generatorem, który generuje wszystkie możliwe problemy z korespondencją pocztową, dla których rozwiązania wymuszania brutalnego w końcu przestają działać. (Brutalne wymuszanie rozwiązań problemu korespondencji Post jest znane jako operacja kompletna Turinga). Łącze TIO zawiera nagłówek, który konwertuje generator do pełnego programu i drukuje każde wyjście natychmiast po wygenerowaniu (a zatem, gdy TIO zabija program z uwagi na to, że zużywa ponad 60 sekund czasu wykonania, dotychczasowy wynik jest widoczny).
Wykorzystuje się w tym sformułowanie problemu, w którym ciągi są podawane jako ciągi cyfr, zera wiodące są niedozwolone, z wyjątkiem
0
samego siebie, rozwiązania problemu dotyczącego zer wiodących nie są akceptowane, a ciąg cyfr może być reprezentowany jako liczba lub minus liczba. Oczywiście nie ma to żadnego wpływu na kompletność języka Turinga (ponieważ nie ma potrzeby, aby problem z korespondencją w Post wykorzystywał cyfrę zero).Ten program działa poprzez generowanie wszystkich możliwych rozwiązań problemów, a następnie pracę wstecz, aby znaleźć oryginalne programy, które są przez nich rozwiązywane. Jako taki, pojedynczy program może być wyprowadzany wiele razy. Nie jest jasne, czy to unieważnia odpowiedź, czy nie; zwróć uwagę, że wszystkie programy zatrzymujące zostaną ostatecznie wydane co najmniej raz (w rzeczywistości nieskończenie wiele razy, ponieważ każdy program, który ma rozwiązania, ma nieskończenie wiele rozwiązań), a programy nie zatrzymujące nigdy nie zostaną wyświetlone.
Wyjaśnienie
źródło
„Fioletowy bez I / O” na Cejlonie, 662
Fioletowy jest samodmodyfikującym się językiem z jedną instrukcją, który został tutaj poproszony o tłumaczenie . Jako wejście i wyjście nie są istotne dla tego zadania, usunąłem
o
znaczenie symbolu od tłumacza, tak że (potencjalnie) symbole są ważne tylkoa
,b
,A
,B
,i
i1
(ten ostatni tylko do czytania, nie do pisania).Ale ponieważ Purple sam się modyfikuje (i używa swojego kodu źródłowego jako danych), potencjalnie przydatne mogą być również programy zawierające inne niż te znaki, dlatego zdecydowałem się zezwolić na wszystkie znaki ASCII do drukowania (inne niż białe znaki) w kodzie (inne mogą być przydatne, ale nie są tak łatwe do wydrukowania).
(Możesz zmodyfikować interpreter, aby zamiast tego przyjmował jako ciąg dozwolonych znaków jako argument wiersza poleceń - przełącz zdefiniowaną
a
poniżej linię z komentarzem . Wtedy długość wynosi 686 bajtów.)Mój „równoległy” interpreter tworzy zatem wszystkie skończone ciągi znaków z tych znaków (w coraz większej długości i porządku leksykograficznym) i próbuje każdego z nich.
Fioletowy zatrzyma się bezbłędnie za każdym razem, gdy polecenie do odczytania z taśmy do wykonania jest nieprawidłowe - dlatego nie ma niepoprawnych programów i wiele, wiele zatrzymujących. (Większość zatrzymuje się nawet na pierwszym etapie, tylko niektóre programy o długości 3 przechodzą do drugiego etapu (i zatrzymają się wtedy), pierwsze nie zatrzymujące się mają długość 6.
Myślę, że pierwszym nie zatrzymującym się programem w kolejności wypróbowanej przez mojego tłumacza jest
aaaiaa
, który w pierwszym kroku ustawiaa
rejestr na 0 (który już był), a drugi i każdy następny krok ustawia wskaźnik instrukcji z powrotem na 0, powodując jegoiaa
ponowne uruchomienie .Ponownie wykorzystałem część kodu napisanego dla mojego interpretera „standardowego” fioletu , ale z powodu usunięcia danych wejściowych i wyjściowych mój równoległy interpreter staje się nawet nieco krótszy, a jednocześnie zawiera dodatkową logikę do wykonywania wielu programów jednocześnie.
Oto skomentowana i sformatowana wersja:
źródło
Rachunek kombinatoryczny SK w Haskell , 249 bajtów
Wypróbuj online!
Jak to działa
Reguły oceny według wartości wywoławczej dla rachunku kombinatora SK są następujące:
(a) S xyz ↦ xz ( yz ), dla x , y , z w postaci normalnej;
(b) K xy ↦ x , dla x , y w postaci normalnej;
(c) xy ↦ x ′ y , jeśli x ↦ x ′;
(d) xy ↦ xy ′, dla x w normalnej formie, jeśli y ↦ y ′ .
Ponieważ jesteśmy zainteresowani jedynie zatrzymywaniem zachowania, nieznacznie rozszerzamy język, wprowadzając symbol H, który nie jest w normalnej formie, ale do którego „wszystkie” normalne formy „oceniają”:
(a) S xyz ↦ xz ( yz ), dla x , y , z w postaci normalnej;
(b ′) K x H ↦ x , dla x w postaci normalnej;
(c) xy ↦ x ′ y , jeśli x ↦ x ′;
(d) xy ↦ xy ′, dla xw normalnej formie, jeśli y ↦ y ′ ;
(e) S = H;
(f) K = H;
(g) SH ↦ H;
(h) KH ↦ H;
(i) SHH ↦ H.
Uważamy, że każda aplikacja H x jest błędem w czasie wykonywania traktowanym tak, jakby była nieskończoną pętlą, i zlecamy oceny w taki sposób, aby żadne H nie było wytwarzane przez (e) - (i), z wyjątkiem kontekstu, w którym będzie ignorowane (najwyższy poziom, dowolne K x ☐, dowolne zignorowane K any, dowolne zignorowane S x ☐ dla x w normalnej formie, dowolne zignorowane S☐H). W ten sposób nie wpływamy na zatrzymanie zachowania zwykłych terminów bez H.
Korzyści z tych zmodyfikowanych reguł są takie, że każdy znormalizowany termin ma unikalną ścieżkę oceny do H i że każdy termin ma skończoną liczbę możliwych obrazków pod under. Zamiast więc stosować podejście typu „jaskółczy ogon”, możemy przeprowadzić o wiele bardziej wydajne przeszukiwanie wszystkich ścieżek oceny odwrotnej od H.
n
sprawdza, czy termin jest w normalnej formie,f
znajduje wszystkie możliwe obrazy tego terminu il
jest leniwą, nieskończoną listą normalizowanych terminów utworzoną podczas pierwszego wyszukiwania od H.źródło