Church-Turing Thesis

Statement

The Church-Turing thesis is the hypothesis that the informal notion of “effectively calculable” functions coincides exactly with the functions computable by a Turing Machine.

Implication

1. Any problem solvable by a physical computer or algorithm can be solved by a Turing Machine.
2. If a problem is undecidable for a Turing Machine (e.g., the Halting Problem), it is undecidable for any computational system.

Status

It is not a mathematical theorem that can be proven, but a definition of computability that is universally accepted due to the equivalence of all known models of computation ($\lambda$-calculus, $\mu$-recursive functions, etc.).