< Previous
Next >

: I brought this up in Math 199:

There is a notion of polynomial time as the upper bound for useful decidability, as opposed to just plain decidability. That is, there are many relations which are decidable but which we don't want to sit around and wait for the decision procedure to finish (eg. a 2^2^n algorithm on a modern computer will take longer than the current age of the universe to run, for n=7).

That was not what I brought up. What I brought up was let's take this to its logical conclusion. There are decidable relations which in a very real sense we cannot actually decide because the heat-death of the universe will occur before any decision procedure finishes. Anything not in the set of such relations, even if decidable, would be effectively undecidable in this universe. Even if we posessed mighty quantum computers which shredded exponential time, there are 2^2^2^2^2^2^2...^n-time decision procedures which we would never be able to run.

Possibly we could formalize this with an information-theoretic argument relating the amount of information in the universe with the amount of information required for a decision procedure, but I don't know any information theory. I do know, however, that this set of effectively decidable relations grows smaller with every second that passes and every action you take. So watch it, pal.


Unless otherwise noted, all content licensed by Leonard Richardson
under a Creative Commons License.