Developments in Language Theory 2010: Where tetration has lease

Tomorrow I’m leaving for Canada, to attend the 14th International Conference on Developments in Language Theory, held at University of Western Ontario, London. You can find the programme here.

Our DLT 2010 paper, authored by yours truly, Alberto Leporati and Claudio Zandron, is titled On a powerful class of non-universal P systems with active membranes. In it, we describe a restricted variant of P systems with active membranes (computing devices inspired by biological cells) that is not Turing-equivalent, but nonetheless decide a surprisingly large class of languages. This class also seems to be somewhat “new” (we haven’t been able to find any reference to it in the literature).

Consider the operation of tetration (iterated exponentiation), defined as

{}^n b = \underbrace{\,b^{b^{b^{\cdot^{\cdot^{\cdot^b}}}}}}_{\text{\emph{n} times}}

and call PTETRA the class of languages decided by Turing machines working in time {}^{p(n)}2 for some polynomial p (the P in PTETRA signifies the fact that exponentiation is iterated only polynomially many times instead of, say, exponentially many). This class is trivially closed under union, intersection, complement, and polytime reductions. Furthermore, it’s easy to see that it can also be defined in terms of space {}^{p(n)}2 (you can also throw in nondeterminism, if you really want to).

Well, the main result of our paper is the following funny theorem.

Theorem. The class of languages decided by our variant of P system with active membranes is exactly PTETRA.

The proof works like this:

  • The upper bound is proved by a few calculations that show how our P systems can never use more that tetrational space, because the process of membrane division (which generates lots of new membranes) must stop after a finite number of steps.
  • To prove the lower bound, we show that we can simulate with our P systems all tetrational-space counter machines, hence tetrational-space Turing machines.

The result is somewhat unexpected, as I was under the impression that all we could do with these P systems was EXPSPACE, and indeed I wasted a few days trying to prove that. Fortunately, reality turned out to be much more interesting.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s