Pomieszaj moje próby rozwiązania problemu zatrzymania

31

Uwaga: specyfika tego wyzwania jest z natury trudna do zrozumienia. Prawdopodobnie wymaga co najmniej pierwszego kursu teorii obliczeń lub równoważnego czytania w tle. Ponadto samo wyzwanie jest dość trudne. Udzielenie odpowiedzi będzie wymagało napisania całego tłumacza dla wybranego podzbioru wybranego przez ciebie języka, i nie tylko to, ale tłumacz będzie musiał mieć formę czegoś w rodzaju quine. Jeśli twoja odpowiedź nie robi tego wszystkiego, prawie na pewno nie spełnia specyfikacji.

Nie musisz rozwiązać problemu zatrzymania (nawet częściowo), aby rozwiązać to wyzwanie. Jednak prawie na pewno zrobić potrzebę napisania tłumacza (języka używanego, napisany w tym samym języku, to interpretuje), choć nie musi być cechą kompletne. To właśnie sprawia, że ​​jest to interesujące wyzwanie.

Obiecałem przyznać nagrodę w wysokości 500 punktów za pierwszą odpowiedź spełniającą specyfikację, a ta zostanie przyznana odpowiedzi BF Jo Kinga .

Wyzwanie

Surowa, uproszczona wersja dowodu Alana Turinga na nierozwiązywalność problemu zatrzymania wygląda mniej więcej tak:

Załóżmy, że napisałem program, Fktóry ma rozwiązać program zatrzymujący. Oznacza to, że Fpobiera kod źródłowy innego programu jako dane wejściowe i F(G)powinien zwrócić, 1jeśli zostanie Gzatrzymany, i w 0inny sposób.

Ale jeśli dam ci mój program F, możesz zbudować inny program H, który uruchamia mój program Hjako jego dane wejściowe. Jeśli F(H)zwraca, 0to Hwraca 0, ale w przeciwnym razie celowo przechodzi w nieskończoną pętlę. Prowadzi to do paradoksu i musimy stwierdzić, że w Fkońcu nie można rozwiązać problemu zatrzymania.

Twoim zadaniem jest napisanie programu H, ale z niespodzianką: nie dam ci mojego programu. Zamiast tego twój program odbierze kod źródłowy mojego programu jako dane wejściowe. To jest:

  • Twój program odbierze mój program jako dane wejściowe w postaci kodu źródłowego. (Np. Jako plik lub dane wejściowe z wiersza poleceń, szczegóły zależą od Ciebie.)

  • Mój program zostanie napisany w tym samym języku co Twój program, a także pobiera dane wejściowe w postaci ciągu kodu źródłowego.

  • Jeśli mój program powróci, 0gdy podasz program jako dane wejściowe, twój program powinien się zatrzymać (i powrócić 0), gdy poda mój program jako dane wejściowe. (Dokładne znaczenie słowa „returing 0” należy do Ciebie).

  • jeśli mój program się nie zatrzyma lub jeśli zwróci coś innego niż 0podany jako dane wejściowe, program powinien działać bez końca.

Rzecz w tym, że aby uczynić to naprawdę o wiele trudniejszym, musisz przestrzegać następujących zasad:

  1. Nie można użyć żadnej wbudowanej funkcji execlub evaltypu.

  2. Nie można użyć żadnych metod „oszukiwania”, aby uzyskać kod źródłowy własnego programu. (Na przykład nie możesz powiedzieć „zapisz to w pliku o nazwie„ program ”, a następnie open(program)umieść w swoim programie).

Oznacza to, że twój program musi być jakimś zwariowanym super-quine'em, który może nie tylko odtwarzać własny kod źródłowy w postaci łańcucha, ale także potrafi poprawnie parsować i interpretować język, w którym jest napisany.

Aby uczynić to nieco mniej niesamowicie trudnym, możesz używać tylko (kompletnego Turinga) wybranego języka. Więc jeśli twój program jest napisany w Pythonie i będzie działał tylko wtedy, gdy mój program zawiera tylko ifs i whilepętle oraz podstawowe operacje na łańcuchach, to jest OK, o ile twój program również używa tylko tych rzeczy. (Oznacza to, że nie musisz się martwić implementacją całej standardowej biblioteki wybranego języka!) Jednak Twój program musi się uruchomić - nie możesz po prostu stworzyć własnego języka.

