April 2020
Intermediate to advanced
244 pages
7h 20m
English
It is important not to confuse the concepts of computability and decidability.
A problem is said to be decidable if there is an algorithm (that is, a predetermined sequence of steps) to solve it. For practical purposes, it is very important to know whether a problem is decidable or not (that is, whether or not an algorithm exists to solve it).
Although, in fact, a Turing machine is able to perform every computable task (based on the Church-Turing thesis), there are problems that cannot be solved by a Turing machine, such as knowing in advance whether the Turing machine will terminate the task that it is performing, or whether it will remain otherwise trapped in an infinite loop (this problem is ...
Read now
Unlock full access