Hacker News Reader

Comment by Animats | Hacker News Reader

Actually, it's quite possible to determine if a deterministic program with finite memory will loop. Either it halts, or it repeats a previous state.

You can check for repeating a previous state by running two copies in lockstep, one running twice as fast as the other. If the states of the two match, you're in an infinite loop. In the 1970s, a batch system intended for beginning programmers actually did that. The college had discovered that the successful jobs ran about a second, and the ones in a loop ran out the 30 second timer. So it was a win to take a 2x speed penalty to catch simple loops.

You can make a program cycle through a very large number of states, so you don't always get a practical halting check, but in theory, and often in practice, you do repeat a state eventually.

Undecidability requires infinities.

View on HN

> Undecidability requires infinities

Not in any reasonably modern system. The state in this case is the exact sequence of bits contained in RAM and on your hard drive, which might as well be infinite (lets ignore for a moment that your computer is connected to the Internet and to real entropy sources, which really do make things infinite).

Some napkin math: if you've got a terabyte hard drive and 32 gigs of RAM, then there are approximately 2^(1,032 * 1024 * 1024) states your computer might be in, which is about 1.79 * 10 ^ 325,753,719. It can be hard to conceptualize numbers at that scale, but a fun illustration is that it is so big that the number itself would not fit on many laptops. It is infinite for any useful sense.

For comparison, there are an estimated 10^86 atoms in the observable universe -- if each atom in the universe was in fact its own universe, and each atom in all of those universes was its own universe, and so on... you'd have to go four layers deep to start talking comparable numbers here.

A finite deterministic state machine can not perform more transitions than it has states without returning to a state it has been in before, and once that happens, because it is deterministic, it will repeat the sequence of transactions, that occurred between the first and second occurrence of that state, indefinitely.

All programs that halt, therefore, must do so in less than #states steps, and the rest certainly never will, so we could show, in finite time, whether any given program on that machine will halt. We know, therefore, that the halting problem on this machine is decidable, even if we could not, in practice, demonstrate it.

The halting problem was not posed because we want to know if a given program will halt; it was posed as a means of attacking a much deeper problem.

Note also that any NFA can be converted to an equivalent DFA by powerset construction.

https://en.wikipedia.org/wiki/Powerset_construction

Computational and complexity theory are abstract mathematical subjects where numbers are either finite or infinite. A very large finite number is still finite. There is no meaningful notion of "so big that we can pretend it is infinity" in questions of decidability, and the limitations of the real world are irrelevant.

> Actually, it's quite possible to determine if a deterministic program with finite memory will loop.

More practically, if you stick to structurally recursive loops, it's trivial to determine those loops will terminate. Structural recursion is when the recursive calls acts on smaller parts of the original input (e.g. map, reduce and filter functions do this), so you know it'll terminate eventually.

I find it pretty rare that I write loops with complex looping conditions.

But without infinity, a system cannot examine itself, only subsets of itself. Even for the two copies in lockstep, you need a system at least two times as big as the one being examined.

I disagree, look at quines. Systems can contain copies of themselves if they can be compressed.

A quine prints a copy of itself, it does not contain a copy of itself. The copy contained in the quine is not executable in its compressed form.

There is a general theorem that says that for any computation, you can write a program that executes that computation on its own source code. The quine is only a special case.

Two is much smaller than infinity.

But the 2x systems still cannot examine itself, but only half of it (being optimistic, because in addition to the 2x you also need the logic doing the stepping and the comparison). There is no finite system that is a true subset of itself.

> Undecidability requires infinities.

As does the Turing machine itself, or any other turing complete computation model for that matter.

Heck, even the study of computational complexity forces you to accept some arbitrarily large value of n, which implies any fixed finite storage capacity is unacceptably small.

Modern programming does a pretty good job at approximating infinite memory (by using the cloud as a data store)

Reply on news.ycombinator.com