To , więc wygrywa odpowiedź z największą liczbą głosów. Jednakże, jak wspomniano powyżej, poważnym wyzwaniem jest w ogóle spełnienie specyfikacji, więc przyznam nagrodę w wysokości 500 punktów za pierwszą odpowiedź, która to zrobi, zgodnie z moim osądem.

Uwaga: bez wątpienia istnieje wiele sposobów „oszukiwania” w tym wyzwaniu, biorąc pod uwagę dokładne sformułowanie, którego użyłem. Jednak naprawdę liczę na odpowiedzi, które wpisują się w ducha pytania. Wyzwanie zgodnie z planem jest bardzo trudne, ale możliwe, i naprawdę mam nadzieję, że uda mi się znaleźć oryginalne rozwiązania. Nie przyznam nagrody za odpowiedź, która według mnie jest oszukiwana.


Uwaga: to wyzwanie zostało pierwotnie opublikowane jako , ale zostało zamknięte w 2016 r. Z powodu braku „obiektywnego kryterium wygranej” i zmieniłem je na , aby je ponownie otworzyć. Jednak odkryłem, że od stycznia 2018 r s nie są w rzeczywistości zakazane na PPCG (z tego jest najnowsza meta dyskusja) zamykając go na pierwszym miejscu był przeciwny polityce miejscu. Rozumiem, że popcony nie są obecnie popularne, ale jest to stare wyzwanie, a jego natura naprawdę nie nadaje się do system oceniania. Jeśli ktoś nadal uważa, że ​​nie powinno to być dozwolone, zróbmy meta dyskusję, zanim zaczną się rzucać bliskie głosy. Wreszcie, na wszelki wypadek, że ktoś spędził ostatni rok na próbowaniu golfa swojego rozwiązania, zapewniam cię, że będzie tak samo konkurencyjny w tym wyzwaniu i równie godny nagrody, jak w przypadku wersja.

Nataniel
źródło
1
Zwracając, masz na myśli kod wyjścia lub standardowe wyjście? Czy oba są dopuszczalne?
PlasmaPower
Oba są dopuszczalne.
Nathaniel
@Nanielaniel Rozumiem, że eksportowanie otrzymanego kodu Fdo pliku i wprowadzanie go byłoby nielegalne import? ; 3
cjfaure
1
Bardzo podoba mi się to pytanie, ale trudno je zrozumieć. Jeśli ktoś ma problemy, te dwa slajdy (w języku Java psuedocode) znacznie ułatwiły mi zrozumienie: imgur.com/a/NRmyO
Harry
1
Wspominasz o „duchu pytania” i „prawdziwych rozwiązaniach”. Co przez to rozumiesz? Czy sami powinniśmy napisać tłumacza dla naszego języka? Nie wyobrażam sobie innego sposobu na zrobienie tego.
KSFT

Odpowiedzi:

23

brainfuck , 6013 4877 4376 bajtów

Edycja: -1136 bajtów. Przełączono na lepszy sposób generowania danych dla quine

Edycja2: -501 bajtów. Ponownie odwiedziłem mojego interpretera i skróciłem go o kilkaset bajtów

