[FOM] Feasible and Utterable Numbers

[Karlis Podnieks]

I would like to call your attention to the following two utterable numbers 
mentioned in Doron Zeilberger's 57th Opinion 
(http://www.math.rutgers.edu/~zeilberg/Opinion57.html):

"Consider walks on the planar square grid with unit steps: "Left", "Right", 
"Up", and "Down". Consider the following two problems:
 - Find a formula for the number of walks with n steps, valid for all n.
 - Find the number of such walks, that are self-avoiding (i.e. never return 
to a previously-visited site) with 1000 steps. "

The solution of the first problem is 4^n, but for the second problem,

"It is very unlikely that a tractable `expression' (or any poly. time 
algorithm) exists. Alas, just like proving that P is not NP, it is just as 
unlikely that there would be a proof that no such algorithm exists."

1. What is the difference between using of very large numbers in physics and 
in combinatorics? Formulas produced by combinatorists - what could be their 
"physical" meaning?

2. Do you think that the notion of utterable numbers is not significant 
because it can be defined simply as "values of feasible size expressions" , 
or "results of (provably halting) computations via feasible programs"?

Exponential expressions represent, perhaps, the simplest structure, in which 
utterable numbers "divorce" from feasible ones. Another remarkable fact: 
comparing of numerical values of these expressions is (probably) an 
absolutely intractable task. Thus, equivalence classes of exponential 
expressions (by their numerical values) represent, indeed, a "fuzzy" notion.

Karlis Podnieks,
University of Latvia