Ask HN: Anyone here working on/with membrane computing? | Hacker News Reader

Ask HN: Anyone here working on/with membrane computing?

57 pointsnetfortius16 comments

Although probably late in this field, I have recently come across the topic, sourced/starting from an old paper by one of the main actors in this area, Gheorghe Paun ("An impossibility theorem for indicators aggregation"), who I then followed through to learning about Membrane Computing. I am planning to buy the introductory book on the topic, also authored by Paun, but not right away. I was wondering if there are individuals who could speak to the how and why, and maybe work on applications in this space.

View on HN

I have worked with it [1], in particular with a special class of it, MP (Metabolic P).

In a nutshell, it is a theoretical model inspired by biology, but which produces many interesting results, as super-Turing computational power.

I am not sure whether it is still, but the reference on web for the subject was http://ppage.psystems.eu/ .

Besides Păun, other big names in the topic are Perez-Jimenez, Gheorghe and Manca.

As far as I am concerned, there are little practical application of it, even though the theoretical potential is considerable.

I tried to focus on more day-to-day application of MP [2], and I managed to get some nice results, but further advance was limited by external forces.

Do I recommend to buy an introductory book on the subject? No, mostly because I think the material online from the people I mentioned above, plus their publication, is more than enough to acquire the knowledge. Besides, I bet the book is published by Elsevier, which usually mean it is a simple collection of papers, except the fact I am not fan of that publishing house.

If you have any more direct question, feel free to contact me—hopefully I can be of some help.

But, I have the impression that membrane computing is still a very academic topic disconnected from the engineering world.

If it is what you like, then it might satisfy you. :)

[1]: https://ricardo.guiraldelli.com/research.html#doctorate

[2]: https://ricardo.guiraldelli.com/research.html#available-mate...

This is interesting stuff--thanks for writing it out.

> ...super-Turing computational power.

Could you expand on this? The Wikipedia page claims that the deterministic version can be efficiently simulated by a Turing machine.

The Wikipedia page and page you linked claim that NP problems can be solved in linear time. It does point out the caveat that it would require exponential space, but I think even then something's being swept under the rug. Namely, it assumes that an exponential number of basic computational steps can be performed in a single "time step". In a physical cell (and presumably any other instantiation of this model in the real world), repeated application of a rule like a -> aa would require an exponentially-increasing expenditure of energy, which isn't being taken into account in the analysis.

Space might be a good enough approximation of energy to not bother?

Thank you! Very informational and kind of you to offer further assistance. I'm way too uneducated in this space, for now, to even assume I could produce pertinent questions.

https://en.wikipedia.org/wiki/Membrane_computing

https://en.wikipedia.org/wiki/P_system

https://en.wikipedia.org/wiki/Cell_membrane

Huh. Wasn't familiar with this before now. Looks very interesting though.

I come at this more from the (amateur) history of science angle (meaning I am in no way qualified to speak about recent work in this field) so take this with a grain of salt, but it all seems very much in the vein of Turing's late work "The Chemical Basis of Morphogenesis". Essentially, one of the first things Turing did when he had regular access to a real computer (and not some lashup being used to break German ciphers) was to use it to simulate how life might arise from ordinary chemical reactions. In other words, Turing himself was using a Turing machine (well, a Ferranti Mk 1 I think, so more of a Von Neuman machine) to simulate what ended up being the path to "super-Turing" models of computation!

regarding https://en.wikipedia.org/wiki/P_system#Rules , cf https://en.wikipedia.org/wiki/Tuple_space

In a somewhat-related area, Alan Kay viewed object-oriented programming as cells (objects) and their transport proteins (messages). Like biology, the system is a big ugly mess, but it's made up of tiny self-contained units that can handle themselves. The actor model continues this idea, but usually drops the connection to biology.

The claims of "solve NP problems in linear time" appear to come with a giant gotcha: they involve allowing the number of membranes to grow exponentially with the problem size! For instance, see:

https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researc...

This seems like a huge problem for any electronic representation, since most any computational approach will deliver "super-Turing" results if you allow the machine to grow faster than the problem...

This seems to be a special case of a computational fabric.[1] If you reduce computation to the barest minimum, you get down to a cartesian grid of 4 input 4 output Look Up Tables (LUTs). If you clock them in alternating phases, like colors on a checkerboard, you avoid all race conditions, and get deterministic general purpose computing which can run this type of algorithm.

I was reading George Gilder back in the 1980s when that idea hit me, and its been in the back of my brain ever since.

[1] https://en.wikipedia.org/wiki/Fabric_computing

Similar to VM emulation, the problems with electronic or Turing simulation of chemical and biological processes are many. Simulating a sea of neurons or organelles doesn't tend to scale well without using actual organic processes.

I wouldn't bother without a specific need that can be accelerated with biochemistry directly. Turing completeness can't be improved on.

Turing completeness can't be improved on.

Are we sure of that though? I thought it was the case that the Church-Turing Thesis[1] was "widely considered to be true" but had not been, in the strict sense, proven. If so, doesn't that leave open the at least the possibility of Hypercomputation[2] as a real thing?

[1]: https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis

[2]: https://en.wikipedia.org/wiki/Hypercomputation

Meh, I obviously can't say anything definitively without hard proofs, but to me it feels similar to how P != NP is assumed to be true.

As in, one can dream, but don't get your hopes up that we will even ever find out if the boring answer turns out to be true.

From a distance, this type of "biological" computing just looks "very massively parallel" to me.

And as in the Iota language, you only need the X combinator to do everything. (Sorry YC.)

What does a "hyperprogram" look like?

What "problem" does a "hypercomputer" solve?

If you can find a real P solution to Travel Salesman without redefining big O complexity or inventing magical computing, I'll give you a billion dollars.

Luca Cardelli, who is quite famous in formal methods, did a lot of work in the area during the early 2000s: http://lucacardelli.name

Reply on news.ycombinator.com