The analogy isn’t perfect because the halting problem can in principle be solved for each particular machine, but trisection can’t be solved for each particular angle.
It can only be solved in that a correct answer can be given; there are some Turing machines that do not halt for which there is no proof that they do not halt.
Yes, this is correct, but the halting problem can still be solved with a simple algorithm for each such machine, and even for all of them at once :-) But okay, we understand each other.
It can only be solved in that a correct answer can be given; there are some Turing machines that do not halt for which there is no proof that they do not halt.
Suppose that for every Turing machine that does not halt, there is a proof that it does not halt. It is pretty obvious that if a Turing machine does halt, there is a proof that it does. Therefore, for every Turing machine, either it halts or it doesn’t, and there is a proof of this. Therefore, the following method constitutes a halting oracle: Go through every possible proof. For each proof P, if P is a proof that the machine in question halts, finish and return YES; if P is a proof that the machine in question does not halt, finish and return NO; otherwise, go on to the next proof. This is contradicts the fact that there are no halting oracles, so the supposition is false.
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.
Of course you can trisect some angles, just not all of them. For example, you can’t trisect the angle of an equilateral triangle (60 degrees).
Just like you can solve the Halting Problem—for particular Turing Machines. The interesting impossibility results are always general.
The analogy isn’t perfect because the halting problem can in principle be solved for each particular machine, but trisection can’t be solved for each particular angle.
It can only be solved in that a correct answer can be given; there are some Turing machines that do not halt for which there is no proof that they do not halt.
Yes, this is correct, but the halting problem can still be solved with a simple algorithm for each such machine, and even for all of them at once :-) But okay, we understand each other.
Prove it.
Suppose that for every Turing machine that does not halt, there is a proof that it does not halt. It is pretty obvious that if a Turing machine does halt, there is a proof that it does. Therefore, for every Turing machine, either it halts or it doesn’t, and there is a proof of this. Therefore, the following method constitutes a halting oracle: Go through every possible proof. For each proof P, if P is a proof that the machine in question halts, finish and return YES; if P is a proof that the machine in question does not halt, finish and return NO; otherwise, go on to the next proof. 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.
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.