Смути мои попытки решить проблему остановки

31

Пожалуйста, обратите внимание: по своей природе спецификации для этой задачи трудно понять. Это, вероятно, требует, по крайней мере, курса новичка в теории вычислимости или эквивалентного базового чтения. Кроме того, сама задача довольно сложная. Ответ на него потребует написания полного переводчика для некоторого подмножества вашего языка по вашему выбору, и не только это, но и переводчик должен быть в форме чего-то похожего на квинну. Если ваш ответ не делает всего этого, почти наверняка не будет соответствовать спецификации.

Вам не нужно решать проблему остановки (даже частично), чтобы решить эту проблему. Тем не менее, вы почти наверняка сделать нужно написать переводчик (язык , который вы используете, написанный на одном языке он интерпретирует), хотя это не обязательно должно быть законченным продукт . Именно это делает это интересным испытанием.

Я обещал присудить награду в 500 баллов за первый ответ, который соответствует спецификации, и это будет за ответ BF Джо Кинга .

Соревнование

Грубая, упрощенная версия доказательства Алана Тьюринга о неразрешимости проблемы остановки выглядит примерно так:

Предположим, я написал программу F, предназначенную для решения программы остановки. То есть, Fпринимает исходный код другой программы в качестве входных данных и F(G)должен возвращать, 1если Gостанавливается, и в 0противном случае.

Но если я дам вам свою программу, Fвы можете создать другую программу H, которая будет запускать мою программу в Hкачестве входных данных. Если F(H)возвращается, 0то Hвозвращается 0, но в противном случае он намеренно уходит в бесконечный цикл. Это приводит к парадоксу, и мы должны заключить, что Fне можем решить проблему остановки в конце концов.

Ваша задача - написать программу H, но с изюминкой: я не собираюсь давать вам свою программу. Вместо этого ваша программа получит исходный код моей программы в качестве входных данных. То есть:

  • Ваша программа получит мою программу в виде ввода в виде исходного кода. (Например, в виде файла или ввода в командной строке, подробности зависят от вас.)

  • Моя программа будет написана на том же языке, что и ваша программа, и также принимает ввод в виде строки исходного кода.

  • Если моя программа возвращается, 0когда ваша программа вводится как ввод, ваша программа должна останавливаться (и возвращаться 0), когда моя программа вводится как ввод. (Точное значение слова «возвращение 0» зависит от вас.)

  • если моя программа не останавливается, или если она возвращает что-либо кроме того, 0что передается вашей программе в качестве входных данных, ваша программа должна работать бесконечно долго.

Суть в том, что просто чтобы сделать это действительно намного сложнее, вы должны соблюдать следующие правила:

  1. Вы не можете использовать какую-либо встроенную функцию execили eval-типа.

  2. Вы не можете использовать любые "читерские" методы, чтобы получить исходный код своей программы. (Например, вы не можете сказать «сохраните это в файле под названием« программа »», а затем включите open(program)в свою программу ».

Это означает, что ваша программа должна быть своего рода сумасшедшим супер-квинем, который может не только воспроизводить свой собственный исходный код в виде строки, но и способен правильно анализировать и интерпретировать язык, на котором написан.

Чтобы сделать его немного менее безумно сложным, вы можете использовать только (полное по Тьюрингу) подмножество выбранного вами языка. Поэтому, если ваша программа написана на Python и будет работать только в том случае, если моя программа содержит только ifs и whileциклы, а также базовые строковые операции, то это нормально, если ваша программа тоже использует только эти вещи. (Это означает, что вам не нужно беспокоиться о реализации всей стандартной библиотеки выбранного языка!) Однако ваша программа действительно должна работать - вы не можете просто создать свой собственный язык.

Это , поэтому победит ответ с наибольшим количеством голосов. Тем не менее, как уже упоминалось выше, это просто серьезная задача - просто выполнить спецификацию, поэтому я присуждаю награду в 500 баллов за первый ответ, который отвечает моим требованиям.

пожалуйста, обратите внимание: без сомнения, есть много способов, которыми вы можете «обмануть» в этом задании, учитывая точную формулировку, которую я использовал. Тем не менее, я действительно надеюсь на ответы, которые входят в дух вопроса. Задача, как задумано, очень сложна, но возможна, и я очень надеюсь увидеть ее подлинные решения. Я не буду назначать награду за ответ, который кажется мне обманчивым.


Примечание: этот вызов изначально был объявлен как , но он был закрыт в 2016 году из-за отсутствия «объективного критерия выигрыша», и я изменил его на , чтобы открыть его снова. Тем не менее, я обнаружил, что по состоянию на январь 2018 года фактически не запрещены для PPCG (с учетом того, что это самая последняя мета-дискуссия), поэтому закрытие его в первую очередь было против политики сайта. Я понимаю, что попконы не популярны в наши дни, но это старая проблема, и ее природа делает ее действительно непригодной для игры в система баллов. Если кто-то по-прежнему твердо убежден в том, что этого нельзя допустить, тогда давайте проведем мета-обсуждение, прежде чем начнут собираться близкие голоса. Наконец, в связи с тем, что кто-то потратил последний год, пытаясь сыграть в гольф свое решение, будьте уверены, что он будет таким же конкурентоспособным в этом испытании и таким же достойным награды, как это было бы в версия.

Натаниель
источник
1
Возвращаясь, вы имеете в виду код выхода или стандартный вывод? Или оба приемлемы?
PlasmaPower
Оба приемлемы.
Натаниэль
@ Натаниэль Я так понимаю, было бы незаконно экспортировать полученный код Fв файл и importзаписывать его? ; 3
cjfaure
1
Мне очень нравится этот вопрос, но его трудно понять. Если у кого-то еще возникли проблемы, эти два слайда (в Java psuedocode) облегчили мне понимание: imgur.com/a/NRmyO
Harry
1
Вы упоминаете «дух вопроса» и «подлинные решения». Что ты имеешь в виду? Должны ли мы сами писать переводчик для нашего языка? Я не могу представить другого способа сделать это.
KSFT

Ответы:

23

Brainfuck , 6013 4877 4376 байт

Изменить: -1136 байт. Перешли на лучший способ генерации данных для квин

Edit2: -501 байт. Пересмотрел мой самоинтерпретатор и сократил пару сотен байтов

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

Попробуйте онлайн! Здесь вводится простая программа cat (,[.,]), которая печатает саму программу.

«Возвращение 0» определяется завершением программы в ячейке со значением 0.

Нечестивая комбинация двух программ, которые я написал в прошлом, quine и самоинтерпретатора. Первый раздел - это часть quine, которая берет данные и заполняет ленту генерацией данных, за которой следует исходный код. Далее идет самоинтерпретатор, который берет вашу программу и запускает ее. Это в значительной степени неизмененная копия обычного самостоятельного интерпретатора, за исключением того, что вместо непосредственного ввода данных он получает входные данные в начале раздела данных, устанавливая ячейку в 0, если входных данных больше нет. Наконец, завершите текущую ячейку вашей программы и запустите []. Если возвращаемое значение было 0, моя программа завершится на нуле. Если это что-то еще, он будет запускать бесконечный цикл. Если ваша программа работает вечно,моя программа будет работать вечно.

Как это работает:

Часть 1: Генерация данных

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

Эта часть составляет раздел данных quine и на данный момент составляет большую часть кода в 3270 байтов. Начало -является маркером начала данных. Каждый >+++представляет символ кода после этого раздела.

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

Часть 2. Создание раздела данных с использованием данных

+[<+]>

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

При этом используются данные из первой части для добавления символов, которые используются для генерации данных, в раздел кода. Это добавляет >к концу раздела кода и значение этой ячейки много плюсов.

Часть 3: Генерация остальной части кода с использованием данных

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
>>[>]>>[>]<[[-]<]

Уничтожает раздел данных и добавляет оставшуюся часть исходного кода в раздел кода

Часть 4: Получить введенную программу

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

Получает введенную программу. Удаляет не-мозговые символы и представляет каждого персонажа числом:

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

Представляет конец программы с 255.

Часть 5: Интерпретация ввода

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
    [+<<->>]>
]

