[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