[FOM] Monsieur, x^p = x (mod p), donc Dieu existe. Repondez !
dmehkeri at gmail.com
Sat Mar 12 10:10:08 EST 2011
Vaughan Pratt writes:
> For us nonparticipants in this game it would be helpful to know the
> ground rules.
Well, I did say it didn't have to be BA and feasibile algorithm didn't
have to mean PTIME. Do you mean, why must an ultrafinitary
system have any sort of feasible witness property (PTIME or
otherwise) at all?
> it occurs to me now that one might base such a notion on the Blum
> axioms (q.v. on Wikipedia) for a choice of complexity measure on an
> acceptable Goedel numbering of the partial recursive functions,
> along with a plausible limit on how long a program can run, such as
> some estimate of the lifetime to date of the universe in Planck
> time units, or (much) more generously Parikh's number 2^1000.
Sure, why not? I think I've seen complexity-based ideas (maybe not
exactly the Blum axioms) called "utterability" as opposed to
"feasibility". I don't remember seeing any details on utterability.
In my ignorance, I would guess there can't be ANY induction for
utterable numbers (there are gaps), and if there's no induction what
is there, really? (I mean it's not like feasibilists deny that we can
write down formal notations like "2^2^2^1000" or even more
exotic things, and do some feasible, formal calculations on these
notations.) It doesn't sound like anything prevents utterable
numbers from just being interpreted in terms of feasible numbers, so
wouldn't it just have the same problem I am talking about, then?
More information about the FOM