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.