Computability - Revision history

DavidB4-bot: /* top */Spelling/Grammar Check, typos fixed: an universal → a universal

2016-06-27T18:10:04Z

top: Spelling/Grammar Check, typos fixed: an universal → a universal

2016-06-23T15:03:39Z

top: clean up

2008-12-05T23:20:52Z

better cat

2008-06-11T20:49:50Z

fixed link

2008-04-01T21:30:53Z

2007-06-23T02:34:29Z

sp; removing excess links

2007-04-06T12:29:03Z

2007-04-06T12:28:21Z

2007-04-06T12:24:19Z

2007-04-06T12:21:19Z

← Older revision		Revision as of 18:10, June 27, 2016
Line 1:		Line 1:
−	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]].

@@ Line 3: / Line 3: @@
 The definition of computability is largely a consequence of the [[Church-Turing thesis]].
-[[category:Logic]]
+[[Category:Logic]]
 [[Category:Computer Science]]

@@ Line 3: / Line 3: @@
 The definition of computability is largely a consequence of the [[Church-Turing thesis]].
-[[category:mathematics]]
+[[category:Logic]]
 [[Category:Computer Science]]

← Older revision		Revision as of 20:49, June 11, 2008
Line 1:		Line 1:
−	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.	+	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.

	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]].

← Older revision		Revision as of 02:34, June 23, 2007
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 arbitrary 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 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]].

@@ 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 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]].
 [[category:mathematics]]