patternMinor
What is the Name of the Problem or Technique of Determining if a Line in a Program Will Execute
Viewed 0 times
techniqueproblemthedeterminingwhatlineprogramwillnameexecute
Problem
If I were to pose the question: "Given a program $P$ containing statement $X$, will $X$ be executed (given enough runs with all possible inputs)?"
This strikes me of being a relative of the Halting Problem, but I just don't know the taxonomy here.
What is the name of this problem, or does it not have a name because it is solved/uninteresting?
This strikes me of being a relative of the Halting Problem, but I just don't know the taxonomy here.
What is the name of this problem, or does it not have a name because it is solved/uninteresting?
Solution
This is called the reachability problem -- is it possible for a given system to enter a given state?
Techniques that attempt to answer this problem fall under reachability analysis, which is one of the main goals of (finite / symbolic) model checking.
As the other answer suggests, this is one of the many instances covered by Rice's theorem. Answering questions about the runtime behavior of programs from only their source code is almost always undecidable. Nonetheless, there are many attempts to solve these problems that can be fairly effective in "real world" code (e.g., Microsoft's 2002 project SLAM), because human programmers tend to try to make their code easy to understand (for other humans; we hope incidentally also for mechanical analysis)
Techniques that attempt to answer this problem fall under reachability analysis, which is one of the main goals of (finite / symbolic) model checking.
As the other answer suggests, this is one of the many instances covered by Rice's theorem. Answering questions about the runtime behavior of programs from only their source code is almost always undecidable. Nonetheless, there are many attempts to solve these problems that can be fairly effective in "real world" code (e.g., Microsoft's 2002 project SLAM), because human programmers tend to try to make their code easy to understand (for other humans; we hope incidentally also for mechanical analysis)
Context
StackExchange Computer Science Q#103247, answer score: 8
Revisions (0)
No revisions yet.