Tuesday, November 17, 2009

Picture Proves

Do you ever walk through a proof, understand each step, yet not believe the 
theorem, not say ‘Yes, of course it’s true’? The analytic, logical, sequential 
approach often does not convince one as well as does a carefully crafted 
picture. This difference is no coincidence. The analytic, sequential portions 
of our brain evolved with our capacity for language, which is perhaps 105 
years old. Our pictorial, Gestalt hardware results from millions of years 
of evolution of the visual system and cortex. In comparison to our visual 
hardware, our symbolic, sequential hardware is an ill-developed latecomer. 
Advertisers know that words alone do not convince you to waste money on 
their clients’ junk, so they spend zillions on images. This principle, which has 
higher applications, is the theme of this chapter. 


http://ocw.mit.edu/NR/rdonlyres/Mathematics/18-098January--IAP--2008/FFEA8D92-1210-46A9-8D43-931D4A43D87C/0/sf_math.pdf
quote from Street Fighting Mathematics.


Saturday, November 14, 2009

From concrete to abstract

    Most of introduction on Category theory starts with the definition of a category first,
then give some example. Which I believe is wrong.
    It's same wrong way that we are taught on mathematics in university.

Teaching definition, theory first, then give example, exercise is a totally wrong way of teaching math.
This way assume gives us a few axioms, rules, then we can reduce the whole mathematic world,
we can select rule and axioms to solve problem, which is totally wrong.
This way assume human as a computer, a rule deduction system, but think this way:
    assuming we have 1 axiom
    by simple replace rule, we get 1 corollaries.
    so next step , we have to choose from 2 (axiom + corollaries)
    and next , we apply replace rule, get 1 more corollaries, now we have 3 choices. ...
    the search space is 1 * 2 * 3 * 4 ..   = n!
obviously , human mind are not good at this way of thinking. Just take a look how popular of simple
puzzle games on iTune, you can agree with me.

From my own personal experience,  my brain never works this way. It can easily image a 2d image,
then remember there a 7 corollaries.

I believe Feynman( a great physicist) learning mathematics by himself. From a book I ready about him,
he seemed invented a whole system about mathematics by him own, and one day , when he discuss with
other classmate, he found nobody can understand him.

So my point is : mathematics should be learned by yourself, not taught by someone.
Give yourself a few problems, maybe not math problem, solve them, find the common things between them, abstract them .
Example 1 :  we found
    (1 + 2 ) * 3 = 9 = 1*3 + 2 * 3
    (2 + 3) * 4 = 4 * 2 + 4 * 3
    ...
so what's common among them ? think yourself before reading.
( This is important , and maybe the only way to learn math . Think yourself before reading )
 What's common : two numbers add first , then multiply a third number, can multiply to the third number each first, then add.
But the above sentence is too verbose, the third number appeared twice, how about we replace it with z?
also, what number here is not important, how about we use x, y to represent any number?
so we get

          (x +y) * z = x *z + y *z                            (1)

Now we get Algebra : using x,y,z to represent any numbers, we found equations that can be used to any numbers!!

This might seemed to be to simple for most of adults, some let continue to some difficulty ones.

we already might now
     x ^ (m+n) = x^m * x^n                       (2)

( ^ is for power , 2 ^3 = 8, 2 ^ 4 = 16)
so what's common about (1) and (2) ??? ( Think, before you continue)

first , I'll change some variable in (2) to get some hint.
      z ^ ( x + y) = z ^ x * z ^ y                  (3)
      z * ( x + y) = z * x + z * y                  (4)
secondly, there are too many z^ in (3), how about we use f to replace z^ ?
     f(x+y) = f x * f y                                  (5)
use g to replace z*
     g(x+y) = gx + gy                                  (6)

so now we have the concept of function !

But still, the x,y in (5) and (6) appeared twice, can we remove it ?  (Think !!)
how about we image + (add symbol ) as a pipe with 2 input, 1 output ?
and f as a pipe of 1 input , 1 output ? so f(x+y) become
x --->
           +    ---> f  --->  f(x+y)
x --->

for simplicity , we just write
     + f
to represent above picture.
Now your exercise : draw picture of fx * fy
     f(x+y) = fx * fy will change to

-->               --> f
       +  f  =              *
-->               --> f

