Models of computational devices represent one of the main
formalizations of the notion of computability.
Proceeding from Recursion theory to Complexity theory and
Algorithmics notions of time and space consumed during a
computation become relevant. These notions however are
highly model dependent.
Even with this machine dependence complexity theory has
obtained a solid foundation, since the various models
are found to be equivalent in their computational power,
provided they are compared on a sufficiently coarse scale:
the relevant comparison is given by mutual simulations
with polynomially bounded overhead in time and constant
factor overhead in space. The so-called Invariance Thesis
expreses our faith that there exists a class of reasonable
sequential devices, which all are equivalent if measured
on this scale, and which capture our natural intuition for the
realm of sequential computation.
An alternative class of models is formed by the parallel
models. Parallelism comes in many versions, and not all of
them have been shown to be equivalent the way the sequential models
are. A prominent subgroup among the parallel models is the
so-called Second Machine Class, consisting of
those parallel machine models that satisfy the parallel computation thesis.
These models are characterized by the right balance between exponential
growth pattern on the one hand, needed to make them PSPACE powerful,
and uniformity of behavior on the other hand in order to prevent
(in particular their nondeterministic version) to become too powerful.
There exist in the literature a number of sequential models
that have the property that they can recognize in polynomial time
exactly what a Turing machine can recognize in polynomial space.
These models therefore belong to the Second Machine Class.
Models of this sort have been studied in the literature
over the past 22 years.
In my talk I will present two examples of such models
which are not well known in the literature.
The two models presented in this talk share the property that they
are conceptually very close to the standard first class sequential
models which are computationally equivalent to Turing machines.
The first model, called the EDITRAM
is obtained as an abstraction of a text editor.
The second model is a parallel
version of the storage modification machine.
This model, called the Associative Storage Modification Machine
(ASMM) is the first machine model based on pointer manipulation which
achieves this complexity status.
The associative Storage Modification Machine obtains its computational
power from following pointers in the reverse direction.