Models and Properties of Abstract Symbol Systems

Abstract

In this article we discuss properties of the abstract symbol system - a computational device proposed in [3]. We define two formal models of the abstract symbol system based on classical computational devices and study their complexities. We prove the properties of the class PP that is suggested to be an invariant class for our device. Our models are shown to be superior (in terms of the computational complexity) to the devices they originated from.  We deal with properties of complexity measures introduced for the abstract symbol system, namely computational and descriptional complexities. We prove the possibility of improvement in computational complexity for any function bounding the descriptional complexity.