Я написал простой brainfuck интерпретатор в языке MATLAB script. Он управляется случайными программами 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?
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 processings */
EndIf
EndLoop
end
