Comment by jerf | Hacker News Reader

Comment by jerf | Hacker News Reader

Parent Full thread

For the finite case, the more relevant question is, can you predict whether or not the computation will halt in less time than 1. executing the algorithm and 2. checking whether or not the algorithm ever loops?

Bear in mind checking whether or not the algorithm ever loops means taking the full state of the system and checking against a database of all previous states of the system. Bear in mind that the Atari 2600, and its whopping 128 bytes of RAM, has with that amount of RAM more states than there are planck volumes * planck time intervals in the known universe... by over sixty orders of magnitude. And every three additional bits you add to the RAM of the system your are looking at adds an order of magnitude (minus a bit) to that, so, nearly 3 orders of magnitude more states per byte... not per megabyte or gigabyte, per byte. Call it 2 orders of magnitude per byte if you want to be conservative.

It can be solved, if by nothing else simply by running it, in the mathematical sense. In the practical sense it's not even close. That's why we use the Turing machine analysis... technically it's an approximation because we don't actually have real Turing machines. However the size of the finite state machines we have is such that it is far more productive to simply say "the halting problem is unsolvable" than to argue about how many orders of magnitude of orders of magnitude of resources it takes to solve the question of whether or a given program terminates.

Thank you for your insightful answer, in reduction; "Don't fight a god, you won't win, and you'll definitely die in the process!"

The approach you describe though is brute force. I don't think (if there even is an answer to this problem) that it can be brute forced; that's where you run into the limits of hardware/computation/energy and start talking about timeframes which exceed the life of the universe.

I think brute force might be a useful tool in places to validate results, but if there _is_ an answer to this problem it's purely mathematical.

Apologies for sounding both excited and naive; these sorts of challenges make me happy in strange ways that no other thing does!

There is no general solution other than brute force. That's not a terribly difficult extension of the halting problem, it just takes more paperwork to deal with the edge cases, but you'll get to that result. The same basic technique works: Your supposed solution to the problem is itself some finite program, and you can feed it the "I halt only if I don't halt" problem too. The difference is that brute force is a solution, because now instead of an infinite sequence of programs you have a bounded set of programs. So whatever concrete "I halt only if I don't halt" you pass to someone within the specified limits, there is definitely some answer, but your technique won't be able to tell what it is short of just running it.

For the same reason the halting problem doesn't even have a good heuristic, neither does this. Unpredictable chaos is not an exceptional case, it is the exponentially-normal case. You have to go the other way, and construct programs deliberately designed to have the ability to tell if they halt. The term for that if you want to learn more about it is "non-Turing complete programming language", sometimes called a "sub-Turing" programming language: https://increment.com/programming-languages/turing-incomplet...

You can read that as "this is how hard it is to construct code that we can make execution guarantees about". That focuses on code that is deliberately constructed to be finite in scope and may be something that can be strictly bounded in memory use or time or both. You'll note if you spend any time working with them how hard they are to work with. That's a reflection of the limits of generalizing any such proofs of time or space of a given program.

If there is a general algorithm that does what you think, we don't even have a clue what it would look like. And we have a lot of clues there can't be any such thing.

Thanks for the link, great read. I think I get you here; in the context of a DSL where it's impossible to travel more instructions than X, suddenly you don't have a halting problem anymore as you've artificially limited that language's ability to travel beyond a known/fixed set of states.

The second you wield a language which has constructs like Haskell, where in theory you can iterate over an infinite list of items (thinking about it even any language where for i in input_var is possible); the halting problem hits you in the face like a brick.

Its almost a chicken and the egg problem, where you can't know how long it will run for/whether it will halt without already knowing the answer, but if you knew the answer, you wouldn't need the program to find it.

My head is spinning.

Reply on news.ycombinator.com