Linking Post’s Correspondence Problem and ACT-R to Turing Machines

For the final part of the "Models of Computation" course I had to write a paper that would link ACT-R and Post's Correspondence Problem to Turing machines. However the idea behind it was to actually find the connection between ACT-R and PCP. This was not an easy task since PCP is undecidable and ACT-R requires a formalization of a problem-solving procedure. Hence I decided to give a brief, abstract ACT-R model implementation of the heuristic pruning method for solving PCP instances.

Abstract

The aim of this paper to present the relationship between Post’s Correspondence Problem, ACT-R and Turing Machines. For both cases we will simulate the elementary operations of a Turing machine, thus proving constructively their direct analogy, while also their similar capability of computing any functions which can be computed in principle. Moreover, this paper briefly attempts to link Post’s Correspondence Problem to ACT-R using a similar procedure.

Linking Post's Correspondence Problem and ACT-R to Turing Machines

Most of the ideas and methods presented in this paper do not belong to me (just in case people complain). I've cited everyone as it is proper.

1. E.L. Post. “A variant of a recursively unsolvable problem”, Bulletin of the American Mathematical Society, 52, 264-268, 1946.
2. L. Zhao. “Tackling Post’s Correspondence Problem”, 2003
3. M. Sipser.“Introduction to Theory of Computation”, 2nd Edition, Thomson Learning, 2006
4. H. Hoogeboom, W.A. Kosters, “Tetris and decidability”, Information Processing Letters 89, 267–272, 2004.
5. J.R. Anderson “The Architecture of cognition”, Cambridge MA, Harvard University Press, 1983.
6. J.R. Anderson “The Rules of the mind”, Hillsadale NJ, Erlbaum, 1993.
7. C. Labiere, J.R. Anderson “A Connectionist Implementation of the ACT-R system”, In Proceedings of the Fifteenth Annual Conference of the Cognitive Science Society, 1993.
8. H. Schultheis, “Computation and Explanatory Power of Cognitive Architectures: the Case of ACT-R”
9. Y. Rogozhin, “Small Universal Turing machines”, Theoretical Computer Science 215-240, 1996
10. Wikipedia “ACT-R”, en.wikipedia.org/wiki/ACT-R