[FOM] feasibility (was PA Incompleteness)

[Vaughan Pratt]

From: Vladimir Sazunov
> 2. Another approach is based on Parikh's formalization of feasible 
> numbers and, as I believe, more adequate formalization which I 
> mentioned in my recent posting to FOM 
> http://www.cs.nyu.edu/pipermail/fom/2007-October/012042.html
> 
> Here it is assumed that the "semi-set" (using the term of Vopenka) F of 
> feasible numbers contains 0,1 and is closed under +, but is bounded by 
> 2^1000 (Alternatively, forall n log log n < 10 is postulated what means 
> that 2^1024.)

If we are talking about the "real" world here, may I conservatively 
suggest 2^^6, a stack of six 2's?  (Less conservatively, four 2's and a 
3, but six 2's is simpler as well as offering a handy margin of error. 
The notation 2^^6 adapts to ASCII Knuth's notation for the next 
operation after exponentiation in the Grzegorczyk hierarchy.)

Rationale: it is plausible that there are fewer than 2^256 qubits in 
what we understand by the "real world," which therefore would have at 
most 2^(2^256) observable states, noting that 256 = 2^(2^3) < 2^^4, 
whence a state count of six 2's or 2^^6.

2^1024 is tiny, being the square root of the number of memory states of 
the MITS Altair 8800, which at $400 in 1975 was the first PC readily 
available to consumers.  Its 256 bytes of RAM gave it 2^2048 states for 
its RAM alone, rather less than a stack of four 2's (2^65536 = 2^^4, the 
number of states of RAM in the enhanced MAI JOLT kit I assembled in 
September 1975).

For that money today you can buy a terabyte of hard drive offering well 
over 2^^5 states.

Another two in the stack takes you to 2^^6, which should see you through 
the foreseeable future of the universe.

Unless of course you were planning to reason about the universe with 
either dynamic or temporal logic.  In that case you would appear to be 
looking at 2^^7 possible predicates on the states of the universe.

On the other hand the counterargument implied by 
http://boole.stanford.edu/pub/coimbra.pdf suggests 2^^5 as a more 
reasonable estimate of the number of such predicates, on the ground that 
the 2^^6 states form a complete atomic Boolean algebra or CABA, 
predicates on which are better understood as complete ultrafilters, i.e. 
the qubits themselves as the atoms of the CABA, than simply as subsets 
of its underlying set.

Number theory will no doubt demand larger numbers, feasibility be 
damned, but for reasoning about the real world, 2^^6, a stack of six 
2's, may well suffice.

Vaughan Pratt