[Tutor] church numerals

Danny Yoo dyoo at hkn.eecs.berkeley.edu
Sun Nov 12 05:12:14 CET 2006


>>>> The function just mathematically converted a base-10 number into a
>>>> base-2 number.
>>>>
> For what its worth - we say "base 10" to mean "decimal". But 10 = 
> decimal only when we have already agreed we are talking decimal! 
> Consider a planet where residents have 8 fingers. They count 0 1 2 3 4 5 
> 6 7 10 11. When referring to their number system they also say "base 
> 10". Ditto for any other number base.
>
> So recognize there is tacit agreement that we are speaking decimal
> unless we say otherwise.
>
> Also if you told a "binary" person that his base was 2 he could not 
> understand that. To him it is base 10


Just to add confusion to this issue: it sounds like we're really talking 
about positional number representations.

     http://en.wikipedia.org/wiki/Positional_notation

In order to concisely talk about numbers, we resort to positional notation 
because we're trained to do so.  But because it's the default, there might 
be the belief that decimal notation is the ONLY way we can talk about 
numbers.

But if we were wacky, we could just as easily represent numbers using a 
different representation other than positional notation.  We already know 
of one way: drawing lines.  But here's one that may look very shocking:

#############################
>>> def zero(s, z):
...     return z
...
>>> def one(s, z):
...     return s(z)
...
>>> def add1(n):
...     def new_number(s, z):
...         return s(n(s, z))
...     return new_number
...
>>> two = add1(one)
>>> three = add1(two)
#############################


Believe it or not, these things actually work like numbers:

#########################
>>> def iszero(n):
...     def s(x):
...         return False
...     return n(s, True)
...
>>> iszero(zero)
True
>>> iszero(one)
False
>>> iszero(two)
False
>>> iszero(three)
False
>>>
>>> def add(n1, n2):
...     def new_number(s, z):
...         return n1(s, n2(s, z))
...     return new_number
...
>>> iszero(add(zero, zero))
True
>>> iszero(add(zero, one))
False
>>>
>>> def mul(n1, n2):
...     def new_number(s, z):
...        return n1(lambda z: n2(s, z), z)
...     return new_number
...
>>> iszero(mul(zero, zero))
True
>>> iszero(mul(zero, one))
True
>>> iszero(mul(zero, two))
True
>>> iszero(mul(one, two))
False
>>> iszero(mul(mul(one, two), zero))
True
##########################


And we can even convert this crazy thing back to something familiar:

############################################################
>>> def church_numeral_to_python_number(n):
...     def s(n): return n + 1
...     return n(s, 0)
...
>>> church_numeral_to_python_number(add(one, mul(two, two)))
5
############################################################

The code above is a demonstration of a representation of numbers using 
functions, more commonly known as "Church Numerals".  Functions are very 
powerful.  *grin*


So the fundamental notation of number isn't necessarily tied down to 
anything except the operations we use on them.  We find it very convenient 
to use positional notation because it takes advantage of our fingers and 
our eyes; just don't be fooled into thinking that there's only one way to 
represent number.


More information about the Tutor mailing list