Я написал простой интерпретатор brainfuck на языке сценариев MATLAB. В него загружаются случайные программы bf для выполнения (как часть проекта генетического алгоритма). Проблема, с которой я сталкиваюсь, заключается в том, что в программе оказывается бесконечный цикл в значительном количестве случаев, и, следовательно, GA застревает в точке.
Итак, мне нужен механизм для обнаружения бесконечных циклов и предотвращения выполнения этого кода in 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
[]зацикливается бесконечно, только если значение под указателем не0. Да, это было бы бесполезно, если бы оно использовалось в точке, где значение указателя может быть только0(например, в начале программы), но это не обязательно ошибка. - person Skilldrick schedule 17.05.2010Stannett, M. 1990. X-Machines and the Halting Problem: Building a Super-Turing Machine. Formal Aspects of Computing, 2, 331-341.? - person DrBeco schedule 06.04.2011Call bfexec recursively with subprog. Он может работать вечно, если найдет бесконечный цикл. Нет известного решения для этой проблемы с остановкой. - person DrBeco schedule 06.04.2011