4.4.4.6 Computable and non-computable problems and 4.4.4.7 Halting problem Flashcards
1
Q
What is the significance of the halting problem?
A
Shows that some problems are non-computable - some problems cannot be solved by a computer/algorithm;
In general, inspection alone cannot always determine whether any given algorithm will halt for its given inputs // a program cannot be written that can determine whether any given algorithm will halt for its given inputs;
2
Q
What is the halting problem?
A
Is it possible in general to write a program/algorithm; that can tell, given any program and its inputs and without running/executing the program;, whether the given program with its given inputs will halt?
3
Q
What is a non-computable problem?
A
a problem for which there is no algorithm that can be used to solve it
e.g the halting problem
