3
$\begingroup$

The halting problem says that it is impossible to create a general algorithm which can for all inputs and programs determine whether they halt. However, this assumes that the programs and/or the things running them are Turing-complete.

Since all computers have a finite amount of memory and are therefor not Turing-complete, does that mean that the halting problem does not apply to a program run on a machine with finite memory?

$\endgroup$
6
$\begingroup$

You can take a look at: https://en.wikipedia.org/wiki/Halting_problem#Common_pitfalls

One can realize that a program is not halting by seing that it's repeating its behavior.
"A machine with finite memory has a finite number of states, and thus any deterministic program on it must eventually either halt or repeat a previous state"

It also says that even computers are finite state machine, it's more useful to model them as infinite state machines, just because the number of states it's huge.
"Minsky warns us, however, that machines such as computers with e.g., a million small parts, each with two states, will have at least $2^{1,000,000}$ possible states"

$\endgroup$
5
$\begingroup$

If you have a particular machine with a finite state space, you can determine whether a program run by that machine halts by watching it until it either halts or the state of the machine is repeated. This isn't very practical (your halting-checker needs to have vastly more memory than the machine being checked, in order to remember states), but it is decidable.

Of course, that's for a very particular finite state machine implementation running your program. Execution of a program can be abstractly Turing-complete (can theoretically access unbounded memory) even if the actual machine it's practically run on doesn't have unbounded memory. So even if you could check that a program halts on a particular machine (such as by crashing due to insufficient resources), that doesn't necessarily tell you whether the equivalent program would have halted on a different machine with more memory.

$\endgroup$
4
$\begingroup$

Indeed, the theoretical undecidability of the halting problem does not apply to any concrete computer with finite memory. That's a finite system, so for any program, it's mathematically possible to determine whether it halts on a particular computer.

The thing is, this mathematical property is useless in practice.

The main reason for that is that while it's mathematically possible to determine whether a program halts on a computer with finite memory, it may not be physically possible. A computer with $n$ bits of memory has $2^n$ states. The naive way to determine whether a program halts on a finite-state computer is to run it and see if the states repeats before the program halts. But the number of states is so large than this is physically impossible even for relatively small values of $n$. Not only is there not enough time in a human life, there isn't enough energy to do it! Landauer's principle gives a lower limit for the amount of energy consumed by a computer (with any technology that we currently recognize as a computer), and the Solar system only has about enough energy for a little over 200 bits (see Amount of simple operations that is safely out of reach for all humanity?). That's billions of time fewer bits than a typical PC. The whole universe has enough energy, but if you're working on that scale you're probably going to want to analyze a bigger computer, and the ratio between doing and analyzing gets exponentially worse.

In addition, even if you lucked out and found some tricks to analyze the program faster (which isn't always possible — it would effectively mean that you could systematically compress a program — but it might be possible for “interesting” programs), the analysis would only tell you that the program halts, or doesn't halt, on a computer with $n$ bits of memory. It wouldn't tell you whether the program halts on a computer with $n+1$ bits of memory.

In some applications (e.g. a heart monitor or a brake controller), it's very important to know not only that a program will run in a certain fixed amount of memory, but also that it will run in a certain amount of time. For this kind of situation, the halting problem isn't relevant. There is a cost to doing such precise analysis: you need to keep the programs simple enough to stay very, very, very, very far from the theoretical maximum complexity.

In other applications (e.g. a server operating system or a compiler), the exact amount of memory and the exact time are not so important, but we want to be able to analyze complex programs. In this model, removing the time taken and the memory consumption from the analysis makes things a lot easier. It's a well-known phenomenon in mathematics that it's often easier to reason in infinite space than in large finite space, because in large finite space you have to constantly check whether you're bumping into some limit. Here the halting problem corresponds to a useful question to ask in practice.

$\endgroup$
0
$\begingroup$

I agree with the (unanimous) preceding answers regarding finite-memory machines. But I don't see how to apply that argument to the following situation.

Suppose you claim to have a C-language (or any Turing complete language) function

int halts(char *filename)

which reads another C-language program contained in filename and returns 1 if that program eventually halts, returns 0 if not, and just for completeness (i.e., so that halts() is a total function) returns -1 if the contents of filename don't comprise a valid program.

Now, write the following little program and store it in file doIhalt.c

int main(int argc, char *argv[]) {
  int halts();
  while ( halts("doIhalt.c") == 1 ) continue;
  exit; }

Thus, if halts() claims doIhalt.c halts, then it explicitly continues forever; whereas, vice versa, it immediately exits if halts() claims it doesn't halt. So, this is all on a finite-memory machine (assuming the halts() function is finitely implemented), but I don't see how to decide whether or not doIhalt.c halts.

$\endgroup$
  • 1
    $\begingroup$ If you have a finite state halting checker, then it requires more state space than is available on the finite machine you're checking. This means that you can't actually run this program on the same machine that you want to check the halting condition for, so the only way to run it is to run it against a model of the machine with the smaller state space. If you do that, the program must hit a resource limitation built-in to the smaller machine, which means the program must always halt (assuming the function is a valid finite halting-checker when run on a machine with enough memory.) $\endgroup$ – Dan Bryant Sep 2 '16 at 13:37
  • 1
    $\begingroup$ Notably, the program doesn't halt because it comes to an answer; it halts because the finite space limitation of the machine requires execution of the program to fail, either as a halting crash or, possibly, a guaranteed hang. It depends on how the state model of the machine responds to reaching its limit. $\endgroup$ – Dan Bryant Sep 2 '16 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.