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:

1. Możesz użyć dowolnego języka do stworzenia tego tłumacza, nawet jeśli jest on nowszy niż to wyzwanie.
2. Możesz używać dowolnego języka pełnego Turinga, o ile nie jest on tym samym językiem, w którym go piszesz.
3. Nie można po prostu oceniać kodu, na przykład używać funkcji eval.
4. Wyjaśnienie, jak do tego podszedłeś, będzie miłe, ale nie wymagane.
5. To będzie punktowane w bajtach.
6. 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!

Brachylog (2) → Problem z korespondencją pocztową , 9 bajtów

~h=∋ᵐ\cᵐ=

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.

~h=∋ᵐ\cᵐ=
~h         Find {the shortest possible} list which starts with {the input}
  =        and for which all elements are equal
   ∋ᵐ      such that taking an element of each element,
     \cᵐ   and concatenating elements in corresponding positions,
        =  produces a list all of whose elements are equal.

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

Galaretka → „Dodaj minimum do transpozycji”, 5 4 bajtów

+"Ṃẞ

Wypró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 program Z+Ṃ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ą.

Mathematica interpretująca grę Conwaya, 64 bajty

CellularAutomaton@{224,{2,{t={2,2,2},{2,1,2},t}},{1,1}}~Nest~##&

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łkowitej njako argumentów, zwraca wartość wynik niteracji reguły Game of Life.

Dla własnej przyjemności możesz użyć opakowanej wersji

b = RandomInteger[1,{50,50}];
Manipulate[ArrayPlot[
  CellularAutomaton@{224,{2,{t={2,2,2},{2,1,2},t}},{1,1}}~Nest~##&
    [b, n] ]
, {{n,0}, 0, 100, 1}]

i przewijaj swoją drogę przez 100 pokoleń na planszy 50x50.

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)

!-l[*+.r_]' !l[ l]r[ u.(;d' u)d(1[ r].[ l])( r)+]

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

[ ][ ][ ][ ][ ][ ][ ]
[ ][H][E][L][L][O][ ]
[ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ]

na program

dane są wprowadzane jako pierwsze:

!-l[*+.r_]' 

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ę

