Difference between revisions of "Computability"
Jump to navigation
Jump to search
m |
|||
| Line 1: | Line 1: | ||
| − | 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 | + | 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. |
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]] | ||
Revision as of 12:24, April 6, 2007
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.
The definition of computability is largely a consequence of the Church-Turing thesis.