4 - Theory of Computation

Question 1

Describe the significance of the Halting problem for commutation.

Answer 1

The Halting problem demonstrates that there are some problems that cannot be solved by a computer.

Question 2

What is the question posed by the by the Halting problem?

Answer 2

Is it possible in general to write a program that can tell, given any program and its inputs, and without running the program, whether the given program with its given inputs will halt?

Question 3

Why is it not possible to create a Turing machine that solves the Halting problem?

Answer 3

The Halting problem is non-computable