Bevezetés a membránszámítások elméletébe

Ebben részben ugyancsak az élő sejtekkel kapcsolatos számítási modellt veszünk, a membránszámítások viszont csak a motivációt tekintve rokonok az élő sejt folyamataival, maguk a számítások elvont modelleket használnak. Az „in-vitro”, sejten kívüli DNS-számítások alapjai és a csillós egysejtűek génképzési folyamatának modellezése után most nézzünk egy másik számítási modellt, amihez az élő sejtek működése adta a mintát. Ebben a fejezetben, tehát a membránrendszerekkel, mint absztrakt számítási modellekkel fogunk részletesebben megismerkedni. A membránszámítások (Membrane Computing) fogalma Gheorghe Păun nevével kötődik össze, ezért a membránszámítógépeket P-rendszereknek (P-systems) is szokták hívni. Tulajdonképpen a számítástechnikának ez az ága e könyv írásakor még csak 15 éves.

A membránrendszerek a számítások egyféle, a természet, mégpedig a biológiai membránok néhány jellemzője által motivált modelljei. A membránrendszerek objektumok multihalmazaival dolgoznak. A membránrendszer strukturált, a membránokhoz „reakció-szabályok” tartoznak, amik maximálisan párhuzamos, nemdeterminisztikus módon alkalmazandók. Az objektumok áthatolhatnak a membránokon, a membránok töltése, vastagsága (áthatolhatósága) változhat, membránok megszűnhetnek, illetve osztódhatnak. Ezeket a jellemzőket használhatjuk a rendszer konfigurációinak, átmeneteinek és magának a számításnak a definiálására. Rengeteg variációját definiálták már ezeknek a rendszereknek, a legtöbb ezek közül univerzális, vagyis számítási ereje megegyezik a Turing-gépével. Ezzel szemben köszönhetően a párhuzamos működésüknek, illetve, hogy akár exponenciális tárhellyel is dolgozhatnak, bonyolult (NP-teljes, vagy akár PSPACE-teljes stb.) problémák is hatékonyan oldhatók meg (lineáris, polinomiális időben) segítségükkel.

Most az alapötletet és néhány membránrendszer (és a velük történő számítások) néhány alaptulajdonságát fogjuk kicsit részletesebben megvizsgálni.