65.4k views
1 vote
We have been assigned the task of developing a software testing tool (tester) that can assess reachability of statements in a program. Namely, given a program and a statement x in the program (line in the code), the tester should produce a sequence of inputs that demonstrates that the program can reach statement x, or declare that statement x is not reachable under any input sequence. What should we respond to the manager who assigned this task?

A. There is no algorithm to decide whether this can be done or not.
B. This can be done when the program is in C++ but not always for other programming languages.
C. This can never be done because of the Church-Turing thesis.
D. This can always be done because of the Church-Turing thesis.

User CiucaS
by
8.5k points

1 Answer

4 votes

Final answer:

The correct response to the manager would be to convey that while practical tools and techniques exist for estimating reachability in many programs, there is no algorithm that can universally solve the reachability problem for all programs due to undecidability in computability theory. The correct answer is option B. This can be done when the program is in C++ but not always for other programming languages.

Step-by-step explanation:

The task of developing a software testing tool to assess reachability of statements in a program is a challenge that relates to computability and verification in computer science. Responding to a manager who assigns such a task involves clarifying what is possible with current computational theory. The claim that there is no algorithm to decide whether a sequence of inputs can reach a specific statement or to declare it as unreachable, known as the reachability problem, is related to the undecidability issues found in computability theory.

This means that in a general case, for arbitrary programs, there is no algorithm that can always decide the reachability for every given statement. However, there are many static analysis techniques and tools that can be used for a variety of practical programs to make a good estimate or to handle a subset of programs where the problem is decidable. It is not specific to any particular programming language such as C++ as suggested in option B.

The Church-Turing thesis is about the capabilities of what can be computed, not specifically about the problem of reachability, thus neither options C nor D are correct. The best response to the manager would be to clarify that the reachability can often be estimated in practice, but there exists no universal algorithm that can decide reachability for all possible programs and statements.

User Boris Siscanu
by
8.3k points