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.

Index Structures for Multimedia Databases

Here is a paper assignment I had to do for the "Query and Retrieval" course in 2011. The topic is "Index Structures for Multimedia Databases" which I found very interesting. I initially thought that there wouldn't be so much research going on in the field, but I was proved wrong.

Index Structures for Multimedia Databases

ABSTRACT

In this document we address the issue of index structures for multimedia objects. Video, audio and other inhomogeneous formats contain such amount of varying information that cannot be efficiently organized using conventional database techniques. However, fast accessing, response times and efficient sharing are keys issues when it comes to multimedia, due to their rapidly growing commercial and practical applications. An overview of the current drawbacks and limitations of typical index structures will be initially discussed. We will also investigate in which ways the multimedia storage issue can be transformed to the high-dimensional indexing problem. Most of the paper though is focused in presenting a series of generalized 1D and 2D structures while also algorithms specially designed for complicated data.

After I handed in the assignment I stumbled upon other methods such as VA-index; overall the paper contains lots of information and is well written.