(New page: According to Wikipedia, the Halting Problem is a decision problem about properties of computer programs on a fixed Turing-complete model of computation. The question is, given a program an...) |
|||
| Line 1: | Line 1: | ||
According to Wikipedia, the Halting Problem is a decision problem about properties of computer programs on a fixed Turing-complete model of computation. The question is, given a program and an input to the program, whether the program will eventually halt when run with that input. In this abstract framework, there are no resource limitations of memory or time on the program's execution; it can take arbitrarily long, and use arbitrarily much storage space, before halting. The question is simply whether the given program will ever halt on a particular input. | According to Wikipedia, the Halting Problem is a decision problem about properties of computer programs on a fixed Turing-complete model of computation. The question is, given a program and an input to the program, whether the program will eventually halt when run with that input. In this abstract framework, there are no resource limitations of memory or time on the program's execution; it can take arbitrarily long, and use arbitrarily much storage space, before halting. The question is simply whether the given program will ever halt on a particular input. | ||
| + | |||
| + | |||
| + | -- | ||
| + | |||
| + | The halting problem relates a lot to computer science and being able to determine if a computer program will go into an infinite loop. Since you can determine if hte loop is infinite simply by entering an input (even if it doesn't stop...how do you know it never will), is there a computer program that could decide if there is an infinite loop or not. The problem with this is that the written computer program would have to run inside of the program checking for an infinite loop. Thus, the program checking for the infinite loop would never end if there was an infinite loop program. | ||
Revision as of 13:37, 9 November 2008
According to Wikipedia, the Halting Problem is a decision problem about properties of computer programs on a fixed Turing-complete model of computation. The question is, given a program and an input to the program, whether the program will eventually halt when run with that input. In this abstract framework, there are no resource limitations of memory or time on the program's execution; it can take arbitrarily long, and use arbitrarily much storage space, before halting. The question is simply whether the given program will ever halt on a particular input.
--
The halting problem relates a lot to computer science and being able to determine if a computer program will go into an infinite loop. Since you can determine if hte loop is infinite simply by entering an input (even if it doesn't stop...how do you know it never will), is there a computer program that could decide if there is an infinite loop or not. The problem with this is that the written computer program would have to run inside of the program checking for an infinite loop. Thus, the program checking for the infinite loop would never end if there was an infinite loop program.
