On Fri, 24 Aug 2007, Mike Stay wrote:
(Referring to Jason's writeup)
What did you think was wrong in the italicized statements?
Here are the quotes I took issue with from the random lecture slides I found online: :: There are things we can imagine wanting to do, but which cannot be done by following an algorithm. As Hilarie pointed out privately, halting proves something very specific for true turing machines (infinite tape). My writeup was trying to say that the thing we want to do -- find out about whether programs halt -- might very well be possible to accomplish with an algorithm, even for true turing machines, if we bend the constraints of the proof even slightly. And of course for practical (finite) turing machines, we even have an algorithm for solving it. It just needs (lots, and lots of) optimization to be practical. :: Equivalently, we now know there are recursively enumerable languages that are not recursive. For such languages, we have no parsing algorithm that will terminate on all inputs. I pointed out that phrase as one that might actually contradict my argument. I'm still wrapping my head around the question of whether I believe this applies in practical circumstances. :: Are there no practical applications of HP? Sometimes, programs loop. So you may want to design a compiler that warns the programmer if asked to compile a program that will loop. The undecidability of HP tells you that unless you limit the range of programs in some way, you will not be able to design such a compiler." This, like the first statement, is I think the classic sin committed wrt halting -- claiming that there's something special about this particular hard problem (as opposed to, say, computer vision or human-like AI) just because there's a proof about it in the vaguely similar theoretical model of computing.