Difference between revisions of "Comment MA375Fall2008walther" - Rhea

Revision as of 22:48, 21 November 2008

Based on mathworld, "The determination of whether a Turing machine will come to a halt given a particular input program. The halting problem is solvable for machines with less than four states".

--lee462 03:48, 22 November 2008 (UTC)

@@ Line 1: / Line 1: @@
-In computability theory, the halting problem is a decision problem which can be stated as follows:
+Based on mathworld, "The determination of whether a Turing machine will come to a halt given a particular input program. The halting problem is solvable for machines with less than four states".
-A description of a program and a finite input, decide whether the program finishes running or will run forever, given that input.
-Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. We say that the halting problem is undecidable over Turing machines. Copeland (2004) attributes the actual term halting problem to Martin Davis.--[[User:Kim297|Kim297]] 10:14, 20 November 2008 (UTC)
+--[[User:lee462|lee462]] 03:48, 22 November 2008 (UTC)

Difference between revisions of "Comment MA375Fall2008walther" - Rhea

Revision as of 22:48, 21 November 2008

Alumni Liaison