Scooping the Loop Snooper: Proof That the Halting Problem Is Undecidable (2000) | Hacker News Reader

Scooping the Loop Snooper: Proof That the Halting Problem Is Undecidable (2000)

lel.ed.ac.uk

26 pointslgessler33 comments

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.

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.

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.

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.

> 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.

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.

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

> 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.

> 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)

The easy way to think about the halting problem is imagine a program to do some sort of exponential time algorithm. At the end, it checks the result, and if it meets some test, the program goes into an infinite loop. If you could determine that this program halts faster than it would take to run it, then you would know something about this difficult calculation without having to run it. This would be a way to speed up any algorithm!

But it's not only impossible to decide halting faster than the program would run, but impossible at all, a much stronger statement.

It's not really stronger, given that non-halting programs run forever.

That does not exclude possibility. Say determining the result takes 2^n and determining termination takes n!, you cannot speed up the algorithm using halting.

“It seems be too good to be true” is a useful intuition, but it’s importantly different from “it is proven to be false”. (See also P ≠ NP.)

Submitted many times, but only https://news.ycombinator.com/item?id=10077471 had comments, only two.

I've always felt that the lesson in the Halting Problem was that you should write programs that a theoretical P would be able to take in as data and calculate an answer. It's easy to make computers blow up but hard to make them useful. That's why we have well paying jobs managing them.

I wonder, while the halting problem is undecidable for arbitrary Turing machines, are there any practically useful subsets where the halting problem is decidable?

This is the best I could find: https://en.wikipedia.org/wiki/Total_functional_programming

There's also https://en.wikipedia.org/wiki/Primitive_recursive_function implemented in https://en.wikipedia.org/wiki/LOOP_(programming_language)

BPF (and eBPF) disallow all backwards jumps. This makes the halting problem trivially decidable (all programs halt in finite steps), and those programs are still practically useful in their problem domain.

According to my (admittedly minimal) understanding of Turing machines and the halting problem, a Turing machine has a set state encoded on the tape and then the head starts running the program.

I didn't think there was any provision in pure Turing machines for referencing external data, so to reference itself, Q must contain itself recursively on the tape to start with.

If every copy of Q contains a full copy of Q within it then it must be an infinite length program, and any Turing machine will require infinite steps to even read it.

I don't believe this "proof" for this reason.

> If every copy of Q contains a full copy of Q within it then it must be an infinite length program

Try running this Python program and see what it prints:

    w = "print('w = ' + chr(34) + w + chr(34) + chr(10) + w)"
    print('w = ' + chr(34) + w + chr(34) + chr(10) + w)

Setting aside that turning machines have infinite tapes, it's easier to think of them as subroutines in a program.

    P(input: Program): Boolean = ???
    Q(input: Program) = if(P(input)) loop() else stop()

    A() = Q(A)

Writing the above program on a tape (source code file) can be done in fixed space (I've just done it above, no recursive definition required)

While running the program a turing machine can inspect the piece of tape with the program input. It's as if a program is inspecting its own code, which is not only possible in a turing machine, but common to various degrees in languages like Lisp, Scala, Javascript, Java, PHP, Ruby and Python. You might know it as reflection or macros.

Here’s the information you’re missing: https://en.wikipedia.org/wiki/Kleene's_recursion_theorem

Ok, I've made a fool of myself... not sure what I was thinking at the time. Thank you.

Does the halting problem imply perfect automated testing is impossible on nontrivial systems?

No, the halting problem is an abstract result that only applies to infinite systems.

You can test a system with a bigger system, but that is generally economically infeasible, since testing costs are exponential in system size.

Yes. This is Rice's Thm.

Of course, the ever relevant (but in this case somewhat strangely worded) xkcd: https://xkcd.com/622/. Mathematical proofs in the form of poetry are always fun to read.

I was actually surprised by your choice of xkcd, even if it is a fun one. For me the most relevant would have been 1266 - 'Halting problem' : https://xkcd.com/1266/ which is one of my all time favorite.

It may well be, you can't be 100% sure.

Reply on news.ycombinator.com