Q6Theory of Computation
Question
4 marks
Explain the Church-Turing Thesis.
Answer
TMs define what is computable.
The thesis states that a function on the natural numbers is computable by a human following an algorithm if and only if it is computable by a Turing Machine.