Wyzwaniem, które moim zdaniem byłoby bardzo fajne, było stworzenie tłumacza dla wybranego przez ciebie kompletnego języka Turinga .
Zasady są proste:
- Możesz użyć dowolnego języka do stworzenia tego tłumacza, nawet jeśli jest on nowszy niż to wyzwanie.
- Możesz używać dowolnego języka pełnego Turinga, o ile nie jest on tym samym językiem, w którym go piszesz.
- Nie można po prostu oceniać kodu, na przykład używać funkcji eval.
- Wyjaśnienie, jak do tego podszedłeś, będzie miłe, ale nie wymagane.
- To będzie punktowane w bajtach.
- Każde przesłanie musi być w pełni sprawne, co oznacza, że każda funkcja wybranego języka musi być obecna.
Mówiąc krótko:
Twoim zadaniem jest stworzenie działającego tłumacza dla dowolnego języka pełnego Turinga z dowolnym wybranym językiem.
Powodzenia!
code-golf
interpreter
arodebaugh
źródło
źródło
eval
rozwiązaniom.eval
polecenia / funkcje, ponieważ niektóre języki mają wbudowane funkcje do oceny kodu w innym języku.Odpowiedzi:
Brachylog (2) → Problem z korespondencją pocztową , 9 bajtów
Wypróbuj online!
Dane wejściowe to lista list ciągów znaków. (W problemie z korespondencją Post zdefiniowanym na Wikipedii, wewnętrzne listy mają po dwa elementy, chociaż ten program może faktycznie uogólniać dowolną liczbę elementów.) Ten program brutalnie wymusza rozwiązania problemu, według długości, aż do rozwiązanie zostało znalezione. Wiadomo, że problem z korespondencją pocztową jest w stanie symulować maszynę Turinga, a zatem brutalne rozwiązania tego problemu są kompletne. Jeśli jest uruchamiany jako funkcja, a nie program, w rzeczywistości generuje również znaczący wynik.
Program w powyższym linku TIO to
[["a","baa"],["ab","aa"],["bba","bb"]]
, który skopiowałem z Wikipedii. Rozwiązaniem (które program znajduje dość szybko) jest["bbaabbbaa","bbaabbbaa"]
.Wyjaśnienie
Jest to właściwie bezpośrednie tłumaczenie problemu korespondencji pocztowej na Brachylog.
Zasadniczo tworzymy listę, która zawiera powtarzające się kopie danych wejściowych (tak mało, jak to możliwe, co oznacza, że nie tracimy żadnych możliwości podczas brutalnego wymuszania), bierzemy jeden element z każdej kopii, a następnie łączymy odpowiednie elementy (jak w korespondencji Post problem).
źródło
~dp
(co nie oznacza całkiem tego samego, ale jest wystarczająco blisko, aby nadal być Turing-complete), z wyjątkiem tego, że interpreter Brachylog nie wie jeszcze, jak cofnąćd
.Galaretka → „Dodaj minimum do transpozycji”,
54 bajtówWypróbuj online! (uruchamia tylko jedną iterację, aby uniknąć przekroczenia limitu czasu)
Bardzo prosta konstrukcja Turinga: bierzemy kwadratową macierz jako program i zapętlamy na zawsze, identyfikując leksykograficznie najmniejszy rząd, a następnie powiększając każdy element pierwszego rzędu o pierwszy element leksykograficznie najmniejszego, każdy element drugiego rzędu przez drugi element najmniejszego leksykograficznie i tak dalej. (Program Jelly „
+"
dodaje odpowiednie elementy {wejścia i}Ṃ
minimum {oryginalnej}ẞ
pętli”; jest to bajt krótszy niż mój poprzedni programZ+ṂZß
, który zrobił dokładnie to samo. Oczywiście powinienem był skupić się na grze w golfa Galaretka, nie tylko golfa zaimplementowanego języka).Powstały język jest kompletny z Turinga z tego samego powodu, co Kangur. Pierwszy element każdego wiersza działa jak liczba pominięć (chociaż zamiast liczby pominięć każdej komendy zmniejszającej się, gdy jest ona pomijana, zamiast tego zwiększamy liczbę pominięć każdej komendy podczas jej uruchamiania i szukamy polecenia o najniższej liczbie pominięć niż komendy z zerową liczbą pominięć; chodzi o to samo). Zapewniamy, że ten pierwszy element jest wyższy niż pozostałe elementy (które reprezentują liczbę wyświetleń każdego polecenia w multisetcie każdego polecenia), zapewniając w ten sposób, że pierwszy wiersz nigdy nie jest minimalny; pozostała część pierwszego rzędu może być śmieciem. Jedynym pozostałym problemem jest modelowanie sposobu, w jaki polecenia o równej liczbie pominięć są uruchamiane cyklicznie w sekwencji, ale możemy to zrobić, mnożąc wszystkie liczby pominięć przez dużą stałą, a następnie dodając małą „początkową” pomiń liczy się do pierwszej kolumny, która służy jako remis. Daje nam to remis „pierwsze niepisane polecenia”, a nie „niepisane polecenia uruchamiane cyklicznie w sekwencji”, ale konstrukcja kompletności Turinga dla Kangura nie przejmuje się tą różnicą.
źródło
Mathematica interpretująca grę Conwaya, 64 bajty
Gra życia Conwaya jest znana jako ukończona przez Turinga; a automaty komórkowe to prawdziwa obsesja Stephena Wolframa.
CellularAutomaton@{224,{2,{t={2,2,2},{2,1,2},t}},{1,1}}
to reguła, która przekształca dwuwymiarową tablicę zer i jedynek zgodnie z jednym krokiem Gry życia Conwaya. (Myślę, że domyślnym zachowaniem jest to, że tablica owija się wokół jej krawędzi, więc jest to naprawdę dyskretny torus).~Nest~##&
Zamienia tę regułę w funkcję, która po podaniu początkowego stanu tablicy (dowolnych wymiarów) i liczby całkowitejn
jako argumentów, zwraca wartość wynikn
iteracji reguły Game of Life.Dla własnej przyjemności możesz użyć opakowanej wersji
i przewijaj swoją drogę przez 100 pokoleń na planszy 50x50.
źródło
Turtlèd interpretujący CT , 49 bajtów
Mogę to zagrać w golfa
To również nie daje nic użytecznego. po prostu zatrzymuje się wtedy i tylko wtedy, gdy dany program CT zostanie zatrzymany.
ten właśnie zrobiłem jakiś czas temu (potem trochę grałem w golfa)
Jak to działa:
Turtlèd używa komórek siatki. Kiedy mówię „napisz coś na siatce”, mam na myśli, że ciągła grupa znaków jest umieszczana na siatce. przykład
na program
dane są wprowadzane jako pierwsze:
jest to zasadniczo program dla kotów. zapisuje dane wejściowe na siatce.
następnie wprowadzane są polecenia:
co robi z tymi poleceniami:
te polecenia to „produkcje”. jeśli najbardziej wysunięty w lewo bit danych ma wartość 1, kopiuje produkcję na końcu ciągu danych. inaczej nic się nie stanie. następnie bit danych skrajnie lewy jest usuwany i wykorzystuje następną produkcję z bitem danych najbardziej lewostronnym. program zatrzymuje się, gdy nie ma bitów w ciągu danych. Sposobem na zrobienie tych produkcji jest osobne radzenie sobie z częściami i końcem produkcji. tak robi nasz program. oddzielnie kopiuje bity z ciągu poleceń na koniec ciągu danych i oddzielnie usuwa bity z przesyłania danych
na temat tego, jak ten program to robi. po wprowadzeniu poleceń wskaźnik żółwia / siatki przesuwa się z powrotem na lewy bit datastringu. następnie przechodzi w pętlę
to, co robi w tej pętli, to przesuwa się w górę od lewego skrajnego datastringu i zapisuje bieżący znak polecenia (u.). jeśli tak jest; koniec produkcji przesuwa się w dół i usuwa znajdujący się poniżej lewy bit danych i przesuwa się z powrotem w górę (
(;d' u)
). następnie, w obu kierunkach, przesuwa się w dół o jeden (d
). jeśli bit tam nie został usunięty, oznacza to, że musi sprawdzić, czy skopiować nieco z poleceń na końcu. więc jeśli ten znak, który jest lub był lewostronnym zestawem danych, ma wartość 1, przesunie się na koniec prawego końca ciągu danych, skopiuje bit z ciągu poleceń i wróci do miejsca po lewej stronie danych bit ((1[ r].[ l])
). teraz znajduje się albo po lewej stronie danych, która była zerowa, albo po lewej stronie lewej transmisji danych. więc poruszamy się w prawo, jeśli na polu (( r)
). następnie wskaźnik polecenia jest zwiększany, więc zapiszemy następne polecenie w następnej iteracji pętli. Jeśli nie będzie już przesyłania danych, oznacza to, że będziemy na spacji i pętla się zakończy. w przeciwnym razie ponownie uruchomimy pętlę.źródło
Perl → wariant programatora trzech gwiazdek , 26 + 1 = 27 bajtów
Wypróbuj online! (Ten link zawiera nagłówek, który opuszcza program po określonej liczbie iteracji (aby TIO nie przekroczył limitu czasu) i aby drukować stan wewnętrzny po każdej iteracji (aby zrobił coś obserwowalnego).)
Biegnij z
-a
(1 bajtową karą, ponieważ możesz zmieścić ją przed-M5.010
produkcją-aM5.010
).W szczególności implementuje to program Three Star Programmer, w którym polecenia są oddzielone spacjami i w pliku nie są dozwolone komentarze, bez rozszerzeń I / O. (Te zmiany nie mają oczywiście wpływu na kompletność Turinga w języku). Nie ma dowodu na kompletność Turinga dla trzygwiazdkowego programisty online, ale jest to kompletny Turing (udostępniłem szkicowy szkic jego Turinga -kompletność z innymi esoprogramistami, ale przestałem pracować nad językiem, gdy odkryłem, że tak naprawdę dość łatwo było go zaprogramować, gdy tylko przeszedłeś pierwotny szok).
Program tak naprawdę nie potrzebuje wielu wyjaśnień; Program Three Star Programmer ma bardzo prostą specyfikację i jest to jego bezpośrednie tłumaczenie. Jedyne subtelne punkty:
@F
to dane wejściowe do programu w postaci tablicy (jest to konsekwencja-a
); iredo
powtórzy cały program, ponieważ jest w niejawnej pętli (również konsekwencja-a
).źródło
Zestaw x86 (składnia Intel / MASM) -Brainfuck 2127 bajtów.
Nadal w stanie golfa
źródło
Pip interpretacji cykliczne układy tag , 16 bajtów
Pobiera produkcje systemu znaczników jako argumenty wiersza polecenia i początkowy ciąg danych ze standardowego wejścia.
Powyższy kod jest trochę trudny do zweryfikowania, ponieważ nie generuje żadnych danych wyjściowych (więc jedynym możliwym do zaobserwowania zachowaniem jest „kończy” vs. „nie kończy”). Dlatego oto wersja bez golfa, która wyprowadza ciąg danych po każdym kroku, a także kończy się po 20 krokach, więc TIO nie musi radzić sobie z mnóstwem danych wyjściowych z nieskończonych pętli: Wypróbuj online!
Cykliczne systemy znaczników
Cykliczne systemy znaczników są niezwykle prostym, lecz kompletnym modelem obliczeniowym Turinga . Składają się z listy produkcji, które definiują operacje na ciągu danych . Produkcje i ciąg danych składają się z 1 i 0.
Na każdym kroku usuwa się lewy znak ciągu danych.
W obu przypadkach bieżąca produkcja przechodzi cyklicznie na następną produkcję na liście: jeśli jesteśmy przy ostatniej produkcji, zapętlamy się do pierwszej. Wykonanie jest kontynuowane, dopóki ciąg danych nie będzie pusty.
Wyjaśnienie
źródło
1
źródło: linki esolangs do tego arxiv.org/abs/1312.6700 . Niedługo zredaguję moją odpowiedź, a jeśli to pomoże twojej odpowiedzi, powinieneś (choć twój wkład wydaje się wystarczająco golfowy)Iterowane uogólnione funkcje Collatz -> Python 2, 46 bajtów
Wywołaj tę funkcję z listami m-1 a i b, wartością początkową x oraz dzielnikiem m, które łącznie stanowią „program” dla IGCF. Zamiast brać trzecią tablicę, aby wskazać, które moduły należy zatrzymać, po prostu zatrzymuje się, gdy moduł wynosi m-1. Uproszczenie to może wymagać dodatkowego wysiłku, aby przekonwertować dany program Fractran na ten wariant, ale pozwala zaoszczędzić kilka bajtów w tłumaczu.
Wypróbuj online! To TIO pokazuje, jak dodać 5 + 5 w tym języku. Program a = [3], b = [0], m = 2 dodaje, a począwszy od 7776 = 2 ^ 5 * 3 ^ 5 ostatecznie daje 59049 = 3 ^ 10.
źródło
Wariant ResPlicate -> Python 2, 47 bajtów
Ta funkcja interpretuje wariant ResPlicate
Ostatnia zmiana oznacza, że niektóre programy ResPlicate (które spełniają pierwszy warunek) nie będą zachowywać się tak samo w tym wariancie, ale na szczęście interpretery BCT nie wymagają usuniętej funkcjonalności, więc język pozostaje TC.
Wypróbuj online! Ten TIO ma nadrukowany klin, aby pokazać, że działa, i nagłówek, który zabija program po 1 sekundzie, oraz przykład, który potrafi wygenerować więcej danych wyjściowych niż TIO może obsłużyć w ciągu jednej sekundy.
źródło
l=input()
? Byłby bajt krótszy.Perl
-a
→ I / D machine , 24 bajtyWypróbuj online! (zawiera nagłówek, który drukuje stan wewnętrzny i zatrzymuje się po 10 iteracjach, dzięki czemu zachowanie jest obserwowalne)
O języku
Ostatnie kilka dni spędziłem pracując na maszynie I / D , jednym z moich najnowszych pomysłów na bardzo proste języki programowania. Działa w następujący sposób: pamięć danych składa się z nieograniczonej pamięci RAM, początkowo wszystkich zer. Każdy element może przechowywać nieograniczoną liczbę całkowitą (chociaż w praktyce większość programów maszynowych we / wy będzie przechowywać tylko małe liczby całkowite w większości z nich, i używa nieograniczonych liczb całkowitych tylko jako sposobu adresowania komórek o dużych adresach). Istnieje również wskaźnik danych, który wskazuje na komórkę (tzn. Przechowuje adres jako komórkę); początkowo jest to również zero.
Istnieją tylko dwa polecenia:
I
: Zwiększ komórkę, na którą wskazuje wskaźnik danych. (Sam wskaźnik danych pozostaje niezmieniony.)D
: Odłóż wskaźnik danych, tzn. Odczytaj wartość komórki, na którą wskazuje wskaźnik danych. Następnie zapisz wynikową wartość, którą ponownie wczytałeś do wskaźnika danych.Wykonanie po prostu uruchamia program w pętli wielokrotnie, na zawsze.
To dość zaskakujące, że tak prosty język jest kompletny w Turinga, więc pracowałem nad udowodnieniem tego. Oto dowód . Jest dość podobny do (ale prostszego) dowodu na Three Star Programmer, bardzo podobny język (i w rzeczywistości, to zgłoszenie używa tej samej podstawowej „powłoki” OISC wokół programu, różniąc się tylko rzeczywistą zaimplementowaną instrukcją).
O programie
Stosowanie
Dane wejściowe należy podawać na standardowym wejściu i jest to program maszynowy We / Wy bez komentarzy i wykorzystujący składnię RLE / OISC. (Maszyna I / D ma dwie różne, równoważne składnie, ale dla golfisty program obsługuje tylko jedną z nich.) W tej składni program jest sekwencją liczb dziesiętnych, reprezentujących długości sekwencji
I
poleceń międzyD
poleceniami. (Możesz podać dwa lub więcej kolejnychD
poleceń, umieszczającI
między nimi „ciąg 0 poleceń”, więc składnia jest w pełni ogólna).Wyjaśnienie
Jak widać z programu, nie implementuje pojedynczo poleceń
I
iD
. W rzeczywistości jest to (bardzo nieznacznie) optymalizujący interpreter (wyłącznie dlatego, że jest krótszy do pisania w ten sposób). Kluczem jest zobaczyć, że uruchomienie n poleceń zwiększania zwiększa docelowy wskaźnik danych n razy, tj. Dodaje do niego n ; w ten sposób można również zaimplementować ciąg 0 komend przyrostowych, ponieważ dodanie 0 do pamięci nie ma wpływu. Tak więc operacja, którą faktycznie wdrażamy, polega na naprzemiennym wdrażaniu seriiI
iD
. Lub innymi słowy „dodaj ndo wartości wskazywanej przez wskaźnik danych (przechowywanie go z powrotem w wartość wskazywaną przez wskaźnik danych), a następnie odczytaj wartość wskazywaną przez wskaźnik danych i zapisz go we wskaźniku danych ". To wyraźnie bardziej szczegółowe niż potrzeba i możemy to jeszcze bardziej uprościć, aby „dodać n do wartości wskazywanej przez wskaźnik danych, a następnie zapisać tę wartość zarówno w celu wskaźnika danych, jak i samym wskaźniku danych”.To stanowi rdzeń naszego programu. Używamy tablicy
$a
do przechowywania pamięci RAM i$p
jako wskaźnik danych (indeksowanie do tablicy):Dogodnie Perl interpretuje niezainicjowane elementy tablicy jako 0, gdy są one traktowane jak liczby, więc tablica będzie dla nas leniwie inicjowana na zero bez żadnego jawnego kodu, który byłby potrzebny. (Jednym potencjalnym problemem jest dokładność liczbowa, gdy liczby stają się duże; stanie się to jednak tylko wtedy, gdy ilość użytej tablicy przekroczy przestrzeń adresową maszyny (liczby całkowite Perla są wystarczająco duże, aby pomieścić wskaźniki), co nie może się zdarzyć na wyidealizowanej maszynie).
Wreszcie, wszystko, co musimy zrobić, to umieścić ten program w kilku pętlach.
for@F
Pętla, w połączeniu z-a
opcją wiersza poleceń, pętla nad polami standardowego wejścia (definicja domyślna „pola” tu będzie podzielony na spacji).redo
Pętla miejsce całego programu w sposób dorozumiany pętli (poza dogodnie odczyt standardowego wejścia), co spowoduje, że wykonywanie programu w pętli wielokrotnie, zgodnie semantyki urządzenia l / D.źródło
-a
”. codegolf.meta.stackexchange.com/a/14339/9365Galaretka → system 2-Tag , 8 bajtów
Wypróbuj online!
Mam nagrodę faworyzującą praktyczne języki, ale pomyślałem, że równie dobrze mogę spróbować wygrać oryginalne zadanie, gdy byłem przy nim (ponieważ nie jestem w stanie wygrać własnej nagrody).
Implementuje wariant systemów tagów bez zatrzymania, ponieważ nie jest potrzebny do kompletności Turinga. Stany są ponumerowane kolejno od 1, a ciąg początkowy pojawia się przed programem.
Na przykład, Wikipedia podaje przykład systemu tagów {
a
,b
,c
}, {a
→bc
,b
→a
,c
→aaa
} z początkową napisuaaa
; w tym formacie wejściowym, to jest[1,1,1]
,[[2,3],[1],[1,1,1]]
. (Systemy znaczników nie mają ustalonej składni i wydaje się to rozsądnym sposobem na zrobienie tego.)Łącze TIO ma dodane
Ṅ
(„zapisz stan wewnętrzny i nowy wiersz na standardowe wyjście”), aby pokazać, że program faktycznie działa.Wyjaśnienie
źródło
BF / P ”zaimplementowany w maszynie Turinga, 842 bajty
Tabela przejściowa (połączona ze względu na długość)
Stolik przejściowy, wersja mniej golfowa
Użyłem symulatora maszyny Turinga
Z pewnością nie wygra żadnych nagród za długość, ale zawsze chciałem to zrobić, ponieważ BF jest bardzo podobny do maszyny Turinga. Każda komórka przechowuje wartość z
0x0
-0xF
. Szerokość jest jednak daleko, ale witryna internetowa Turing Machine może pójść bez awarii przeglądarki. Funkcje,
i.
(wejściowe i wyjściowe) nie są zdefiniowane, więc jest to trochę bardziej jak P "niż prawdziwy BF.Aby go uruchomić, wklej tabelę przejścia do symulatora maszyny Turinga, ustaw dane wejściowe na kod BF i naciśnij klawisz run.
Taśma TM przechowuje zarówno kod BF, jak i dane BF, z pojedynczym odstępem na środku. Śledzi swoją pozycję w kodzie, modyfikując znak, który jest aktualnie uruchomiony (
[
->(
itd.) I jego pozycję w danych za pomocą^
przed komórką. Po odczytaniu znaku polecenia porusza się, dopóki nie trafi w karetkę, przesuwa jedną komórkę w prawo i wykonuje odpowiednią funkcję. Następnie wraca, szukając jednego ze „zmodyfikowanych” znaków polecenia w kodzie BF i przechodzi do następnego, powtarzając cały proces. Gdy skończy się kod, zatrzymuje się.Najlepszym sposobem na zrozumienie, jak to działa, jest uruchomienie wersji bez golfa, przejście do trybu krokowego i obserwowanie, które linie prowadzą do innych i co robi każdy stan / blok linii.
Wersje z golfem i bez golfa są dokładnie takie same pod względem sposobu działania, ale wersja bez golfa ma bardziej przyjazne dla ludzi nazwy i jest podzielona na sekcje.
źródło
C implementuje (2,3) maszynę Turinga ,
236205 bajtów (4631 mniej, jeśli nie przejmujesz się niezręcznymi danymi wejściowymi)Dzięki Appleshell za -11 bajtów, VisualMelon za -12 bajtów i Johan du Toit za -7 bajtów.
CeilingCat stworzył wersję, która wykorzystuje tylko 144 bajty, patrz tutaj .
(Dodałem tutaj kilka podziałów linii, abyś nie musiał przewijać, ale zwykle większość z nich zostałaby usunięta)
Wypróbuj online!
Aby użyć: Wprowadź ciąg maksymalnie 256 zer, zer i dwójek, aby zainicjować taśmę. Wszelkie niezainicjowane wartości będą wynosić zero. (Wartości inne niż 0, 1 i 2 mogą powodować niezdefiniowane zachowanie.) Program wykona iterację po 256 krokach. Liczbę kroków iteracji można zwiększyć, modyfikując kod, ale oczywiście wymaga to więcej znaków.
To dość długi wpis, ale po raz pierwszy robię jedno z nich i nie używałem dedykowanego języka golfowego. Świetnie się bawiłem, nawet jeśli okazało się, że trwa dłużej niż się spodziewałem.
Wiele bajtów pochodzi z przetwarzania danych wejściowych i wyjściowych, a ja straciłem całe 42 bajty, przyjmując 0, 1 i 2 zamiast NUL, SOH, STX. (Aby to zmienić, usuń
k;
z przodu ifor(;k<256&&d[k];)d[k++]-=48;
z drugiej linii.)Tabela tranzystorów, szczególnie linia
*p=-t*t+(2-s)*t+1+s;
(która ustawia wartości na taśmie), prawdopodobnie mogłaby być również bardziej skompresowana.źródło
k,j;c s,d[256];
(int
domyślnie w C, możesz też przejśći
do globalnej deklaracji, aby zaoszczędzić 3 bajty więcej)k++
i usuwanie{}
zapisuje kilka dodatkowych bajtów:for(;k<256&d[k];)d[k++]-=-48;
Ponieważj
jest to tylko chronometrażysta (wartość nigdy nie używana), możesz go zastąpić (ii
)k
licząc do tyłu: wieszk==256
po pierwszej pętli, więc odliczaj do zera w drugiejfor(;k>0;)
, który opuszczak==-1
, więc ostatnia pętla może się staćfor(;++k<256;)
. (Uwaga: Zwykle gram w golfaC#
, ale wydaje się, że się kompiluje).k<256&&d[k]
, nie&
, ponieważd[k]
był oceniany nak==256
. Ponadto, ponieważk
nie było już gwarancji, że będzie256
po tej pętli, musiałem ją później zresetować, aby zagwarantować 256 kroków. (Jeśli ty (czyli VisualMelon) masz jakieś inne sugestie, prawdopodobnie powinniśmy zamieścić je na czacie, abyśmy nie otrzymywali zbyt wielu komentarzy)Röda wdrażająca Fractran ,
114112106 bajtów1 bajt zapisany dzięki @fergusq przez zmianę parametrów
Wypróbuj online!
Wywołać funkcję tak:
f reference_to_input program
. Dane wyjściowe zostaną zapisane w lokalizacjiinput
.źródło
e[1]
jest zbędny. Ponadto można zapisać jeden bajt zmieniając kolejność parametrów:f&n,a
.f&n,a
podstęp, a ja właśnie miałem usunąć ten średnik, kiedy skomentowałeś :)Clojure,
8281 bajtów (maszyna Turinga)Aktualizacja: usunięto spację z
t{} s
.Implementuje maszynę Turinga jako pętlę, zwraca taśmę po osiągnięciu stanu zatrzymania. W regułach przejścia między stanami jest to zaznaczone przez pominięcie stanu przejścia. Nastąpi
N
to,nil
a kolejneif-let
zostaną przerwane, ponieważ nie znaleziono odpowiedniego przejścia stanu z wejściowej mapy skrótów%
. W rzeczywistości wystarczy dowolna wartość dla tego stanu, na przykład:abort
0 lub -1.Niegolfowany z przykładowym 3-stanowym 2-symbolowym bobrem z Wikipedii .
Wypróbuj online .
Na pojedynczym rdzeniu 6700K uruchamia on 5-stanowy 2-symbolowy zajęty bóbr (47,1 miliona kroków) w około 29 sekund lub 1,6 miliona kroków / sekundę.
źródło
M → Wskazówka , 4 bajty
Wypróbuj online!
Łącze TIO dodaje stopkę do wywołania funkcji za pomocą przykładowego programu Tip pokazanego na stronie Esolang („automatyczne opakowanie” M do wywoływania funkcji tak, jakby były programami, które nie mogą obsługiwać liczb wymiernych lub stałych, a przynajmniej nie mam nie wymyśliłem, jak to powiedzieć, więc muszę ręcznie przekształcić tę funkcję w pełny program, aby móc ją uruchomić.)
To faktycznie wypisuje przydatne wyjście debugowania; program nie może być napisany w 3 bajtach w M, ponieważ program składający się z dokładnie trzech dyad wywołuje specjalny przypadek w parserze, więc musiałem dodać dodatkowe polecenie, aby uniknąć specjalnego przypadku. Wykonanie go
Ṅ
(wydrukuj za pomocą nowego wiersza) daje przynajmniej użyteczny cel.ı
Nie implementuje operacji wejścia / wyjścia (innych niż zatrzymanie / brak zatrzymania). I / O jest rozszerzeniem Tip (nie jest częścią samego języka) i nie jest wymagane dla kompletności Turinga.
Wyjaśnienie / tło
[1,2,3]
[1,2,3,1,2,3,1,2,3,…]
ḅ
Spojrzałem więc za siebie i ponownie trochę oceniłem. Czy są jakieś operacje, których moglibyśmy użyć zamiast oceny wielomianowej? Idealnie te, które są przemienne, więc nie musimy się martwić kolejnością argumentów? Wkrótce potem zdałem sobie sprawę, że funkcje Collatz są bardziej złożone niż powinny.
I oczywiście, w przeciwieństwie do konwersji podstawowej (
ḅ
), mnożenie (×
) jest przemienne, a zatem nie ma znaczenia, w jakiej kolejności są umieszczone argumenty. Musimy więc tylko napisać×ị
, a następnie umieścić program w nieskończonej rekurencjiß
, i mamy kompletny język Turinga. Dobrze?¹×ịß
¹
¹
Ṅ
jest dobrym wyborem, ponieważ daje użyteczne wyjście debugowania.Czy możliwe są trzy bajty? Chyba że czegoś mi brakuje, nie z tym konkretnym wyborem języka implementacji i implementacji, ale w tym momencie z pewnością wydaje się, że byłoby to możliwe, ponieważ istnieje tak wiele sposobów na zrobienie tego w czterech i tak wielu Turinga języki, które możesz wdrożyć.
źródło
ḋ
iṙ
zamiast×
iị
; wynikowy język nie jest tym samym językiem co Tip, ale jest dość podobny i prawie na pewno kompletny z Turinga z tego samego powodu. Niestetyḋ
nie jest zaimplementowany w M i nie mogę znaleźć sposobu na wykonanie przez Jelly obliczeń o dowolnej precyzji, gdy którekolwiek z danych wejściowych jest liczbą całkowitą niecałkowitą. Jeśli jednak ktoś zna inne języki gry w golfa, w których ta konstrukcja mogłaby zadziałać, możesz spróbować.C interpretujący Brainfuck, 187 bajtów
Wypróbuj online
źródło
Lua interpretuje Brainf ***, 467 bajtów
Wiem, że mogę trochę później odchudzić, ale tutaj skończyła się moja pierwsza przepustka. Pobiera kod brainf ze standardowego wejścia.
źródło
brains
, zawsze jest fajnie, gdy golfiści przypisują listę zmiennych.CJam → wariant ResPlicate,
151413 bajtów-1 bajt dzięki @ ais523
Wariant jest taki sam jak w tej odpowiedzi , z tym wyjątkiem, że liczba elementów zdjętych z kolejki jest o jeden mniejsza niż najwyższa liczba w kolejce.
l~{ ... }h
Część tylko pobiera tablicę jako wejście i powtarza do momentu, że tablica jest pusta.Objaśnienie głównej pętli:
źródło
Chip , 20 + 3 = 23 bajty (reguła 110)
+3 za flagę
-z
Wypróbuj online!
To przesłanie nie jest idealne, ponieważ Chip nie ma (jeszcze) zdolności do zapętlania, więc dane wyjściowe muszą być przekazywane jako dane wejściowe do symulacji wielu generacji, z czymś takim (oczywiście, można uruchomić tę pętlę w nieskończoność, i Chip może obsłużyć dowolnie długie dane wejściowe, więc ta kombinacja jest Turing Complete).
Ta implementacja odbioru wejściowego i wyjściowego podane w formie ASCII
0
s i1
s. Oto logika:Reszta elementów służy do porządkowania:
e*f
powoduje wyjście liczbowe ASCII iE~Zt
kończy wykonanie o dwa bajty po wyczerpaniu danych wejściowych (ponieważ szerokość rośnie o 2 z każdym pokoleniem).źródło
Clojure, 75 bajtów (cykliczny system znaczników)
Aktualizacja 1: zastąpiona
some?
przeznil?
.Aktualizacja 2: Naprawiono brak
S
w gałęzi else wif s
.Implementuje cykliczny system znaczników , zwraca,
nil
jeśli program się zatrzyma, w przeciwnym razie zapętli się. Clojure naprawdę lśni tutaj nieskończonymi leniwymi sekwencjami (takimi jak cykl ) i destrukcją . Jedynki i zera są wskazywane jako wartości prawda i fałsz. Gdy łańcuch danych się skończy,s
staje sięnil
.Nie golfowany:
Przykładowe wyniki:
źródło
Interpretacja JavaScript Reguła 110 , 131 bajtów (99 bajtów? 28 bajtów?)
Jak widać, kod definiuje 3 funkcje
a
,b
ic
. Być może można zaoszczędzić bajty, łącząc je w 1 funkcję (nie wiem jak), ale dobrze, że są tam oddzielne, ponieważ każda z nich już w pewnym sensie spełnia to wyzwanie.Funkcja
a
przyjmuje 3 liczby jako dane wejściowe i oblicza ich dziwny wielomian. Gdy te 3 liczby są0
lub1
mogą być postrzegane jako komórki z reguły 110. Parzystość wynikua
można następnie postrzegać jako wartość środkowej komórki w następnej generacji. W pewnym sensie ta prosta funkcja jest już „interpretatorem” reguły 110 (28 bajtów):Następnie możemy utworzyć nową funkcję,
b
która będzie oceniaća
każdy znak ciągu zer i jedynek. Jestb
to zatem, w lepszy sposóba
, interpretator reguły 110. Biorąc mod 2 po ocenie nawiasów klamrowych (99 bajtów):Aby faktycznie obliczyć funkcję z regułą 110, użytkownik musi określić stan początkowy i liczbę pokoleń, po których wynik „pojawi się”. Możemy stworzyć trzecią funkcję,
c
która pobiera ciąg zer i jedynek, oraz dodatnią liczbę całkowitąn
, która następnie oceniab
ciąg,n
razy. W ten sposób możemy naprawdę zobaczyć Regułę 110 jako język programowania, w którym program jest stanem początkowym i liczbąn
, a wynikiem jest stan pon
pokoleniach. Ta funkcjac
jest teraz rzeczywistym tłumaczem dla tego języka programowania, więc ostateczny kod tego wyzwania jest tym, co przedstawiłem powyżej.źródło
JS -> Newline 854 bajtów
Super golfa dzięki Google.
źródło
var
stwierdzenia:var b=0,n=!0,c=[],h=[],e=0,l=[],m=0,f=2,a=0,g=!1;
var
tyClojure, 87 bajtów (art. 110 Regulaminu)
Kredyt za kod parzystości otrzymuje Jens Renders! Naprawdę walczyłem z tym, jak to wyrazić i zamierzałem przejść z konwersji
[p q r]
z binarnej na liczbę całkowitą i użyć tabeli odnośników.Tutaj
partition
i destrukcja Clojure'a sprawia, że aplikacja logiczna jest dość prosta. Ta funkcja zwraca nieskończoną sekwencję stanów, więc osoba dzwoniąca jest odpowiedzialnatake
za tyle, ile potrzebuje lub po prostunth
przeskakuje do określonego stanu. Gdyby wypełnienia z zerem były dwoma elementami zamiast tylko jednego, taśma ciągle by się powiększała, unikając problemów z granicami. Teraz zachowuje oryginalną szerokość.Przykład:
źródło
cycle
będzie w stanie skonstruować nieskończony wzór wyściółki, ale wykonanie pierwszego kroku zajmie nieskończoną ilość czasu: /APL (Dyalog) → wariant Fractran , 15 bajtów
Wypróbuj online!
Funkcja przyjmuje argumenty jako listę liczb, a nie dwie listy zawierające licznik i mianownik, i wyświetla wynik, jeśli program się zakończy. To implementuje wariant Fractran, który ma wymierną 1/1 (= 1) na końcu programu. 1 nie ma wpływu na kompletność Turinga (o ile rozumiem), ponieważ dane wejściowe do programu lądują na 1 tylko wtedy, gdy żadne inne uzasadnienie nie działa, a gdy tak się dzieje, dane wejściowe nie są zmieniane. Jest to używane tylko po to, aby funkcja wiedziała, kiedy zakończyć.
Łącze TIO uruchamia funkcję dla 2 iteracji (aby można było zobaczyć wynik, ponieważ program się nie kończy) na pierwszym wejściu i uruchamia drugie wejście do zakończenia, po czym zwraca wyjście.
(⊃0~⍨××0=1|×)⍣≡
przyjmuje listę wymiernych argumentów jako lewy argument, który będzie określany jako ⊣, a dane wejściowe jako prawy argument, który będzie nazywany ⊢(⊃0~⍨××0=1|×)
pociąg funkcyjny1|×
pobierz część po przecinku dziesiętnym (moduł 1) iloczynu×
⊣ i ⊢0=
czy to wynosi 0?××
pomnóż ten wynik przez ⊣ × ⊢, gdziekolwiek wymierna × ⊢ nie jest liczbą całkowitą, jest zastępowana przez 00~⍨
usuń wszystkie zera⊃
zdobądź pierwszy element⍣
pętli, dopóki≡
dane wejściowe się nie zmienią, zwróć uwagę, że wynik(⊃0~⍨××0=1|×)
jest ponownie wykorzystywany jako wejście, więc jeśli przestanie się zmieniać (w wyniku 1 na końcu), program zatrzyma sięźródło
JavaScript: Lambda Calculus (
123114)Reprezentowany przy użyciu wskaźników Debruijn w duplikach.
Kombinator S to
[0, [0, [0, [[3, 1], [2, 1]]]]]
K jest
[0, [0, 2]]
Ja jestem
[0, 1]
Edycja: Ogolono 9 bajtów, zastępując
"number"==typeof c
je!isNaN(c)
źródło
APL (Dyalog Unicode) , 15 bajtów SBCS
Pełny program, który implementuje uogólniony jednowymiarowy moduł wykonujący automat komórkowy. Obejmuje to zasadę 110, która jest kompletna w Turinga. Monituje stdin o stan początkowy, liczbę iteracji (lub
≡
kontynuowanie aż do stabilnego lub{⍵≡⎕←⍺}
wyświetlanie wszystkich wartości pośrednich aż do stabilnego) i zestaw reguł.Wypróbuj online! (4 iteracje art. 110 Regulaminu)
⎕
monit o stan początkowy i⊢
wydajność, która (oddziela stan od liczby iteracji)⍣⎕
zapytaj o liczbę iteracji i zastosuj następującą funkcję wiele razy:(
…)
Zastosuj następującą funkcję ukrytą:⌺3
uzyskaj wszystkie dzielnice długości-3 (z informacją, czy znajdują się na krawędzi) i zastosuj następującą funkcję milczącą dla każdej pary:⊂
ogrodzić okolicę∘
i⊢
daje to (odrzucając informację o byciu na krawędzi)∘
następnie∊⍨
sprawdź, czy są członkami⎕
monit o listę dzielnic prowadzących do włączenia w następnej iteracjiźródło