A blag containing my current adventures in logic, haskell and agents.

Monday 28 June 2010

Linking Interaction Nets and Post Canonical Systems

And one more update due to a paper I wrote for the Models of Computation course. I'd like to attend you all to a very beautiful model of computation called interaction nets. One application this model is used for is to optimally implement lambda calculus in a certain theoretical sense.

The paper I wrote connects the Post correspondence problem (PCP) to interaction nets, by reducing PCP in a number of steps to an interaction net and giving some suggestions for the other way around. (Thereby proving interaction nets at least Turing complete, and leaving the suggestion for Turing equivalence.)

The reverse proof is much more involved, needing multiple reduction steps, possibly through the chemical abstract machine I referenced.

I hope some of you will be inspired by interaction nets.


You can find the paper here.

Slides Church-Turing Thesis and Gödels Incompleteness Theorems

A pair of slides this time. Again for Models of Computation I held a presentation, this time about the Church-Turing Thesis and some interesting variants of it. As a computer scientist one should really know the general ideas surrounding it.

And finally slides for a Philosophy of AI course about Gödel's Incompleteness Theorems (mostly the first theorem). In the slides I tackle some possible misconceptions when interpreting the theorem and try to convince you that Gödel's Incompleteness Theorems, although very interesting, are not very usable in a philosophical argument, but can be used as a starting point for devising new philosophical theories.


I hope you'll find it interesting and comments are always welcome.

The slides for the Church-Turing Thesis can be downloaded here.
The slides for Gödel's Incompleteness Theorems can be downloaded here.

Slides Church-Turing Thesis (MoC)


Slides Gödels Incompleteness Theorems


The slides for the Church-Turing Thesis can be downloaded here.
The slides for Gödel's Incompleteness Theorems can be downloaded here.

Followers