Является ли использование статического анализа байт-кода для определения всех возможных путей с помощью данного метода вариантом попытки решить проблему остановки?

Question

Можно ли определить все возможные пути выполнения, прочитав байт-код данного метода, или это будет эквивалентно попытке решить проблему остановки?Если это не может быть сведено к проблеме остановки, то как далеко я могу пойти со статическим анализом, не переступая границу попытки решить проблему остановки?

Смежный вопрос: "Поиск всего кодав данном двоичном коде эквивалентно проблеме Остановки. "Действительно?

Answer 1

Да, это легко эквивалентно решению проблемы остановки.Рассмотрим следующий оператор if:

if (TuringMachine (x)) then goto fred;

OK, возможно ли действительно перейти к fred?Вы можете ответить на этот вопрос, только если сможете проанализировать машину Тьюринга.Для этого есть эквивалентный набор байт-кодов.

Теперь, если единственная проблема состоит в том, чтобы определить все вероятные пути, и вам все равно, если вы получите несколько ложных срабатываний, ответ таков:Нет. Рассмотрим следующую программу:

if (false) then x else y ;

Возможные пути: eval (false); do x и eval (false); do y - полное перечисление.

Вы должны обработатьЗацикливается специально, как ноль, одна, две или некоторое максимальное ограниченное число итераций, если вы хотите вычислимый ответ.Если цикл может повторяться вечно, некоторые из ваших путей будут бесконечно длинными, и вы не сможете сообщить о них с помощью алгоритма и конечного времени: - {