we use II f to represent a pair of f , so
  + f = (II f)   *             (7)

now can you image we can use (7) to represent both z* (x+y) = z *x + z*y and z^(x+y) = ...?

Now take a look at the pair  II , it take a function ( pipe), and return a pair of pipe ! It's a functor  !
Also we found a lot of binary function  has equations like (7), so we abstract the concept of binary operator , and get
   b1 f = (II f) b2    where b1 ,b2 are binary function.  (8)

I'm a little lazy now, but I'm telling you (8) can be abstract again to get homomorphism, 
and natural  transformation , category .....

The following link is a good article worth reading .
http://betterexplained.com/articles/developing-your-intuition-for-math/

Thursday, November 12, 2009

Readability of programming

The readability of a piece of code depends on following staff:

  • Background knowledge
  • Input of a function
  • Output
  • intermedia  result
To improve readability, there should be a way to visualize how the data are processed by each line of code.

fold VS. map

I prefer map to fold, it's much clear for me to thinking in map than fold.
Fold has a sound mathematic background : induction. While it's good to reason about the correctness of
program, it adds an unnecessary  constrain: the elements have to be processed from left to right.

While with map, all elements can be process parallel.

my reading list

It would be interesting to keep a reading list, logging what I have read.

Category:
        Basic_Category_Theory_for_Computer_Scientists_-_B._Pierce

        Categories for the working mathematician
        A Gentle Introduction to Category Theory —
                the calculational approach — Maarten M. Fokkinga
                Better read Topoi before read this.  A little bit hard as a tutorial,
                but his calculation approach is unique and clear.

        Computational Category Theory - D.E.Rydeheard
                Implementation Category in ML.

        Conceptual_Mathematics_-_A_First_Introduction_to_Categories

        Topoi - the categorial analysis of logic. Robert GoldBlatt. (Great book )
                     Best introduction book. From this book, I begin to understand why category was invented.

Pointfree, Program algebra
        an introduction to the Bird Meertens formalism
        Law and Order in Algorithmics. Maarten M. Fokkinga (Great)

Math:
        Linear Algebra . Jim Hefferon. (Great)

Haskell:
        Arrow and compuation. Ross Paterson

(2009 Nov 12)
Motivation : combinator completeness
        The Church-Turing Thesis
                http://plato.stanford.edu/entries/church-turing/
        Combinatory logic
                http://plato.stanford.edu/entries/logic-combinatory/
                It's quite long, but at least, there is an algorithm to convert from lambda to point-free.

        http://plato.stanford.edu/entries/recursive-functions/
               This means : with
  • zero(x) = 0, 
  • inc(x) = x+1, 
  • Prj(i, x1,x2,x3...) = xi , and function composition:
  •  ƒ(x1,…,xn) = g(h1(x1,…,x n), … , hm(x1,…,x n))
       we can build a whole class of functions, which is supposed to all Turn-machine calculable.
Thus point-free is complete.




Automatic Theorem Prover : Prover9, ACL2,
Logic for application : Anil Nerode

REST:
http://www.ics.uci.edu/~fielding/pubs/dissertation/fielding_dissertation.pdf

To read:
        Designing and Using Combinators: The Essence of Functional Programming
                http://www.cs.chalmers.se/~rjmh/Combinators/
        Algebra, abstract algebra, universal algebra, topological algebra, algebras
        constructive mathematics
        intuition mathematics

  

Sunday, April 26, 2009

divide by zero and Gauss elimination

when applying Gauss elimination, the algorithm could be simplified if we define a divide by zero class.

given a matrix m =

2 2 0 0
0 -1 3 3
3 -2 -1 3

1) we Unitify each row by divide it's column 0 .

1 1 0 0 row 0 divide 2
0/0 -1/0 3/0 3/0 row 1 divide 1
1 -2/3 -1/3 1 row 2 divide 3

2) row 1 and row 2 minus row 0

1 1 0 0
0/0-1 -1/0-1 3/0-0 3/0-0 row 1 - row 0
0 -5/3 -1/3 1 row 2 - row 0

3) apply 0 * to row 1 .
row 1 becomes
0 -1 3 3

here we define x/0 * 0 = x , and x / 0 + y = x/0 ( because when you apply 0* to y , you get 0 )