Block, SkipCaptcha, apieditor, Automoderated users, Bots, edit, ratelimit-exempt
58,183
edits
Changes
Jump to navigation
Jump to search
Line 1:
Line 1: − +
→top: Spelling/Grammar Check, typos fixed: an universal → a universal
An [[algorithm]] is called '''computable''' if it can be encoded into a set of instructions, which can be input into an 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.
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]].
The definition of computability is largely a consequence of the [[Church-Turing thesis]].