Dusko Pavlovic will run an informal weekly seminar on monoidal computer on Fridays from 11-12 noon in ASECOLab (POST 311). He describes it as follows:
If anyone is interested in a
- diagrammatic model of computation
- that lets you prove things about computability, complexity,
- randomized computation, one-way functions
- central dogma of (program) evolution
- and more
- all entirely in pictures
then please join us!
I will begin with a very quick introduction into semantics of computation, spell out the graphical language of monoidal computer, and then proceed towards one of the applications developed so far, depending on participants’ interests and my focus.
Monoidal computer has evolved as my answer to the following questions:
Why is it that the practice of computation is mostly driven by high level programming languages, but the theory of computation is still done in low level machine languages of turing machines, boolean circuits etc?
Why is there no high level view of cryptography? (this has a practical impact: people describe their algorithms in english, which leads not only to misunderstandings and errors in implementation, but also to substantially erroneous proofs.)
I use the tools developed in semantics of programming languages to try provide such a view. I will try to reach the point where we can define one-way and trapdoor functions. this requires capturing feasible randomized computation modulo computational indistinguishability.
Another direction is to define a von Neumann-style model where genes are programs, organisms are computational processes (but with resources, not just with data), and to try to explain algorithmically the central dogma of evolutionary genetics: that the dynamic adaptations acquired by an organism cannot be inherited. wouldn’t evolution be more efficient if they could? Why was LaMarck wrong?