->++>++++>+>++>+++>>++++>>++++>>+++>>++++>>+++>>++>++>++>++>++>++>++>++>++>++>++++>+++++>+>++>++>++>++>++>++>>+++>+>++>++>++++>+>+++>+>++++>+>+++>+>++>>>+++++>++++>++++>>+++>>++++>>+++>>++>++>++>++>++>++>++>++++>+++++>+>++>++>++>++>++>++>>+++>+>++>++++>+>+++>+>++++>+>+++>+>++>>>+++++>+++>>+++>+>+++++>+++++>++++>>++>+>++>++>++>++>++>++>+++>>++>++>>++++>>+++>++>++>++>++>++>++++>+++++>>++>++>++>+>+++>>++++>>++>++>++>>++>++>++>>++>++>++>>++>++>++>++>++>++>>++>++>++>++>++>++>>++>++>++>>++>++>++>++>>++>++>++>++>++++>+>+++>>+++++>+++>>++>>+++++>>>++>>++>++>++>>+++++>+++++>>>++>++>++++>+>+++>+>+>++++>+>+++>+>+>++++>+>+++>>++++>++++>++++>>+++>>>++++>>+++>>>++++>>+++>+>++++>+++++>>>++>+>+>+++>+>++++>+>+++>+>+>++++>+>+++>+>+>++++>+>+++>>+++++>+++>>++++>>+++>>>++++>>+++>>>++++>>+++>>>++++>+++++>+>+>++>++++>+>+++>+>++>>>++++>>+++>>+++>+>+>++++>++++>+++++>>++>+>+++>+>+++>>>++++>>+++>>++++>++++>+++++>+>++>>+++>>+++>+>+>++++>+>+++>+>+>++++>+>+++>+>+>++++>+>+++>>+++>>>>++++>>+++>>>++++>>+++>+>++++>++++>+++++>+++>+>+++>>>>++++++>++++>>++>++>++>++>++>++>++>++++>+>+++++>+++++>+++++>+++++>+++++>+++++>>+++++>+++>++>+>+++++>++++>>+++>>++++>+>++>+>++>>>>>+++>+>+>+>+++++>++++>>+++>>++++>+>++>+>++>>>>>+++>+>+>+>+++++>++++>>+++>>++++>+>++>+>++>>>>>+++>+>+>+>+++++>++++>>+++>>++++>+>+++++>+>++>++>++>>>>>+++>+>+>+>+++++>+++++>+++++>+++++>+++++>+++++>+++++>+++++>+++++>+++++>+++++>+++++>+++++>+++++>++++>>+++>>++++>+>++>++>+>++>>>>>+++>+>+>+>+++++>+++++>++++>>+++>>++++>+>+++++>+>++>++>++>++>++>++>++>>>>>+++>+>+>++>++>++>++>++++>+++++>+>+++++>+++++>+++++>+++++>+++++>+++++>>+++>++>+>++>++++>>+++>>++++>+>++>++>+>++>>>>>+++>+>+>+>+++++>+++++>++++>>+++>>++++>+>+++++>+>++>>>>>+++>+>+>+++++>+>++++>++>+++>+>++++>>+++>>++++++>+++>>>>++>+>+>+>+>+++++>++++>+>+++>>++++>+++++>++++>+>+>+++>>++++>+>++>++++>>+++>>>++++>+>+++>+>+>++++>>>++>++++>+>+>++++>+>+++>+>+>+++++>++++>>>+++>+>++++>>>>>++++>>+++>>++>+>+>++++>+>+++>+>+++>+>+++++>++++>>>+++>+>++++>>>>>++++>>+++>>+++++>+>+>++++>+>+++>+>+++>+>++>++>++++>+++++>>>++>+>+>+++>>>++++>>+++>>+++>+>+++>+>++++>+>+++>>+++++>+>+++>>+++++>++++>+>+>+++>>++++>+>++>++>++++>>+++>>>++++>+>+>+++>>++++>+>+>++>++++>+>+>++++>+>+++>>++++>+++++>+>+>++>>>+++>>+++++>+++++>++++>+>+>+++>>++++>++++>>+++>>++>+>+>++++>+>+++>+>+++>>++>++++>+>+>+++>>++++>++++>>+++>>+++++>+>+>++++>+>+++>+>+++>>++>++++>>+++>>+++>+++>+>+>++++>+>+++>>+++++>+++++>+>+++>>+++++>++++>+>+>+++>>++++>++++>>+++>>>+++++++>+>+>+>++++>+>+++>+>+++>>+++++>++++>+>+>+++>>++++>++++>>+++>>>+++++>+>+>+>++++>+>+++>+>+++>>+++++>++++>+>+>+++>>++++>++++>>+++>>>++++++>+>+>+>++++>+>+++>+>+>+>++++>+>+++>+>++++>+>+++>>++++>++++>>+++>>++++>>+++>>>>++++>>+++>>>++>+>+>+>++++>+>+++>+>+>+>++++>+>+++>+>++++>+>+++>>+++++>+++>>++++>>+++>>++++>>+++>>>++++>+>+++>+>+++>>+++++>++++>+>+>+++>>++++>++++>>+++>>>++>+>+>+>++++>+>+++>+>+++>>+++++>++++>+>+>+++>>++++>++++>>+++>>>>++++>>>+++>>++++>+>+>+>++++>+>+>+++>+>++>>>>++++>>>+++>>+++++>+++>>++++>+++++>+++>+>+>++>++++>+>++++>+++++>>>++>+>+>+++>+>+++>+>++++>+++++>>>++>+>+>+++>+>++++>+>+++>+>+++>>+++++>++++>+>+>+++>>++++>++++>>+++>>++>++>++++>+++++>+++++>>++++>+++++>+>+>++>>>+++>>+++>++>+>+>+++++>++++>++>++>+>+>+++>+>++++>+++++>>>>++++>>>+++>>++>+>+>+>++++>+>+>+++>+>+++>+>++++>+>+++>+>+++>+>++>++>++>++>++>++>++>++>>>++++>++>+>+>+++++>>>+++>>+++>>>++++>++++[<+]>[>[>]>[>]>++++++++++[-<++++++>]<++[<]<[<]<+>>-[[>]>[>]>+++++++[-<++++++>]<+[<]<[<]<+>>-]>]<--[>+<++++++]>++>[>]+++++[->+++<]>[>+++>+++>+++>++++++>++++++>+++>++++>++++[<]>-]>+>->>+>+++>-->>++[<]<<[<]<<[<]>[[[>]>>[>]>>[>]<[->>+<<]<[<]<<[<]<<[<]>-]>[>]>>[>]>>[>]>>[-<<+[<]<+>>[>]>]<<[[->+<]<]>>[>]>[[-<+>]>]<<[<]<<[<]<<[<]>]>>>[>]>>[>]<[[-]<]>>>,[>+++++++[<------>-]+<-[>]>[<+<+>>>>]<<<-[>]>[<+<+>>>>]<<<-[>]>[<+<+>>>>]<<<-[>]>[<-<+++>>>>]<<<--------------[>]>[<++<+>>>>]<<<--[>]>[<-<+++++++>>>>]<<++++[-<------>]+<+[>]>[<++<+>>>>]<<<--[>]>[<-<+>>>>]<<-<[+]<[>]>,]>>>+<<<<-[<]>[-[<<]>[<+[>]>>[<]<<[>>+[<<[<]<<-[>>]<[>>>>[>]>+<<[<]<]<-[>>]<[>>>>[>]>-<<[<]<]<++[->>+<<]>>[>]>]<]<[<]>-<]>-[<<]>[<++[>]>>[<<]>[<<+[<<[<]>[-<<+>>]>--[<<]>[[>]>+<<[<]<]>+[<<]>[[>]>-<<[<]<]>+[>]>]]<<[<]>--<]>-[<<]>[[>]>>.<<<[<]<]>-[<<]>[[>]>>-<<<[<]<]>-[<<]>[[>]>>,<<<[<]<<<[<]<[<]>[[>]>[>]>>>[>]>>+<<<[<]<<<[<]<[<]>-]>[>]>[>]>>[<]<]>-[<<]>[[>]>>+<<<[<]<]>-[<<]>[[>]>>>[>>]>[<<<[<<]<+>>>[>>]>-]>[-]<<+[<[->>+<<]<]<[->>+<<]<[<]<]>-[<<]>[[>]>++[-->[-<<+>>]>]+<<-[++<<]<[->>>[>>]>+<<<[<<]<]<[<]<]<++++++++>>[+<<->>]>]>>[]

