Обнаружение бесконечного цикла в программе brainfuck

Question

Я написал простой интерпретатор brainfuck в языке скриптов MATLAB. Он управляется случайными программами bf для выполнения (как часть проекта генетического алгоритма). Проблема, с которой я сталкиваюсь, заключается в том, что программа оказывается бесконечной петлей в большом числе случаев, и, следовательно, GA застревает в точке.
Итак, мне нужен механизм для обнаружения бесконечных циклов и избежать выполнения этого кода в bf.
Очевидный (тривиальный) случай, когда у меня есть

[] 

я могу обнаружить это и отказаться от выполнения этой программы.
Для нетривиальных случаев я понял, что основная идея: определить, как одна итерация цикла меняет текущую ячейку. Если изменение отрицательное, мы в конечном итоге достигнем 0, поэтому это конечная петля. В противном случае, если изменение неотрицательно, это бесконечный цикл.
Реализация это легко для случая одного цикла, но с вложенными циклами он становится очень сложным. Так, например, (в дальнейшем (1) относится к содержимому ячейки 1 и т.д.)

++++ Put 4 in 1st cell (1) 
>+++ Put 3 in (2) 
<[ While((1) is non zero) 
    -- Decrease (1) by 2 
    >[ While((2) is non zero) 
     - Decrement (2) 
     <+ Increment (1) 
    >] 
    (2) would be 0 at this point 
    +++ Increase (2) by 3 making (2) = 3 
<] (1) was decreased by 2 and then increased by 3, so net effect is increment 

и, следовательно, код работает и на. Однако наивная проверка количества + и s'-файлов, сделанных на ячейке 1, скажет, что число -'s больше, поэтому не будет обнаруживать бесконечный цикл.
Может ли кто-нибудь подумать о хорошем алгоритме обнаружения бесконечных циклов, учитывая произвольное вложение произвольного числа циклов в bf?

EDIT: Я знаю, что проблема с остановкой в ​​общем случае неразрешима, но я не был уверен, не было ли особых случаев исключения. Как, может быть, Matlab может функционировать как машина Super Turing, способная определить остановку программы bf. Я мог бы быть ужасно ошибаюсь, но если так, я хотел бы точно знать, как и почему.

ВТОРОЙ РЕДАКТОР: Я написал то, что я называю бесконечным детектором цикла. Вероятно, он пропускает некоторые крайние случаи (или, что менее вероятно, каким-то образом избегает лап мистера Тьюринга), но, похоже, работает для меня на данный момент. В псевдокоде формы, здесь идет:

subroutine bfexec(bfprogram) 
begin 
    Looping through the bfprogram, 
     If(current character is '[') 
      Find the corresponding ']' 
      Store the code between the two brackets in, say, 'subprog' 
      Save the value of the current cell in oldval 
      Call bfexec recursively with subprog 
      Save the value of the current cell in newval 
      If(newval >= oldval) 
       Raise an 'infinite loop' error and exit 
      EndIf 
     /* Do other character's processings */ 
     EndIf 
    EndLoop 
end 

Answer 1

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

Answer 2

Алан Тьюринг хотел бы поговорить с вами.

http://en.wikipedia.org/wiki/Halting_problem

Answer 3

Off верхней части моей головы (я могу ошибаться), я думаю, что это было бы немного трудно определить, есть ли или нет программа бесконечный цикл без фактического выполнения самой программы ,

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

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

Answer 4

Предположим, вы записали программу, которая могла бы определить, будет ли эта программа работать в бесконечном цикле. Скажем, ради простоты, что эта программа была написана в мозгу, чтобы анализировать программы мозгового искусства (хотя это не является предварительным условием следующего доказательства, потому что любой язык может эмулировать мозговое увлечение и brainfuck может подражать любому языку).

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

Если вы введете эту новую программу в себя, какими будут результаты?

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

Как уже упоминалось ранее, вы существенно переформулировав знаменитую останавливая проблему: http://en.wikipedia.org/wiki/Halting_problem

Ed. Я хочу пояснить, что вышеупомянутое опровержение не является моим собственным, но по существу является знаменитым доказательством того, что Алан Тьюринг дал еще в 1936 году.

Answer 5

Как уже упоминалось, это проблема с остановкой. Но в вашем случае может быть решение: проблема с остановкой рассматривается в отношении машины Тьюринга, которая имеет неограниченную память.

Если вы знаете, что у вас есть верхний предел памяти (например, вы знаете, что не используете более 10 ячеек памяти), вы можете выполнить свою программу и остановить ее. Идея состоит в том, что вычислительное пространство ограничивает время вычисления (поскольку вы не можете писать более одной ячейки за один шаг). После того, как вы выполнили столько шагов, сколько сможете иметь разные конфигурации памяти, вы можете сломаться. Например. если у вас есть 3 ячейки, с 256 условиями, вы можете иметь не более 3^256 разных состояний, и поэтому вы можете остановиться после выполнения этого множества шагов. Но будьте осторожны, есть неявные ячейки, такие как указатель инструкции и регистры. Вы делаете это еще короче, если вы сохраняете каждую конфигурацию состояния, и как только вы обнаружите тот, который у вас уже есть, у вас есть бесконечный цикл. Этот подход определенно намного лучше во время выполнения, но для этого требуется гораздо больше места (здесь он может быть подходящим для хэш-конфигураций).

Answer 6

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

Внедрение тайм-аут на увеличение счетчика каждый раз при запуске команды (например, <, >, +, -). Когда счетчик достигает некоторого большого количества, которое вы установили по наблюдению, вы можете сказать, что для выполнения вашей программы требуется очень много времени. Для вашей цели «очень долго» и бесконечно - достаточно хорошее приближение.

Answer 7

Состояние в bf - это единый массив символов.

Если бы я был вами, я бы взял хэш состояния интерпретатора bf на каждом "]" (или один раз в rand (1, 100) "]" s *) и утвердил, что набор хэшей уникален ,

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

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

В каждой команде ввода ('.', IIRC) я возвращаю сохраненные состояния и список хэшей.

Оптимизация заключается только в том, что часть состояния была затронута.

Я не решил проблему с остановкой - я обнаруживаю бесконечные циклы во время работы программы.

* Ранд, чтобы сделать чек независимо от периода петли

Answer 8

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

Рассмотрим эту программу:

+[->[>]+<[-<]+] 

Эта программа не будет повторяться до тех пор, пока не заполнила копирование всей памяти, которая всего за 1000 ячеек будет принимать около 10^300 лет.

Answer 9

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

Рассмотрите Fermat's Last Theorem. Легко создать программу, которая выполняет итерацию через каждое число (или в этом случае 3 числа) и определяет, является ли это контрпримером к теореме. Если он останавливается, в противном случае он продолжается.

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

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