3 ms·
Oh I see what you're getting at. I think what you're trying to get at is, "If you had a halting-solver, you could use that like an oracle to answer arbitrary ma
by xamuel 7y ago
Oh I see what you're getting at. I think what you're trying to get at is, "If you had a halting-solver, you could use that like an oracle to answer arbitrary mathematical questions." Unfortunately, this isn't true, you couldn't use it to answer arbitrary mathematical questions, just certain questions.
For example, even if Pi happens to be rational, and the algorithm to list its digits eventually starts listing a periodic repetition (possibly the all-0 repetition even), that still doesn't mean it halts. So the halting-solver doesn't directly help you determine whether or not Pi is rational. You would instead need a "determine-if-given-function-eventually-has-periodic-output" solver, which is stronger than a halting solver.
I'm not sure if there are any really slam-dunk examples of what you seem to be looking for, that don't involve proofs in some guise or other. An example which does involve proofs might look like this: "Let x be a program which attempts, by brute force, to find a proof that P<>NP, and immediately halts when it finds such a proof, if ever. If you had a halting detector, you could plug x into it and based on its output, you would know whether or not there is a proof of P<>NP." [Which is subtly different than whether or not P<>NP is true. That would require something stronger than a halting solver to obtain.]
- jandrese 7y agoWouldn't you simply define your sample program to halt upon discovering a periodic repetition in its output?
- tlb 7y agoFinding any finite number of repeating digits does not prove that there's an infinite number to follow. You might find 1000 3s in a row, followed by not a 3.
- jandrese 7y agoIf you know the entire state of your algorithm then it's possible to compare the state vs. it's state in a previous step to determine if you are in a repeating loop. If all of the parameters and internal are identical, then the algorithm can not produce a different result.
- xamuel 7y agoA machine can print the same thing over and over, and yet never repeat its own internal state. For example, "let x=0; while(true) { print("0"); x=x+1;}"
- jandrese 7y agoA halting problem solver would necessarily have to be smart enough to detect state that is relevant to the completion of the program vs. not. Plus, even in this case on a real world machine x can only store as much state at the underlying type. So if it's a 32 bit int then you can absolutely prove the algorithm does not halt after only 4 billion iterations, but even before that you can simply note the lack of exit conditions from the loop to show that it never terminates. However clever you are, the halting problem program has to be even more clever by definition. But we don't have an upper bound on cleverness, so the halting problem program has to be infinitely clever, hence my previous point about it being able to solve all of mathematics.