Book in the works by Alexander Stepanov

[Manfred_Nowak]

superdan wrote:

>> Sorrily Stepanov gives no answer for the immidiately rising
>> question what the restriction of a finite computational basis
>> implies for computational hard/intractable problems. 
[...]
> please explain it to me.  

Every natural number has a prime factorization and the set of prime 
numbers is infinite. Therefore: if one is restricted to a finite set 
of prime numbers for the use in a prime factorization then there 
exist natural numbers for which one will not be able to build a prime 
factorization, based on the given restricted set.

My prerequisite for the citation above was "If an analogy to numbers 
is allowed [...]". Under this prerequisite and the contents of the 
paragraph immediately above, one would be allowed to conclude:

| for _some_ given specification of a type `T', the restriction of a
| finite computational basis for `T' might imply, that there exist
| problems based on the specification of `T', that cannot be solved
| efficiently by using that _finite_ basis 

If the word "some" above can be generalized to "any", then this would 
be a severe strike into the face of the fans of the reusable 
components view on programming, to which Stepanov belongs. However, 
if one stays with the "some", then one has to give criteria on how 
one can decide whether a given specification is efficiently 
fulfillable with a finite computational basis.

Those that are considered not fulfillable by a finite basis might be 
those, which are considered hard or intractable in the known sense.

I am quite surprised, that hard/intractable problems might show up on 
something I considered mostly harmless until reading Stepanov: the 
specification of a type, for which a finite computational basis is 
known.


A simple solution would be, that my prerequisite "analogy to 
numbers" is disallowed, but I do not see any obvious reason for this 
disallowance and I would be glad, if Stepanov would provide some 
guidance. Therefore:

| Sorrily Stepanov gives no answer ...

-manfred
   


-- 
If life is going to exist in this Universe, then the one thing it 
cannot afford to have is a sense of proportion. (Douglas Adams)