Changes

An [[algorithm]] is called '''computable''' if it can be encoded into a set of instructions, which can be inputed into a [[Universal Turing machine]] for processing, and the [[Universal Turing machine]] eventually halts.  How to decide if an algorithm is actully computable is called the [[halting problem]].  [[Alan Turing]] proved that the [[halting problem]] itself is uncomputable.

An [[algorithm]] is called '''computable''' if it can be encoded into a set of instructions, which can be inputed into a [[Universal Turing machine]] for processing, and the [[Universal Turing machine]] eventually halts.  How to decide if an arbitrary algorithm is actully computable is called the [[halting problem]].  [[Alan Turing]] proved that the [[halting problem]] itself is uncomputable.

The definition of computability is largely a consequence of the [[Church-Turing thesis]].

The definition of computability is largely a consequence of the [[Church-Turing thesis]].

[[category:mathematics]]

[[category:mathematics]]