Обнаружение бесконечного цикла в программе brainfuck
Я написал простой интерпретатор 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
и, следовательно, код работает и продолжается. Однако наивная проверка числа "+" и "-" в ячейке 1 говорит о том, что число "больше" больше, поэтому не обнаружит бесконечный цикл.
Кто-нибудь может придумать хороший алгоритм для обнаружения бесконечных циклов, учитывая произвольную вложенность произвольного числа циклов в BF?
РЕДАКТИРОВАТЬ: я знаю, что проблема остановки вообще неразрешима, но я не был уверен, что не существует исключений особых случаев. Например, возможно, 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
9 ответов
Когда я использовал линейное генетическое программирование, я просто использовал верхнюю границу для количества инструкций, которые одной программе было разрешено выполнять за время ее существования. Я думаю, что это разумно по двум причинам: я все равно не могу решить проблему остановки, а программы, которые требуют слишком много времени для вычислений, в любом случае не стоят больше времени.
Алан Тьюринг хотел бы поговорить с вами.
Допустим, вы написали программу, которая могла бы определить, будет ли эта программа работать в бесконечном цикле. Скажем для простоты, что эта программа была написана на языке brainfuck для анализа программ brainfuck (хотя это не является предварительным условием следующего доказательства, потому что любой язык может эмулировать brainfuck, а brainfuck может эмулировать любой язык).
Теперь предположим, что вы расширяете программу проверки, чтобы создать новую программу. Эта новая программа завершается немедленно, когда ее вход повторяется бесконечно, и возвращается навсегда, когда ее вход завершается в какой-то момент.
Если вы введете эту новую программу в себя, каковы будут результаты?
Если эта программа зацикливается навсегда при запуске, то, по собственному определению, она должна немедленно завершиться при запуске с самим собой в качестве ввода. И наоборот. Программа проверки не может существовать, потому что само ее существование подразумевает противоречие.
Как было упомянуто ранее, вы по существу решаете известную проблему остановки: http://en.wikipedia.org/wiki/Halting_problem
Издание Я хочу пояснить, что это опровержение не мое, а по сути известное опровержение, которое Алан Тьюринг дал в 1936 году.
Состояние в bf представляет собой единый массив символов.
На вашем месте я бы взял хеш состояния интерпретатора bf в каждом "]" (или один раз в rand(1, 100) "]"s*) и утверждал, что набор хешей уникален.
Во второй (или более) раз, когда я вижу определенный хэш, я сохраняю все состояние в стороне.
В третий (или более) раз я вижу определенный хэш, я сравниваю все состояние с сохраненным (и) и, если есть совпадение, я ухожу.
При каждой входной команде ('.', IIRC) я сбрасываю свои сохраненные состояния и список хэшей.
Оптимизация - это хэширование только той части состояния, которая была затронута.
Я не решил проблему остановки - я обнаружил бесконечные циклы во время работы программы.
* Рэнд должен сделать проверку независимой от периода цикла
Бесконечный цикл не может быть обнаружен, но вы можете определить, занимает ли программа слишком много времени.
Реализуйте тайм-аут, увеличивая счетчик каждый раз, когда вы запускаете команду (например, <, >, +, -). Когда счетчик достигает некоторого большого числа, которое вы устанавливаете наблюдением, вы можете сказать, что выполнение вашей программы занимает очень много времени. Для вашей цели "очень длинное" и бесконечное - это достаточно хорошее приближение.
Как уже упоминалось, это проблема остановки. Но в вашем случае может быть решение: проблема с остановкой, которая рассматривается, касается машины Тьюринга, которая имеет неограниченную память.
Если вы знаете, что у вас есть верхний предел памяти (например, вы знаете, что не используете более 10 ячеек памяти), вы можете запустить свою программу и остановить ее. Идея состоит в том, что пространство вычислений ограничивает время вычислений (поскольку вы не можете записать более одной ячейки за один шаг). После того, как вы выполнили столько шагов, сколько можете иметь различные конфигурации памяти, вы можете сломать. Например, если у вас есть 3 ячейки с 256 условиями, вы можете иметь не более 3^256 разных состояний, и поэтому вы можете остановиться после выполнения такого количества шагов. Но будьте осторожны, есть неявные ячейки, такие как указатель инструкций и регистры. Вы делаете это еще короче, если вы сохраняете каждую конфигурацию состояния и, как только вы обнаруживаете конфигурацию, которая у вас уже была, вы получаете бесконечный цикл. Этот подход определенно намного лучше во время выполнения, но для этого требуется гораздо больше места (здесь может быть уместно хешировать конфигурации).
Это не проблема остановки, однако все же нецелесообразно пытаться обнаружить остановку даже в такой ограниченной машине, как машина с 1000 ячейками BF.
Рассмотрим эту программу:
+[->[>]+<[-<]+]
Эта программа не будет повторяться до тех пор, пока не заполнит всю память, что всего на 1000 ячеек займет около 10^300 лет.
Если я правильно помню, остановка доказательства проблемы была верна только для некоторого крайнего случая, который включал в себя самостоятельную ссылку. Тем не менее, все еще тривиально показать практический пример того, почему вы не можете сделать детектор с бесконечной петлей.
Рассмотрим последнюю теорему Ферма. Легко создать программу, которая перебирает каждое число (или в данном случае 3 числа) и определяет, является ли это контрпримером к теореме. Если это так, он останавливается, в противном случае он продолжается.
Поэтому, если у вас есть детектор с бесконечным циклом, он сможет доказать эту теорему и многие другие (возможно, все остальные, если они могут быть сведены к поиску контрпримеров).
В общем, любая программа, которая включает в себя итерацию по числам и остановку только при некотором условии, потребует проверки общей теоремы, чтобы доказать, может ли это условие когда-либо выполняться. И это самый простой случай зацикливания.
Вдобавок ко всему (и я могу ошибаться) я бы подумал, что было бы немного трудно определить, есть ли в программе бесконечный цикл без фактического выполнения самой программы.
Поскольку условное выполнение частей программы зависит от состояния выполнения программы, будет трудно узнать конкретное состояние программы без фактического выполнения программы.
Если вам не требуется, чтобы программа с бесконечным циклом выполнялась, вы можете попробовать использовать счетчик "инструкции выполнены" и выполнять только конечное количество инструкций. Таким образом, если программа имеет бесконечный цикл, интерпретатор может завершить программу, которая застряла в бесконечном цикле.