[ u.(;d' u)d(1[ r].[ l])( r)+]

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

Perl → wariant programatora trzech gwiazdek , 26 + 1 = 27 bajtów

++$a[$a[$a[$_]]]for@F;redo

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.010produkcją -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: @Fto dane wejściowe do programu w postaci tablicy (jest to konsekwencja -a); i redopowtórzy cały program, ponieważ jest w niejawnej pętli (również konsekwencja -a).

Zestaw x86 (składnia Intel / MASM) -Brainfuck 2127 bajtów.

Nadal w stanie golfa

.386
.model flat,stdcall
.stack 4096
include \masm32\include\masm32.inc
includelib \masm32\lib\masm32.lib
ExitProcess proto,dwExitCode:dword
.data
bfsrc BYTE 200 dup(0) 
bfcells BYTE 100 dup(0) 
loopStack DD 5 dup(0) 
charBuf BYTE 5 dup(0) 
newline BYTE 10,0 
prompt BYTE "$",0 
hr BYTE 50 dup('-'),0 
space BYTE ' ',0
.code
EvalBf proc
    start:
    invoke StdOut, addr prompt
    invoke StdIn, addr bfsrc,200
    cmp bfsrc,0
    je exit
    mov eax,0 
    mov ebx,0 
    mov ecx,0 
    processInstruction:
    cmp BYTE PTR bfsrc[ebx], '+'
    je plus
    cmp BYTE PTR bfsrc[ebx], '-'
    je minus
    cmp BYTE PTR bfsrc[ebx], '>'
    je fwd
    cmp BYTE PTR bfsrc[ebx], '<'
    je back
    cmp BYTE PTR bfsrc[ebx], '['
    je open
    cmp BYTE PTR bfsrc[ebx], ']'
    je close
    cmp BYTE PTR bfsrc[ebx], '.'
    je dot
    jmp processNextInstruction
    plus:
    inc BYTE PTR bfcells[eax]
    jmp processNextInstruction
    minus:
    dec BYTE PTR bfcells[eax]
    jmp processNextInstruction
    fwd:
    inc eax
    jmp processNextInstruction
    back:
    dec eax
    jmp processNextInstruction
    open:
    mov loopStack[ecx*4],ebx
    inc ecx
    jmp processNextInstruction
    close:
    dec ecx
    cmp BYTE PTR bfcells[eax], 0
    je processNextInstruction
    mov ebx,loopStack[ecx*4]
    inc ecx
    jmp processNextInstruction
    dot:
    mov dl, BYTE PTR bfcells[eax]
    mov BYTE PTR charBuf[0], dl
    mov BYTE PTR charBuf[1],0anything
    push eax
    push ecx
    invoke StdOut, addr charBuf
    pop ecx
    pop eax
    jmp processNextInstruction
    processNextInstruction:
    inc ebx
    cmp BYTE PTR bfsrc[ebx], 0
    je done
    jmp processInstruction
    done:
    invoke StdOut, addr newline
    mov eax, 0
    printNext:
    cmp eax, 100
    jge reset
    push eax
    invoke dwtoa, BYTE PTR bfcells[eax], addr charBuf
    invoke StdOut, addr charBuf
    invoke StdOut, addr space
    pop eax
    inc eax
    jmp printNext
    reset:
    invoke StdOut, addr newline
    invoke StdOut, addr hr
    invoke StdOut, addr newline
    jmp start

    exit:
    invoke ExitProcess,0
EvalBf endp
end EvalBf

Pip interpretacji cykliczne układy tag , 16 bajtów

YqWyyPBg@++vXPOy

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.

• Jeśli znak ma wartość 1, bieżąca produkcja jest dołączana po prawej stronie ciągu danych.
• Jeśli znak ma wartość 0, nic nie jest dodawane.

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

                  g is list of cmdline args; v is -1 (implicit)
 q                Read a line of stdin for the data string
Y                 and yank it into the y variable
  Wy              While data string is nonempty:
       g@++v       Retrieve the next production from g (using cyclic indexing)
             POy   Pop the first character of y
            X      String-multiply: result is the production if the first character of y
                   was 1, or empty string if it was 0
    yPB            Push that string to the back end of y

Iterowane uogólnione funkcje Collatz -> Python 2, 46 bajtów

a,b,x,m=input()
while-~x%m:x=x/m*a[x%m]+b[x%m]

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.

Wariant ResPlicate -> Python 2, 47 bajtów

l=input()
while l:l=l[2+l[0]:]+l[2:2+l[0]]*l[1]

Ta funkcja interpretuje wariant ResPlicate

• dla których program jest listą pythonową o parzystej długości z parzystymi elementami o parzystych indeksach.
• bez I / O.
• dla których próba skopiowania większej liczby wartości niż istnieje w pozostałej części kolejki, po prostu kopiuje pozostałą część kolejki (tzn. skopiowany bit nie jest dopełniany zerami do wymaganej długości).

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.

Perl -a → I / D machine , 24 bajty

$p=$a[$p]+=$_ for@F;redo

Wypró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 Ipoleceń między Dpoleceniami. (Możesz podać dwa lub więcej kolejnych Dpoleceń, umieszczając Imię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ń Ii D. 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 serii Ii D. 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 $ado przechowywania pamięci RAM i $pjako wskaźnik danych (indeksowanie do tablicy):

$p=$a[$p]+=$_
         + $_  add {the run length}
   $a[$p]      to the element of $a pointed to by $p
   $a[$p] =    storing the result back into that element
$p=            and also in the pointer itself

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@FPętla, w połączeniu z -aopcją wiersza poleceń, pętla nad polami standardowego wejścia (definicja domyślna „pola” tu będzie podzielony na spacji). redoPę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.

Galaretka → 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ą napisu aaa; 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

µḢị⁴⁸;Ḋß
           {implicit: initialise internal state from first argument}
µ          Disregard the second command-line argument by default
 Ḣ         Take the first element, removing it from the internal state
  ị⁴       Use the value to index into the second argument
    ⁸;     Prepend (the rest of) the internal state
      Ḋ    Discard the first element of the internal state
       ß   Loop forever

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.

C implementuje (2,3) maszynę Turinga , 236 205 bajtów ( 46 31 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)

#define c char
j;i;k;c s,d[256];c main(){c*p=d+128;gets(d);
for(;k<256&&d[k];)d[k++]-=48;for(;++j<256;)
{c t=*p;*p=-t*t+(2-s)*t+1+s;p+=(s^t==0)*2-1;s=s?t%2:!t%3;
for(i=0;++i<256;)printf("%d",d[i]);puts("");}}

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 i for(;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öda wdrażająca Fractran , 114 112 106 bajtów

1 bajt zapisany dzięki @fergusq przez zmianę parametrów

f&n,a{x=1{x=0;(a/" ")()|[_/`/`]|[parseInteger(_[0],_1[1])]|{|q,w|{n*=q/w;x=1}if[n%w<1,x<1]}_,_}while[x>0]}

Wypróbuj online!

Wywołać funkcję tak: f reference_to_input program. Dane wyjściowe zostaną zapisane w lokalizacji input.

Clojure, 82 81 bajtów (maszyna Turinga)

Aktualizacja: usunięto spację z t{} s.

#(loop[p 0 t{}s 1](if-let[[S M N](%[(or(t p)0)s])](recur(+ p M)(assoc t p S)N)t))

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 Nto, nila kolejne if-letzostaną 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 :abort0 lub -1.

Niegolfowany z przykładowym 3-stanowym 2-symbolowym bobrem z Wikipedii .

(def f #(loop[pos 0 tape {} state 1]
          (if-let [[sym move next-state](%[(get tape pos 0)state])]
            (do (println [pos tape state])
                (recur(+ pos move)(assoc tape pos sym)next-state))
            tape)))

(f {[0 1] [1  1 2]
    [0 2] [1 -1 1]
    [0 3] [1 -1 2] 
    [1 1] [1 -1 3]
    [1 2] [1  1 2]
    [1 3] [1  1]})

{0 1, 1 1, -1 1, -2 1, -3 1, 2 1}

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

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.

ı$i=\sqrt{-1}$

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

Ṅ×ịß
Ṅ     Print {the left argument} and a newline; also resolves a parser ambiguity
  ị   {The left argument}th element of {the right argument}, wrapping on OoB
 ×    Multiply {the left argument} by {the chosen element}
   ß  Recursive call; arguments: {the product} and {the same right argument}

[1,2,3][1,2,3,1,2,3,1,2,3,…]$rx+s$, który jest wielomianem, a wbudowana „konwersja podstawowa”, którą ma wiele języków golfowych, jest w rzeczywistości ukrytym oceniaczem wielomianów ogólnego przeznaczenia. Więc wszystko, co musimy zrobić, to zindeksować listę cyfr, przekonwertować je i już gotowe, prawda?

$x$$x$

ḅ$x\oplus(x\otimes y)$$x\otimes y$${\oplus}$. Pewnie, moglibyśmy zastąpić łańcuchowe zachowanie prawie wszystkim, czego chcemy, ale to kosztowałoby cały bajt, a wpisy języka golfowego w tym pytaniu stają się tak krótkie, że bajt to dużo.

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.

$s$

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?

$(x\odot y)\oplus(x\otimes y)$¹×ịß¹¹Ṅ 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ć.

C interpretujący Brainfuck, 187 bajtów

t[999],*p=t,c,i,l;f(char*t){for(i=0;c=t[i];i++){c^62?c^60?c^43?c^45?c^46?c^44?c^91:(*p=getchar()):putchar(*p):--*p:++*p:--p:++p;if(c==93&&*p)for(l=1;l>0;)c=t[--i],c==91?l--:c==93?l++:0;}}

Wypróbuj online

Lua interpretuje Brainf ***, 467 bajtów

b,r,a,i,n,s=0,io.read,{0},1,1,"><+-.,[]"c,f=r(),{function()n=n+1;a[n]=a[n]or 0;end,function()n=n-1;a[n]=a[n]or 0;end,function()a[n]=a[n]+1;end,function()a[n]=a[n]-1;end,function()io.write(string.char(a[n]))end,function()a[n]=io.read():byte()end,function()i=a[n]~=0 and i or c:find("]",i)end,function()if a[n]~=0 then b,x=1,""repeat i=i-1 x=c:sub(i,i)b=x=="["and b-1 or x=="]"and b+1 or b until b==0 and x=="["end end}repeat f[s:find(c:sub(i,i),1,1)]()i=i+1 until i>#c

Wiem, że mogę trochę później odchudzić, ale tutaj skończyła się moja pierwsza przepustka. Pobiera kod brainf ze standardowego wejścia.

CJam → wariant ResPlicate, 15 14 13 bajtów

^{-1 bajt dzięki @ ais523}

l~{(/((*+e_}h

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~{ ... }hCzęść tylko pobiera tablicę jako wejście i powtarza do momentu, że tablica jest pusta.

Objaśnienie głównej pętli:

    e# Stack:             | [3 2 1 1 2 2 2 1]
(   e# Pop first element: | [2 1 1 2 2 2 1] 3
/   e# Split chunks:      | [[2 1 1] [2 2 2] [1]]
(   e# Pop first:         | [[2 2 2] [1]] [2 1 1]
(   e# Pop first:         | [[2 2 2] [1]] [1 1] 2
*   e# Repeat array:      | [[2 2 2] [1]] [1 1 1 1]
+   e# Concatenate:       | [[2 2 2] [1] 1 1 1 1]
e_  e# Flatten:           | [2 2 2 1 1 1 1 1]

Chip , 20 + 3 = 23 bajty (reguła 110)

AZZ
>}/a
`)\'E~Zte*f

+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 0s i 1s. Oto logika:

p := value of left neighbor cell    AZZ
q := value of current cell          AZ
r := value of right neighbor cell   A

q' := ((r xor q) and p) or          >}/a
      ((r or q) and ~p)             `)\'

Reszta elementów służy do porządkowania: e*fpowoduje wyjście liczbowe ASCII i E~Ztkończy wykonanie o dwa bajty po wyczerpaniu danych wejściowych (ponieważ szerokość rośnie o 2 z każdym pokoleniem).

Clojure, 75 bajtów (cykliczny system znaczników)

Aktualizacja 1: zastąpiona some?przez nil?.

Aktualizacja 2: Naprawiono brak Sw gałęzi else w if s.

#(loop[[p & P](cycle %)[s & S]%2](if(nil? s)S(recur P(if s(concat S p)S))))

Implementuje cykliczny system znaczników , zwraca, niljeś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, sstaje się nil.

Nie golfowany:

(def f #(loop[[p & P] (cycle %) [s & S] %2 i 5]
          (do
            (pprint [p (concat [s] S)])
            (if (and (some? s) (pos? i))
              (recur P (if s (concat S p) S) (dec i))))))

Przykładowe wyniki:

(f [[false]] [true true])
[[false] (true true)]
[[false] (true false)]
[[false] (false false)]
[[false] (false)]
[[false] (nil)]

(f [[false true true] [true false] [true false true]] [true])
[[false true true] (true)]
[[true false]      (false true true)]
[[true false true] (true true)]
[[false true true] (true true false true)]
[[true false]      (true false true false true true)]
[[true false true] (false true false true true true false)]

Interpretacja JavaScript Reguła 110 , 131 bajtów (99 bajtów? 28 bajtów?)

a=(p,q,r)=>q+r+q*r+p*q*r
b=l=>{r="";for(i=0;i<l.length-2;i++)r+=a(l[i],+l[i+1],+l[i+2])%2;return r}
c=(l,n)=>!n?l:c(b(0+l+0),n-1)

Jak widać, kod definiuje 3 funkcje a, bi c. 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 aprzyjmuje 3 liczby jako dane wejściowe i oblicza ich dziwny wielomian. Gdy te 3 liczby są 0lub 1mogą być postrzegane jako komórki z reguły 110. Parzystość wyniku amoż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):

a=(p,q,r)=>(q+r+q*r+p*q*r)%2

Następnie możemy utworzyć nową funkcję, bktóra będzie oceniać akażdy znak ciągu zer i jedynek. Jest bto zatem, w lepszy sposób a, interpretator reguły 110. Biorąc mod 2 po ocenie nawiasów klamrowych (99 bajtów):

a=(p,q,r)=>q+r+q*r+p*q*r
b=l=>{r="";for(i=0;i<l.length-2;i++)r+=a(l[i],+l[i+1],+l[i+2])%2;return r}

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ę, cktóra pobiera ciąg zer i jedynek, oraz dodatnią liczbę całkowitą n, która następnie ocenia bciąg, nrazy. 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 po npokoleniach. Ta funkcja cjest teraz rzeczywistym tłumaczem dla tego języka programowania, więc ostateczny kod tego wyzwania jest tym, co przedstawiłem powyżej.

JS -> Newline 854 bajtów

(function(d){var b=0;var n=!0;var c=[];var h=[];var e=0;var l=[];var m=0;var f=2;var a=0;var g=!1;var k=function(a){if(a===1)return!1;if(a%2===0&&a!==2)return!1;if(a%3===0&&a!==3)return!1;if(a%5===0&&a!==5)return!1;if(a%7===0&&a!==7)return!1;for(var b=7;b<d.round(d.sqrt(a))+1;b++)if(a%b===0)return!1;return f=a,!0;};var j=0;var i=0;var o=function(q){var o=d.__split(q,'\n');d.println(o);for(var n=0;n<o.length;n++)if(n>=f^2&&n<=f+1^2&&k(n)){f=n;for(var p=0;p<o[n].length;p++){if(o[n]==='+'&&(a+=c[b],b++),o[n]==='-')if(g===!0&&a<=0)break;else a-=c[b],b++;if(o[n]==='*'&&(a*=c[b],b++),o[n]==='/'&&(a/=c[b],b++),o[n]==='s'&&(a=d.sqrt(a)),o[n]==='%'&&(a%=c[b],b++),o[n]==='a'&&l.push(a),o[n]==='g'&&(a=c[b],b++),o[n]==='q'&&c.push(a),o[n]==='i'&&a++,o[n]==='d')if(g===!0&&a<=0)break;else a--;o[n]==='r'&&(g=!0),o[n]==='w'&&(g=!1),o[n]==='['&&(j=n),o[n]===']'&&a>0&&(n=j,h[e]--),o[n]==='{'&&(i=n),o[n]==='}'&&h[e]>0&&(n=i,h[e]--),m=a,o[n]==='k'&&e++;}}};});

Super golfa dzięki Google.

Clojure, 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.

#(iterate(fn[S](for[[p q r](partition 3 1(concat[0]S[0]))](mod(+ q(* q(+ 1 p)r)r)2)))%)

Tutaj partitioni destrukcja Clojure'a sprawia, że ​​aplikacja logiczna jest dość prosta. Ta funkcja zwraca nieskończoną sekwencję stanów, więc osoba dzwoniąca jest odpowiedzialna takeza tyle, ile potrzebuje lub po prostu nthprzeskakuje 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:

(def f #(iterate(fn[S](for[[p q r](partition 3 1(concat[0]S[0]))](mod(+ q(* q(+ 1 p)r)r)2)))%))

(pprint (take 5 (f '(0 0 0 0 0 1 1 1 0 0 1 0 0))))
((0 0 0 0 0 1 1 1 0 0 1 0 0)
 (0 0 0 0 1 1 0 1 0 1 1 0 0)
 (0 0 0 1 1 1 1 1 1 1 1 0 0)
 (0 0 1 1 0 0 0 0 0 0 1 0 0)
 (0 1 1 1 0 0 0 0 0 1 1 0 0))

APL (Dyalog) → wariant Fractran , 15 bajtów

(⊃0~⍨××0=1|×)⍣≡

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 funkcyjny

• 1|×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 0

• 0~⍨ 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ę

JavaScript: Lambda Calculus ( 123 114)

Reprezentowany przy użyciu wskaźników Debruijn w duplikach.

V=function b(c,d){if(!isNaN(c)){for(;--c;)d=d[1];return d[0]}return 0==c[0]?e=>b(c[1],[e,d]):b(c[0],d)(b(c[1],d))}

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 cje!isNaN(c)

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

⎕∊⍨∘(⊢∘⊂⌺3)⍣⎕⊢⎕

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