How to prove computational completeness of a variant of P system

Question

I have read a lot of books on membrane computing (P system), of which the computational completeness of several variants are already under investigation. My goal is to design my own variant and prove its computational completeness.

I also know that in order to prove computational completeness many research papers normally prove the equivalence of their variants of P system with variants of formal languages (e.g. context-free, context sensitive languages, Turing machines etc.), those of which are already known to be computationally complete.

My question is how exactly can I prove equivalence of a variant of P system with a formal language?

Answer 1

When you have studied a lot of papers, as you say, then you must have seen how it works. You prove a system to be computationally complete by showing how your new system is able to simulate a Turing machine. Instead of a Turing machine you can use any computational model that in itself is computationally complete, like counter automata (register machines) for example.

In P system theory there are many variants, some work on strings, other on numbers. The model you choose to simulate ideally must match that domain.

So, you do not use "formal language" as such, but only the models studied by formal language theory.