Difference between revisions of "Computability"
Jump to navigation
Jump to search
m (New page: 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 Tu...) |
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. | 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. | ||
| + | |||
| + | The definition of computability is largely a consequence of the [[Church-Turing thesis]]. | ||
[[category:mathematics]] | [[category:mathematics]] | ||
Revision as of 12:16, 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.
The definition of computability is largely a consequence of the Church-Turing thesis.