= 27d567bc2d48d9f40e9ccc20ea370b15)
Technologos 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)
Which is perhaps what you meant by "break the rules" (of construction), by using a marked ruler, for instance.
Right. There are some constructions like Archimedes's use of a marked ruler (which is covered, actually, in the 'Means to trisect angles by going outside the Greek framework' section) which work correctly & are not immediately obviously breaking the rules. So I had to ask before I could know whether he had broken the rules or broken his proof (if you follow me).
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.