[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [ProgSoc] Programming! Code!



On Thu, 2006-10-19 at 14:28 +1000, John Elliot wrote:

> This is the function signature:
> 
>  Int32 fn( Int32 )
> 
> Knowing nothing more about the 'semantics' of the function beyond this 
> signature we know that there are 2 ^ 32 possible inputs each mapped to 
> any one of 2^32 + 1 possible outputs (the '+1' being 'exception', lets 
> assume only one 'exception type').
> 
> So... that is 2^32 * (2^32+1) possible functions. Right?

Not even close.

Consider the truth table:

- It has 2^32 rows, that being the number of possible input values.

- It has 32 columns, that being the number of bits in the possible
output value. (I'm disregarding the +1 for the moment as it is
immaterial and complicates the algebra. Putting the +1 back is left as
an exercise for the reader.)

- So, it is a rectangle with 2^32 * 32 = 2^37 positions on it.

- The number of possible truth tables (implementations) is 2^(number of
positions in the truth table) = 2^(2^37) which is somewhere around
googol^6.




- Raz


-
You are subscribed to the progsoc mailing list. To unsubscribe, send a
message containing "unsubscribe" to progsoc-request@xxxxxxxxxxxxxxxxxxx
If you are having trouble, ask owner-progsoc@xxxxxxxxxxxxxxxxxx for help.