This is contradicts the fact that there are no halting oracles, so the supposition is false.
What is it about this algorithm that makes calling it an oracle prove it doesn’t halt? Oracles (as I understand them, at least) can be created (or assumed) to solve all sorts of problems, from trivial to unsolvable.
(1) Suppose that for every Turing machine that does not halt, there is a proof that it does not halt.
(2) We know that for every Turing machine that halts, there is a proof that it halts.
(3) For every Turing machine, there is either a proof that it halts or a proof that it does not halt. (by (1) and (2))
(4) We know that the set of all proofs is recursively enumerable, i.e. there is a program that outputs all proofs.
(5) We know that, given a proof, it is possible to determine whether it proves that a Turing machine halts, and whether it proves that a Turing machine does not halt.
(6) The set of all proofs that a Turing machine halts, and the set of all proofs that a Turing machine does not halt, are both recursively enumerable. (by (4) and (5))
(7) The set of all Turing machines that halt, and the set of all Turing machines that do not halt, are both recursively enumerable. (by (3) and (6))
(8) There is a program that determines, given a Turing machine, whether it halts or not. (by (7))
(8) contradicts what we already know, so our supposition, (1), must be false.
What is it about this algorithm that makes calling it an oracle prove it doesn’t halt? Oracles (as I understand them, at least) can be created (or assumed) to solve all sorts of problems, from trivial to unsolvable.
Uh, let me try that again.
(1) Suppose that for every Turing machine that does not halt, there is a proof that it does not halt.
(2) We know that for every Turing machine that halts, there is a proof that it halts.
(3) For every Turing machine, there is either a proof that it halts or a proof that it does not halt. (by (1) and (2))
(4) We know that the set of all proofs is recursively enumerable, i.e. there is a program that outputs all proofs.
(5) We know that, given a proof, it is possible to determine whether it proves that a Turing machine halts, and whether it proves that a Turing machine does not halt.
(6) The set of all proofs that a Turing machine halts, and the set of all proofs that a Turing machine does not halt, are both recursively enumerable. (by (4) and (5))
(7) The set of all Turing machines that halt, and the set of all Turing machines that do not halt, are both recursively enumerable. (by (3) and (6))
(8) There is a program that determines, given a Turing machine, whether it halts or not. (by (7))
(8) contradicts what we already know, so our supposition, (1), must be false.
I follow (1) and grant (2). (3) Follows from (1) and (2).
Are you asserting that the set of proofs is finite? This would surprise me but seems to be required for (8) to contradict what I know.
No, the set of proofs is infinite. There is a program that outputs all proofs; it’s just that it takes forever to do so.
...but a finite amount of time to output any specific proof off the list.