L8 - Further Undecidable Problems

Question 1

What is Problem Reduction?

Answer 1

Technique of reducing a problem A to problem B such that a solution to B can be used to solve A.

Question 2

How does Problem Reduction relate to decidability?

Answer 2

If A reduces to B, and B is decidable, then A is also decidable.

Question 3

How does Problem Reduction and the Halting Problem help classify decidability of problems?

Answer 3

If the Halting Problem is undecidable, through problem reduction we can verify that other problems are also undecidable.

Question 4

What is the Totality Problem?

Answer 4

Is there a universal program that can determine whether another program halts for all inputs.

Question 5

What is the relationship between the Totality and Halting Problems?

Answer 5

The Halting Problem is reducible to the Totality Problem. If we solve the Totality Problem, it means M halts on all X, thus M halts on X.

Question 6

Define the Equivalence Problem…

Answer 6

Given 2 Turing machines, determine whether they compute the same function. I.e both machines halt or not for an input.

Question 7

Why is the Totality Problem reducible to the Equivalence Problem?

Answer 7

Program T is true if P halts on D. Program U always returns true.

If T==U, then P halts on all inputs.

Question 8

What is Rices theorem…

Answer 8

Any functional property of a program is undecidable.

Question 9

What is the implication of Rices Theorem?

Answer 9

There exists no verification tool that can be sure that a program meets its technical specification.

Question 10

What are the 4 ways to deal with undecidability in Program Verification?

Answer 10

Approximation algorithms

Probabilistic arguments -> Test on a subset to gauge probability

Less automation

Simplify problems