Wypróbuj online! Dane wejściowe to prosty program cat (,[.,]), który wydrukuje sam program.

„Zwrot 0” jest definiowany poprzez zakończenie programu w komórce o wartości 0.

Bezbożna kombinacja dwóch programów, które napisałem w przeszłości, quine i self-tłumacza. Pierwsza sekcja to część quine, która pobiera dane i zapełnia taśmę generowaniem danych, a następnie kodem źródłowym. Następny jest interpreter, który bierze program i uruchamia go. Jest to prawie niezmieniona kopia normalnego interpretera, z tą różnicą, że zamiast brać dane bezpośrednio, pobiera dane od początku sekcji danych, ustawiając komórkę na 0, jeśli nie ma już danych wejściowych. Na koniec zakończ bieżącą komórkę programu i uruchom []. Jeśli zwrócona wartość to 0, mój program zakończy się na zero. Jeśli jest coś innego, uruchomi nieskończoną pętlę. Jeśli twój program działa wiecznie,mój program będzie działał wiecznie.

Jak to działa:

Część 1: Generowanie danych

->++>++++> ....... >+++++>>>+++>>+++>>>++++>+++

Ta część stanowi sekcję danych w quine i jest to zdecydowanie większość kodu o 3270 bajtach. Początek -jest znacznikiem początku danych. Każda z nich >+++reprezentuje znak kodu po tej sekcji.

