Computability theory is part of computer science. Scientists want to know what can be computed, and what can not.

There is a model of a computer that is used for this. It is called the Turing machine. A Turing machine basically is a special typewriter with an endless ribbon. The machine is named after the mathematician Alan Turing.

People say a problem is computable, if the problem can be expressed in such a way that Turing machine can solve it.

One of the best known examples is the halting problem. The task is to write a program which says for all programs whether they will finally stop. This is impossible to decide. Mathematicians say the problem is undecidable.

Computer science | Mathematics

نظرية الحسوبية | Teorie vyčíslitelnosti | Berechenbarkeitstheorie | Computability theory (computer science) | Teoría de la computabilidad | نظریه محاسبه‌پذیری | Calculabilité | 계산 가능성 이론 | Teoria della calcolabilità | Berekenbaarheid | 計算可能性理論 | Teoria obliczalności | Теория вычислимости | ทฤษฎีการคำนวณได้