Интерпретирует программу. Единственное отличие от обычного состоит в том, что ввод берется из начала раздела кода, а не из ввода.

Часть 6: остановка, если возврат не равен 0

>>[]

Перейдите к конечной ячейке вашей программы и запустите бесконечный цикл, если возвращаемое значение не равно 0. Если оно равно 0, выйдите из цикла и закончите на том же 0.

Тестовые входы:

Всегда возвращает 0 (останавливается и возвращает 0)

(empty program)

Всегда возвращает 1 (работает вечно)

+

Возвращает все входные данные, добавленные вместе, мод 256 (возвращает 211, поэтому он работает вечно)

,[[->+<],]>

Возвращает 0, если последние два символа кода представляют собой бесконечный цикл ( []) ( ваша программа возвращает 0, когда передается моя программа , поэтому моя программа останавливается)

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

Интересный факт для тех, кто все еще читает

Если исходные данные для этой программы являются исходным кодом этой программы, то она начнет повторяться, многократно создавая интерпретаторы, которые запускают эту программу, а затем снова передают ей ту же самую программу. Это дает мне некоторые интересные идеи по созданию реальных рекурсивных программ в Brainfuck. Вместо проверки возвращаемого значения и запуска бесконечного цикла, как в этом вопросе, возвращаемое значение может быть сохранено и обработано. Простым примером будет факториальная программа, которая идет

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

Конечно, это совершенно безумный способ кодирования мозговых ошибок, учитывая, что выполнение рекурсивных самоинтерпретаторов увеличит время выполнения в геометрической прогрессии.

Джо Кинг
источник
Ура! Кстати, если вы хотите сыграть в гольф, учитывая ваше возвращение, я думаю, вы можете отказаться от поддержки .. Хотя этот вопрос больше не является вопросом игры в гольф, поддержка всего языка может быть более впечатляющей.
Орджан Йохансен
@ ØrjanJohansen, я, вероятно, могу сыграть в гольф примерно тысячу байтов, переключившись на другой метод генерации данных. Кроме того, самоинтерпретатор не самый маленький, который я мог написать, поскольку он поддерживает отрицательные ячейки.
Джо Кинг
Похоже, это должно выиграть награду, но я хочу не торопиться, чтобы понять это, а не быть экспертом BF сам. Не могли бы вы пинговать меня, если не услышите ответ на следующей неделе?
Натаниэль
1
Я подтверждаю, что это соответствует спецификации, насколько я могу судить. Щедрость должна скоро добраться до вас. (Существует задержка, прежде чем система позволит мне наградить ее.) Спасибо за ответ, это очень ценится.
Натаниэль
1
Вы можете быть заинтересованы в Мюриэль .
PyRulez