ACT-R

My second presentation for the course of "Models of Computation" investigated the ACT-R framework. This is actually a  very popular and interesting model of human cognition. It simulates, with the employment of modules, the functionality of fundamental brain parts.

    The idea behind the presentation was to introduce the model, then link it to Turing Machines and optionally to Post's Correspondence Problem. Since the connection of ACT-R to PCP is not possible, the corresponding slides are small in number. In order to compensate for that I investigated and presented the connection of ACT-R to Neural Networks (ACT-RN model).

ACT-R

1. HolgerSchultheis, "Computational and Explanatory Power of Cognitive Architectures: The Case of ACT-R “.J. R. Anderson, D. Bothell, M. D. Byrne “An Integrated Theory of the Mind”, (2004), Psychological Review, Vol. 111, No. 4,
2. John R. Anderson, “How Can the Human Mind Occur in the Physical Universe?” (2007),Oxford University Press
3. C. Labiere, John R. Anderson, “A Connectionism Implementation of the ACT-R Production System” (1993),In Proceedings of the Fifteenth Annual Conference of the Cognitive Science Society

Post's Correspondance Problem

This is a presentation I did about Post's Correspondence Problem for the "Models of Computation" course in 2011.

   The presentation starts by giving an introduction to the problem itself and then showing its Turing completeness using  M.Sipser’s proof from“Introduction to Theory of Computation”. I spent a lot of time on understanding and visualizing it so I think it's worth it. Later in the presentation slides I present some methods for proving the insolvability of some PCP instances,  using knowledge from L. Zhao's. “Tackling Post’s Correspondence Problem”.

 

Post's Correspondence Problem

In retrospect there might be some things I would have changed in it; however I believe it has a nice smooth flow from simple notions to formalizations.

1.Michael Sipser, "Introduction to the Theory of Computation" (2nd edition), Thomson Course Technology, (2005).
2.Ling Zhao, “Tackling Post’s Correspondence Problem”, (2003).