Number of Pluses
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
> | < | + | ] | [ | - | , | . |

Część 2: Wygeneruj sekcję danych na podstawie danych

+[<+]>

[
    Add a right arrow
    >[>]>[>]>(10++++++++++)[-<(6++++++)>]<++[<]<[<]
    <+>>-
    Add the right amount of pluses
    [
        [>]>[>]>(7+++++++)[-<(6++++++)>]<+[<]<[<]<+>>-
    ]
    >
]
Add the beginning minus
<--[>+<++++++]>++

Wykorzystuje dane z części pierwszej, aby dodać znaki używane do generowania danych do sekcji kodu. Dodaje on >na końcu sekcji kodu i wartość tej komórki wiele plusów.

Część 3: Wygeneruj resztę kodu na podstawie danych

Initialises the 8 characters of brainfuck
>[>]+++++[->+++<]>[>+++>+++>+++>++++++>++++++>+++>++++>++++[<]>-]
>+>->>+>+++>-->>++[<]<<[<]<<[<]>

Tape looks like:
data 0 0 code 0 0 characters

Runs through the data destructively and adds the represented symbol to the code section
[
    [
        For each plus in this cell
            Shift the gap in the characters over one
        [>]>>[>]>>[>]<[->>+<<]
        <[<]<<[<]<<[<]>-
    ]
    Navigate to character
    >[>]>>[>]>>[>]>>
    Copy the character to the end of the code section
    [-<<+[<]<+>>[>]>]

    Shift the symbol section over one
    <<[[->+<]<]
    >>[>]>[[-<+>]>]

    Navigate to next byte of data
    <<[<]<<[<]<<[<]>
]

Remove characters
>>[>]>>[>]<[[-]<]

Niszczy sekcję danych i dodaje resztę kodu źródłowego do sekcji kodu

Część 4: Pobierz wprowadzony program

>>>,
[
    >(7+++++++)[<(6------)>-]+<-
    [>]>
    [plus <+<+>>>>]<<<
    -[>]>
    [comma <+<+>>>>]<<<
    -[>]>
    [minus <+<+>>>>]<<<
    -[>]>
    [dot <-<+++>>>>]<<<
    (14--------------)[>]>
    [left <++<+>>>>]<<<
    --[>]>
    [right <-<+++++++>>>>]<<
    (29++++[-<------>]+<+)
    [>]>
    [start loop <++<+>>>>]<<<
    --[>]>
    [end loop <-<+>>>>]<<
    -<[+]<[>]>,
]

Pobiera wprowadzony program. Usuwa postacie niemądre i reprezentuje każdą postać liczbą:

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
] | [ | . | - | , | + | > | < |

Reprezentuje koniec programu za pomocą 255.

Część 5: Interpretacja danych wejściowych

Initialise simulated tape
>>>+<<<<-

[<]>
[
    -[<<]>
    [end loop
        co 0 0 0 e:  _1 0 0 0 1 ?
        Check if current cell is one
        <+[>]>>[<]<<
        co 0 0 1 e _1: 0 0 !0 1
        or
        co 0 0 1 e _1 0: 0 0 1
        [ If current cell is one navigate to corresponding start loop
            Create counter
            >>+
            [
                co 0 0 de _1 0 c: !0 1
                checks if next instruction is an end loop
                <<[<]<<-
                [>>]<
                c !0 0: 0 de _1 0 c !0 1
                or
                c: 0 0  0 de _1 0 c !0 1
                [>>>>[>]>+<<[<]<] Add one to counter if it is
                checks if start loop
                <-[>>]<
                c !0 0: 0 de _1 0 c !0 1
                or
                c: 0 0  0 de _1 0 c !0 1
                [>>>>[>]>-<<[<]<] Subtract one from counter if it is
                c ? 0: 0 de _1 0 c !0 1
                Adds two to counteract checks and move to the next instruction
                <++[->>+<<]
                >>[>]>
                c 0 0 ode _1 0 c: !0 1
                End on the counter
                    If the counter is 0 then we have reached the corresponding bracket
            ]
            c 0 0 2 de _1 0 0: !0 1 0
            <
        ]
        c 0 0 1?2 de _1 0: 0 0 1 0
        Subtract one from current instruction
            This executes the start loop code next but that does nothing
        <[<]>-<
    ]
    >-[<<]>
    [start loop
        c 0 0 0 de:  _1 0 0 ? 1
        <++[>]>>[<<]>
        c 0 0 2 de _1 0 0 0 1:
        or
        c 0 0 2 de _1 0 0: !0 1
        [ If current cell is 0 navigate to corresponding end loop
            Initialise counter
            <<+
            c 0 0 ode _1 0 c: 0 1
            [ While counter is not 0
                Transfer current instruction over (first instruction is guaranteed to be start loop)
                <<[<]>[-<<+>>]>
                co 0 0 de _1 0 c: 0 1
                Check if start loop
                --[<<]>
                co 0 0: !0 e _1 0 c 0 1
                or
                co 0 0 0 e _1 0 c 0 1
                [[>]>+<<[<]<] Add one to counter if so
                checks if end loop
                >+[<<]>
                co 0 0: !0 e _1 0 c 0 1
                or
                co 0 0 0 e:  _1 0 c 0 1
                [[>]>-<<[<]<] Subtract one from counter if so
                Add one to counteract checks and navigate to counter
                >+[>]>
                co 0 0 de _1 0 c: 0 1
                End on counter
                    If counter is 0 then we have reached the corresponding end loop
            ]
            co 0 1 e _1 0 0: 0 1
        ]
        co 0 0 2?1 e _1 0 0: ? 1
        Subtract two from the current instruction to bring it back up to the right value
        <<[<]>--<
    ]
    3 of these are pretty self explanatory
    Navigate to the current cell and execute the instruction on it
    >-[<<]>
    [output
        [>]>>.<<<[<]<
    ]
    >-[<<]>
    [minus
        [>]>>-<<<[<]<
    ]
    >-[<<]>
    [input
        Reset current cell
        [>]>>, (no more input so this is set to 0)
        co 0 0 0 e:  _1 0 0 0: 1 b 1 a 0 d 1 e 1 f
        Navigate to start of code section
        <<<[<]<<<[<]<[<]>
        d: ata 0 co 0 0 0 e _1 0 0 0 1 b
        or
        0: co 0 0 0 e _1
        Transfer next instruction to current cell
        [[>]>[>]>>>[>]>>+<<<[<]<<<[<]<[<]>-]
        0: ata 0 co 0 0 0 e _1 0 0 d 1 b
        or
        0: co 0 0 0 e _1
        Navigate back to the normal spot
        >[>]>[>]>>[<]<
    ]
    >-[<<]>
    [plus
        [>]>>+<<<[<]<
    ]
    >-[<<]>
    [right
        Simulated tape looks like:
            a b c: d e f
        co 0 0 0 e:  _1 0 0 c 1 b 1 a 0 d 1 e 1 f
        Navigate to value of cell to the right
        [>]>>>[>>]>
        co 0 0 0 e _1 0 0 c 1 b 1 a 0 d: 1 e 1 f
        Transfer it to temporary cell
        [<<<[<<]<+>>>[>>]>-]
        co 0 0 0 e _1 d 0 c 1 b 1 a 0 0: 1 e 1 f
        Pop extra marker if it exists from the right cells and add one to the left
        >[-]<<+
        co 0 0 0 e _1 d 0 c 1 b 1 a 1: 0 0 e 1 f
        Transfer all left cells over 2 cells
        [<[->>+<<]<]<[->>+<<]
        co 0 0 0 e _1 0: 0 d 1 c 1 b 1: a 0 e 1 f
        Navigate back to normal spot
        <[<]<
    ]
    >-[<<]>
    [left
        Simulated tape looks like:
            a b c: d e f
        co 0 0 0: e _1 0 0 c 1 b 1 a 0 d 1 e 1 f
        Add temporary marker
        [>]>++
        co 0 0 0 e _1 0 2: c 1 b 1 a 0 d 1 e 1 f
        Remove temporary marker and transfer all left cells over two
        [-->[-<<+>>]>]
        co 0 0 0 e _1 c 0 b _1 a _1 0 0: d 1 e 1 f
        Add marker to right cells remove marker from left cells and reset left cell's markers
        +<<-[++<<]<
        co 0 0 0 e _1 c: 0 b 1 a 0 0 1 d 1 e 1 f
        Transfer current cell to to right cells
        [->>>[>>]>+<<<[<<]<]
        co 0 0 0 e _1 0: 0 b 1 a 0 c 1 d 1 e 1 f
        Navigate back to normal spot
        <[<]<
    ]
    Add 8 to reverse checks
    <(8++++++++)>>

    Execute next instruction
    [+<<->>]>
]

Interpretuje program. Jedyną różnicą od normalnej jest to, że dane wejściowe są pobierane od początku sekcji kodu zamiast danych wejściowych.

Część 6: Zatrzymaj się, jeśli zwrot nie będzie wynosił 0

>>[]

Przejdź do końcowej komórki programu i uruchom nieskończoną pętlę, jeśli wartością zwracaną nie jest 0. Jeśli jest to 0, wyjdź z pętli i zakończ na tym samym 0.

Wejścia testowe:

Zawsze zwraca 0 (zatrzymuje i zwraca 0)

(empty program)

Zawsze zwraca 1 (działa wiecznie)

+

Zwraca wszystkie dane dodane razem, mod 256 (zwraca 211, więc działa wiecznie)

,[[->+<],]>

Zwraca 0, jeśli ostatnie dwa znaki kodu są nieskończoną pętlą ( []) ( twój program zwraca 0, gdy otrzyma mój program , dlatego mój program zatrzymuje się)

,[>,]>(9+++++++++)[-<(10++++++++++)>]<[-<-<->>]+<---[[-]>[-]<]<-[[-]>>[-]<<]>+>[-<->]<    

Ciekawostka dla tych, którzy wciąż czytają

Jeśli dane wejściowe dla tego programu są kodem źródłowym tego programu, zacznie się on cyklicznie powtarzać, wielokrotnie tworząc self-interpretery, które uruchamiają ten program, a następnie ponownie nadaje mu ten sam program. To daje mi kilka ciekawych pomysłów na tworzenie rzeczywistych programów rekurencyjnych w pieprzeniu mózgu. Zamiast sprawdzania wartości zwracanej i rozpoczynania nieskończonej pętli, jak w tym pytaniu, wartość zwracaną można zapisać i wykorzystać. Prostym przykładem może być program czynnikowy

If cell1 == 0:
    Get input into cell1
If cell1 == 1 or cell1 == 0:
    Return 1
Else:
    Initialise self-interpreter-quine function
    Pass cell1-1 into cell1 of the function
    Run function
    Multiply cell1 by the return value
    Return cell1

Oczywiście jest to całkowicie szalony sposób kodowania pieprzenia mózgów, biorąc pod uwagę, że uruchamianie rekurencyjnych interpreterów zwiększy wykładniczo czas działania.

Jo King
źródło
Tak! BTW, jeśli chcesz zagrać w golfa, biorąc pod uwagę konwencję dotyczącą powrotu, myślę, że możesz rzucić wsparcie .. Chociaż ponieważ nie jest to już kwestia golfa, obsługa całego języka może być bardziej imponująca.
Ørjan Johansen
@ ØrjanJohansen, prawdopodobnie mogę zagrać w golfa około tysiąca bajtów wyłączając samą metodę generowania danych. Ponadto interpreter nie jest najmniejszy, jaki mogłem napisać, ponieważ obsługuje komórki ujemne.
Jo King
Wygląda na to, że powinien wygrać nagrodę, ale chcę poświęcić trochę czasu, aby to zrozumieć, nie będąc ekspertem od BF. Czy możesz mnie pingować, jeśli nie odezwiesz się w następnym tygodniu?
Nathaniel
1
Potwierdzam, że jest to zgodne ze specyfikacją, o ile mogę powiedzieć. Nagroda powinna wkrótce nadejść do ciebie. (Wystąpiło opóźnienie, zanim system pozwoli mi je przyznać.) Dziękuję za odpowiedź, bardzo ją doceniam.
Nathaniel
1
Możesz być zainteresowany Muriel .
PyRulez