I recently went through my approximately 3-year cycle of wondering what the significance of the Halting problem is all about and wrote up my thoughts here: http://credentiality2.blogspot.com/index.html (I include the link for completeness, but it's not the point of this message, and I can't claim that it's in any way worth the time it takes to read it.) My old CS theory prof tells me I take offense to the notion of uncomputability because I prefer the constructivist school of logic: http://en.wikipedia.org/wiki/Constructivism_(mathematics) I poked around wikipedia a bit and have to agree that it does appeal to me. In particular, I like the idea that the reals are computable and perhaps thus not 200% more infinite than the naturals as I had been lead to believe, but rather 100% less different in cardinality, there being no more fewer reals than naturals than there are naturals and integers. Excuse me, I think I need to sit down for a moment. Anyway, it seems that Constructionism has not yet converted all the heathen masses, and I'm curious what this mass of heathens thinks of it. In particular, I'm curious what it means for diagonalization proofs, which have always seemed suspicious to me, doing magical things that only work out at infinity.
(Referring to Jason's writeup) What did you think was wrong in the italicized statements? -- Mike Stay metaweta@gmail.com http://math.ucr.edu/~mike
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.
At 02:20 PM 8/24/2007, Jason Holt wrote:
In particular, I'm curious what it means for diagonalization proofs, which have always seemed suspicious to me, doing magical things that only work out at infinity.
Just because popular myth has infinity driving Cantor insane doesn't mean that it should do the same thing to us. Certain diagonalization arguments shouldn't be suspicious at all. Diagonalization is essentially the Pigeon-Hole Principle: you can fit n+1 objects (pigeons) into n boxes (pigeon-holes) with only one object per box; popular analogy: 10# of s__t in a 5# bag. For example, a Turing Machine with more tape can disagree with all Turing Machines with less tape. Outline of proof: simulate all the Turing Machines with less tape & disagree with all of those smaller machines in at least one way. A biologist has used a similar argument to claim that creatures with more DNA can resist being wiped out by pests with less DNA -- there are enough variations in the creature with more DNA to be able to resist all of the challenges of the "smaller DNA" pests. The usual Halting Problem proofs simply extend this thinking to countably infinite sequences by unbounding the amount of tape that the Turing Machine is allowed to use.
participants (3)
-
Henry Baker -
Jason Holt -
Mike Stay