Is This True?
cards.jordanscales.com
cards.jordanscales.com
> That is a perfectly acceptable response.
No, it isn’t. Not all problems are decidable (https://en.wikipedia.org/wiki/Undecidable_problem)
Somewhat sounds like an existential horror.
Are we such sentient programs?
Am I?
Hello?
key = 0x0000...
while (decrypt(key, ciphertext) != plaintext) {
key++ // add 1, rollover to zero at the end of keyspace
}
return
The Collatz conjecture example on the other hand shows something where we don’t know whether it will halt for all input[1], because we don’t know if the Collatz conjecture is actually true. There are many other things without proof in either direction, some of which may not be able to be proven (Goedel’s incompleteness theorem says that if I’m not mistaken, but I am not a mathematician, please correct me if I’m wrong or inaccurate).
[1] Yes in practice the data types are limited, memory is limited, state in general is limited. So you can always “solve” the halting problem for a “real” computer by just trying out every representable state, even if that takes longer than the universe exists. But Turing machines, which is what the halting problem is defined on, have infinite tape.
But my point is in practice, this is just not possible, because the problem spaces are too large.
A related problem is the Busy Beaver Problem - how many steps can a program take as a factor of the number of turing instructions it contains. If we could determine that, we would "solve" the halting problem, in that we would know a program that is still running after N steps will never terminate.
However, even for very small programs, N is so large to be incomprehensible; ie, all the stars will have burned out even with all the compute in the world running until that happens.
You brought an example for something where a particular instance is practically unsolvable (because you will run out of time). But it’s still possible to formulate an easy criterium for halting for that program, as I did above.
There are however programs where you can’t know if it halts or not for any input. No criteria can be made (apart from semi-decidable ones: “I know it doesn’t halt for x, does halt for y, but I still don’t know about z”). There is nothing where you can pluck the answer from, as you put it.
FWIW, your take boils down to https://xkcd.com/1266/.
This is wrong, and the proof of the halting problem illustrates why it must be:
Let's name your "sentient program" halts. That is halts(someProgram) "intellectually interprets" the code of someProgram and tells us whether running someProgram will terminate or not. Now consider the following program:
def g():
if halts(g):
loop_forever()
The article contains a few programs for which we (but also compilers nowadays) can statically determine whether they halt. This is not evidence of "intellectual interpretation solves the halting problem". It only means "there are programs for which we can determine whether they terminate", which does not in any way contradict "there cannot be a program that decides whether any arbitrary program halts eventually".