L1 - Introduction Flashcards
What question underpins the origin of computability? And who asked it?
David Hilbert questioned whether there was a mechanical procedure that can determine the truthfulness or falseness of any mathematical statement.
In regards to the origin of computability, what did David Hilbert think?
He believed all mathematical problems could be solved via a mechanical process.
Define what it means for a problem to be computable…
A problem is computable if it is possible for a computational device to solve it.
Who proved Hilberts assumption wrong? And how was this done?
Alan Turing : He noted that on certain inputs, the Turing Machine did not halt.
Define Universality…
Universality is a property which a mechanism has such that it can solve perform and solve different problems whilst maintaining the same underlying structure.
Define Computation Limits…
The fact that there are problems that are not solvable given the current limits of computation.
Define Problem Complexity…
Refers to the computational complexity of the problem we are trying to solve.
