Можно ли определить, удалось ли получить доступ к массиву памяти за пределами программы Brainf ** k?

Question

Я написал собственный переводчик BF в Assembly, и теперь я пишу компилятор BF на Java, который компилируется в код Assembly.

Я хотел реализовать небольшую приятную функцию, которая обнаружила, что массив ячеек памяти вышел за пределы. Традиционным ограничением для массива является указание индекса в [0, 30000), в противном случае обычно используется [0, inf). Другой вариант заключается в том, что память обернута вокруг, так что в первом случае это может означать, что доступ к индексу 30000 означает доступ к индексу 0.

В моем компиляторе это обнаружение будет выполнено на этапе семантического анализа традиционного компилятора, поэтому мы уже получили наш AST (абстрактное синтаксическое дерево) на этапе анализа синтаксиса.

После попытки создать конструкцию для этого на некоторое время я нашел Detecting infinite loop in brainfuck program, а также страницу Википедии BF. Я узнал, что программа BF с массивом памяти [0, inf) напоминает машину Тьюринга.

Таким образом, мой вопрос заключается в том, что касается как корпусов [0, max), так и [0, inf), можно ли обнаружить, что указатель памяти опускается ниже нуля, а в первом случае ниже max? Очевидно, не завершаясь в бесконечном цикле, проверяя его, и я предпочел бы избежать установки максимального времени выполнения.

Вопрос о бонусе: Можно ли определить количество циклов петли [...]?

Answer 1

BF обладает способностью к Тьюрингу. Если вы используете его для вычисления индекса, то вы не можете определить вообще, если индекс имеет определенное значение (например, 30001) из-за проблемы с остановкой. Так что в общем случае вы не можете обнаружить вне доступа. Однако вы можете обнаружить это для многих отдельных программ; поэтому статические анализаторы строятся и используются, несмотря на то, что они теоретически бесполезны.

Что касается количества циклов отключения: Конструкция цикла работает в зависимости от того, является ли переменная нулевой или нет. BF, являющийся способностью Тьюринга, означает, что в общем случае вы не можете знать, равна ли переменная нулевой или нет в какой-либо конкретной точке. Следствием этого является то, что вы не можете знать количество раз, когда работает контур цикла. Опять же, вы можете понять это для многих отдельных программ.

Для некоторых программ с простыми корпусами вы можете легко реализовать свои проверки. В общем, для проведения такого рода статических анализов требуется довольно много механизмов.