Difference between revisions of "Computability"
From Conservapedia
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...) |
DavidB4-bot (Talk | contribs) (→top: Spelling/Grammar Check, typos fixed: an universal → a universal) |
||
| (10 intermediate revisions by 5 users not shown) | |||
| Line 1: | Line 1: | ||
| − | An [[algorithm]] is called '''computable''' if it can be encoded into a set of instructions, which can be | + | An [[algorithm]] is called '''computable''' if it can be encoded into a set of instructions, which can be input into a universal [[Turing machine]] for processing, and the universal Turing machine eventually halts. How to decide if an arbitrary algorithm is actually 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]]. |
| + | |||
| + | [[Category:Logic]] | ||
| + | [[Category:Computer Science]] | ||
Latest revision as of 18:10, June 27, 2016
An algorithm is called computable if it can be encoded into a set of instructions, which can be input into a universal Turing machine for processing, and the universal Turing machine eventually halts. How to decide if an arbitrary algorithm is actually 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.
