= 27d567bc2d48d9f40e9ccc20ea370b15)
cousin_it comments on Rationality Quotes: October 2009 - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (276)
Couldn't you trisect a right angle by making an equilateral triangle with one of the right angle's lines for a side, then bisecting that angle of the triangle? It wouldn't generalize to other angles, but you wouldn't need a ruler.
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.
(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.