Я написал простой 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 мог бы функционировать как машина Супер-Тьюринга, способная определить остановку программы 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