Hacker News Reader

Comment by jojogeo | Hacker News Reader

Something has always nagged me about the halting problem, might be my mis-understanding of the problem space but;

- You have a piece of software

- That software does in memory compute only

- The software does not touch any peripherals, networking, or any other external source which introduce unpredictability (x)

I'm convinced that somehow this can be solved/proven whether the execution will halt or not.

(x) The second you touch any external peripherals or networking, you're effectively asking the question of "If I phone my friend, will they pick up the phone?" -> to which the only answer is, "They'll pick it up, only if they pick it up/are there". You can't answer that question without trying it.

Am I missing the point? I'm sure you can introduce other edges even in the limited model above, e.g. where a memory stick stops responding or something; but all in if you have reliable kit and don't touch anything external, why can't this be solved?

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

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.

The standard argument is:

Assume H(P,i) to be a program that tells you whether the program P will halt on input i. Returns true if it halts and false if it doesn't.

Define a new program G(x) that halts if x does not halt on itself as input and loops forever if x halts on itself as input:

  def G(x):
    if H(x,x):
      while True:
        pass
    else:
      return

Does G(G) halt?

If G(G) halts then H(G,G) is true so we end up in the infinite loop, a contradiction. If G(G) does not halt then it returns without looping, also a contradiction.

So our halting oracle H does not exist, so there can not be a function that tells you whether another function will halt on itself as input, so there can not be a function that tells you in the general case whether some other computation will halt, QED.

Imagine a program that generates the digits of pi, one after the other and stops when it is finished. A general purpose program analysing this program to decide if it stops or not would have to know about pi. And about every other possible algorithm.

This is a brilliant explanation thank you.

Related: the Busy Beaver problem https://news.ycombinator.com/item?id=40857041

Thank you internet stranger, for introducing me to hard-maths drugs; am hooked!! \o/

I love the idea of this. So the BB problems are individual iterations of the halting problem right? To truly solve the problem one would have to come up with a program which would operate on all possible BB numbers?

It can be solved if the memory is bounded. But unbounded memory comes with undecidable problems.

This truly leads into "computation"; when we're dealing with known quantities, yes, we can "solve" the halting problem. The second you move into "we don't know the answer yet", the can of worms opens. Thank you.

There remain undecidable problems even with finite memory/state space.

Linear bounded automata (LBA) the halting problem is decidable. But many properties of LBA are undecidable:

Emptiness: Does an LBA reject all possible inputs? Universality: Does an LBA accept all possible inputs over its alphabet? Equivalent: Do two LBA accept the same language? Finiteness: Does an LBA accept a finite number of strings.

Computation is the study of infinity. That is how I like to think about it. It doesn't seem that way when you're building a website (well, in some ways because it's not at that point), but every algorithm, data structure, etc is an investigation into a certain part of infinity. Think of the way in which we generally categorize algorithms (Big-O notation)... that's just characterizing infinity.

If the memory is bounded then your software is a simple finite automaton, and can be decided in finite time. The issue is with unbounded memory. The issue with the halting problem is a simple characteristic of infinity. This is actually what people are noticing when they say that computation is a fundamental part of the universe. They are correct! The universe deals with infinitisemals all the time. As humans, we have only discovered ways of dealing with certain classes of infinitesemals (calculus). The others remain beyond our ability to characterize. Indeed, some have been proven to be uncharacterizable.

Ahhh thank you it's effectively the known-vs-unknown space;

- How long does it take to get from A to B? => Easy if you know where A and B are, and what mode of transport you're taking to get there.

- How long does it take to get from A to _somewhere_ => As long as it takes!!

You might enjoy the book Escher Gödel Bach, the Eternal Golden Braid by Douglas Hofstadter, which will open up the world, power, and "danger" of proofs using contradiction to you.

Bonne lecture !

Thank you for the suggestions, I look forward to reading!

Reply on news.ycombinator.com