Halting problem - Revision history

DavidB4-bot: /* top */clean up

2016-06-23T15:04:12Z

top: clean up

FrederickT3: comma

2011-09-26T15:17:14Z

comma

CPalmer: cat

2011-08-18T11:23:32Z

cat

NekoMimi: Rather brief and somewhat more obtuse than I would like, but hopefully more accurate.

2011-02-08T04:52:50Z

Rather brief and somewhat more obtuse than I would like, but hopefully more accurate.

Melisande: spelling: undecideabe -> undecidabe

2008-09-16T03:03:31Z

spelling: undecideabe -> undecidabe

Foxtrot: link

2008-06-11T20:57:03Z

link

Foxtrot: famous theoretical computer science problem

2008-06-11T01:36:40Z

famous theoretical computer science problem

New page

The '''Halting Problem''' is a problem in theoretical [[computer science]] which measures the effectiveness with which [[computer]]s execute [[algorithm]]s. In the theoretical formulation, computers are represented by [[Turing machine]]s and algorithms are represented by an infinitely long piece of tape that moves around inside the Turing machine. The tape has instructions for the machine; if it can execute this instruction it moves to the next piece of tape, if it cannot, the machine halts. The Halting Problem asks for a reliable prediction of whether a particular machine will halt before you put the tape into it.

[[Alan Turing]], the founding father of theoretical computer science, showed the Halting Problem is undecideable. In other words, one can never truly rely on a computer to halt its computations. While this is theoretically significant, in practice most computer programs have been written so that they do not have [[runtime error]]s.

[[Category:Computer Science]]

@@ Line 6: / Line 6: @@
 halts for all valid input less than or equal to 0, and continues forever for all such input greater than 0.
-In 1936, [[Alan Turing]] proved that there is no general algorithm that can decide this for every possible program and every possible input. (In other words, it is impossible to write a program that is capable of deciding whether a given program and given input will halt in all cases -- there will be some for which it is impossible for it to make such a determination.) As such, the halting problem is [[undecidable]] over Turing machines.
+In 1936, [[Alan Turing]] proved that there is no general algorithm that can decide this for every possible program and every possible input. (In other words, it is impossible to write a program that is capable of deciding whether a given program and given input will halt in all cases—there will be some for which it is impossible for it to make such a determination.) As such, the halting problem is [[undecidable]] over Turing machines.
 [[Category:Computer Science]]

@@ Line 1: / Line 1: @@
-The '''halting problem''', a subject in theoretical [[computer science]] is the general question of determining, given a description of a [[computer program]], and a given input to said program, whether the program will come to an end (halt) on a Turing-complete machine, or continue to run forever. For example, it is apparent that the program described by the C snippet
+The '''halting problem''', a subject in theoretical [[computer science]], is the general question of determining, given a description of a [[computer program]], and a given input to said program, whether the program will come to an end (halt) on a Turing-complete machine, or continue to run forever. For example, it is apparent that the program described by the C snippet
   int halts(int x) {
       while(x > 0) {

← Older revision		Revision as of 11:23, August 18, 2011
Line 7:		Line 7:

	In 1936, [[Alan Turing]] proved that there is no general algorithm that can decide this for every possible program and every possible input. (In other words, it is impossible to write a program that is capable of deciding whether a given program and given input will halt in all cases -- there will be some for which it is impossible for it to make such a determination.) As such, the halting problem is [[undecidable]] over Turing machines.		In 1936, [[Alan Turing]] proved that there is no general algorithm that can decide this for every possible program and every possible input. (In other words, it is impossible to write a program that is capable of deciding whether a given program and given input will halt in all cases -- there will be some for which it is impossible for it to make such a determination.) As such, the halting problem is [[undecidable]] over Turing machines.
		+	[[Category:Computer Science]]

← Older revision		Revision as of 04:52, February 8, 2011
Line 1:		Line 1:
−	The '''~~Halting Problem~~''' is a ~~problem~~ in theoretical [[computer science]] ~~which measures~~ the ~~effectiveness with which~~ [[computer]]~~s execute [[algorithm]]s. In the theoretical formulation~~, ~~computers are represented by [[Turing machine]]s~~ and ~~algorithms are represented by~~ an ~~infinitely long piece of tape that moves around inside the~~ Turing machine. ~~The tape has instructions for the machine; if~~ it ~~can execute this instruction it moves to~~ the ~~next piece of tape, if it cannot,~~ the ~~machine~~ halts~~. The Halting Problem asks~~ for ~~a reliable prediction of whether a particular machine will halt before you put the tape into it~~.	+	The '''halting problem''', a subject in theoretical [[computer science]] is the general question of determining, given a description of a [[computer program]], and a given input to said program, whether the program will come to an end (halt) on a Turing-complete machine, or continue to run forever. For example, it is apparent that the program described by the C snippet
		+	int halts(int x) {
		+	while(x > 0) {
		+	}
		+	}
		+	halts for all valid input less than or equal to 0, and continues forever for all such input greater than 0.

−	[[Alan Turing]]~~, the founding father of theoretical computer science, showed the Halting Problem~~ is ~~[[undecidable]]~~. In other words, ~~one can never truly rely on~~ a ~~computer~~ to ~~halt its computations~~. ~~While this~~ is ~~theoretically significant, in practice most computer programs have been written so that they do not have~~ [[~~runtime error~~]]s.	+	In 1936, [[Alan Turing]] proved that there is no general algorithm that can decide this for every possible program and every possible input. (In other words, it is impossible to write a program that is capable of deciding whether a given program and given input will halt in all cases -- there will be some for which it is impossible for it to make such a determination.) As such, the halting problem is [[undecidable]] over Turing machines.
−
−	~~[[Category:Computer Science]]~~

@@ Line 1: / Line 1: @@
 The '''Halting Problem''' is a problem in theoretical [[computer science]] which measures the effectiveness with which [[computer]]s execute [[algorithm]]s. In the theoretical formulation, computers are represented by [[Turing machine]]s and algorithms are represented by an infinitely long piece of tape that moves around inside the Turing machine. The tape has instructions for the machine; if it can execute this instruction it moves to the next piece of tape, if it cannot, the machine halts. The Halting Problem asks for a reliable prediction of whether a particular machine will halt before you put the tape into it.
-[[Alan Turing]], the founding father of theoretical computer science, showed the Halting Problem is [[undecideable]]. In other words, one can never truly rely on a computer to halt its computations. While this is theoretically significant, in practice most computer programs have been written so that they do not have [[runtime error]]s.
+[[Alan Turing]], the founding father of theoretical computer science, showed the Halting Problem is [[undecidable]]. In other words, one can never truly rely on a computer to halt its computations. While this is theoretically significant, in practice most computer programs have been written so that they do not have [[runtime error]]s.
 [[Category:Computer Science]]