logoalt Hacker News

jerftoday at 7:06 PM1 replyview on HN

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.


Replies

jojogeotoday at 7:39 PM

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!

show 1 reply