Week 4

Question 1

The Entscheidungsproblem

Answer 1

Hilbert’s idea was to find an algorithm which, given any statement in a formal system, would determine whether or not that statement was true.

Question 2

What is the incompleteness theorem?

Answer 2

This showed that there is no algorithm whose input can be any statement about the integers and
whose output says whether or not the statement is true.

Question 3

How do we prove the Halting Problem is undecidable?

Answer 3

A proof that the halting problem is undecidable goes like this:
1 assume we can write HaltTester;
2 use HaltTester to write Funny;
3 show Funny leads to a contradiction (if P terminates then loop forever);
4 conclude the assumption is wrong. (if we test if funny halts, it never will as it contradicts)

Question 4

What is the totality problem?

Answer 4

Decide whether a program P halts on all inputs - if it does, it computes a total function.

Question 5

How is the totality problem different from the halting problem

Answer 5

Halting problem asks whether it enters an infinite loop for a given input.

Question 6

How do we solve the totality problem?

Answer 6

It converts to the halting problem.
Construct a program Q that ignores its own input and always emulates P on some input D. Q will halt on all inputs only if P halts on input D (which is the halting problem)

Question 7

What is the equivalence problem?

Answer 7

The equivalence problem is to decide whether two programs
are equivalent; that is, they produce the same output for the
same input.

Question 8

How do we solve the equivalence problem?

Answer 8

It is easy to devise programs T and U, such that asking whether T is equivalent to U is like asking if T is total, meaning this problem converts to the totality problem. It’s undecideadble

Question 9

What is Rice’s theorem?

Answer 9

Rice’s Theorem says that if 𝐴 is an extensional and non-trivial
program property then 𝐴 is undecidable.
It implies that there can be no program verification tool that can
check if a program meets the specification.

Question 10

What are the 3 types of problem

Answer 10

Computable - algorithmic solution
Partially computable - approximate algorithmic solution
Noncomputable - no algorithmic solution

Question 11

The Halting problem is…

Answer 11

Partially computable as we