Page namespace (page_namespace) | 0 |
Page title (without namespace) (page_title) | 'Halting problem' |
Full page title (page_prefixedtitle) | 'Halting problem' |
Old content model (old_content_model) | 'wikitext' |
New content model (new_content_model) | 'wikitext' |
Old page wikitext, before the edit (old_wikitext) | '{{stub}}
The '''halting problem''' is to determine, given a program and its
input, whether the program will halt or loop forever. On
[[Turing machine]]s, which have no constraints on memory, the halting
problem can be shown to be unsolvable. The same is thus true for any
[[Turing-complete]] programming language, such as [[Brainfuck]].
The proof is actually relatively simple. It can be done by proof of negation.
Suppose that there ''is'' an algorithm that can decide if other programs, given certain inputs, will end or not. Let's use a C-like syntax, for demonstration purposes. Say that this algorithm is a function declared like so:
bool doesHalt(program, input) {
//How the program and its arguments are represented doesn't actually matter.
...
}
Now let's say we have another function that takes a program as input, like so:
void selfLoop(program) {
if (doesHalt(program, program)) {
infiniteLoop(); //Doesn't matter what happens in this function, just that it will never end
}
else {
return;
}
}
If the program, passed as an argument, loops forever when given itself as input, then <code>selfLoop</code> will loop forever. Otherwise, it will end.
Here's the kicker. What happens if we do this?
selfLoop(selfLoop);
Inside that function call, we'll see <code>doesHalt(selfLoop, selfLoop)</code> be run. That statement will return whether or not <code>selfLoop(selfLoop)</code> runs forever when given itself as input. So if <code>selfLoop(selfLoop)</code> eventually halts, <code>selfLoop(selfLoop)</code> should run forever.
Wait, what? That can't be right. We've come upon a contradiction, a statement that cannot be true. Thus, the halting problem cannot be solved for Turing machines.
The halting problem is, however, solvable for [[finite state machine]]s:
whenever a state change occurs, you compare the new state of the FSM
against all previous states. If you find a match, the program will not
halt. Since the machine has a finite number of states, it is guaranteed
to either halt or return to a previous state at some point. This is how
the [[Smallfuck]] to lookup table compiler works.
[[Category:Concepts]]' |
New page wikitext, after the edit (new_wikitext) | '{{stub}}
The '''halting problem''' is to determine, given a program and its
input, whether the program will halt or loop forever. On
[[Turing machine]]s, which have no constraints on memory, the halting
problem can be shown to be unsolvable. The same is thus true for any
[[Turing-complete]] programming language, such as [[Brainfuck]].
The proof is actually relatively simple. It can be done by proof of negation.
Suppose that there ''is'' an algorithm that can decide if other programs, given certain inputs, will end or not. Let's use a C-like syntax, for demonstration purposes. Say that this algorithm is a function declared like so:
bool doesHalt(program, input) {
//How the program and its arguments are represented doesn't actually matter.
...
}
Now let's say we have another function that takes a program as input, like so:
void selfLoop(program) {
if (doesHalt(program, program)) {
infiniteLoop(); //Doesn't matter what happens in this function, just that it will never end
}
else {
return;
}
}
If the program, passed as an argument, halts when given itself as input, then <code>selfLoop</code> will loop forever. Otherwise, it will end.
Here's the kicker. What happens if we do this?
selfLoop(selfLoop);
Inside that function call, we'll see <code>doesHalt(selfLoop, selfLoop)</code> be run. That statement will return whether or not <code>selfLoop(selfLoop)</code> runs forever when given itself as input. So if <code>selfLoop(selfLoop)</code> eventually halts, <code>selfLoop(selfLoop)</code> should run forever.
Wait, what? That can't be right. We've come upon a contradiction, a statement that cannot be true. Thus, the halting problem cannot be solved for Turing machines.
The halting problem is, however, solvable for [[finite state machine]]s:
whenever a state change occurs, you compare the new state of the FSM
against all previous states. If you find a match, the program will not
halt. Since the machine has a finite number of states, it is guaranteed
to either halt or return to a previous state at some point. This is how
the [[Smallfuck]] to lookup table compiler works.
[[Category:Concepts]]' |