Re: Computability in principle

From: Joachim Durchholz (joachim.durchholz_at_web.de)
Date: 11/04/03 

Date: Tue, 04 Nov 2003 22:59:19 +0100

I agree that enumeration isn't a practical approach for most problems.

There's one class of exceptions where enumeration is still an option:
namely programs with a rather small input, say, in the range of 10-20 bits.
The exact limit depends on the resources needed for checking each case,
and the available processing power. The distributed processing power
used to demonstrate the "crackability" of DES enumerated a search space
of 2^56 values, so this provides us with a useful upper limit on how far
enumeration can take us.

To state the point more clearly: for some N << 56, enumerating all
programs up to N bits size isn't a promising approach since most
programs have an entropy of more than N bits, but enumerating all inputs
up to N bits to prove a property of a given program might very well be
useful.

Hope this is uncontroversial...

Regards,
Jo