[HN Gopher] Ask HN: Anyone here working on/with membrane computing?
___________________________________________________________________
Ask HN: Anyone here working on/with membrane computing?
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.
Author : netfortius
Score : 46 points
Date : 2023-01-25 13:21 UTC (9 hours ago)
| [deleted]
| nextos wrote:
| Luca Cardelli, who is quite famous in formal methods, did a lot
| of work in the area during the early 2000s:
| http://lucacardelli.name
| mikewarot wrote:
| 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
| mindcrime wrote:
| 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.
| ElevenLathe wrote:
| 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!
| 082349872349872 wrote:
| regarding https://en.wikipedia.org/wiki/P_system#Rules , cf
| https://en.wikipedia.org/wiki/Tuple_space
| guiraldelli wrote:
| 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 Paun, 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...
| netfortius wrote:
| 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.
| jsenn wrote:
| 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.
| fdupress wrote:
| Space might be a good enough approximation of energy to not
| bother?
| pubby wrote:
| 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.
| cvccvroomvroom wrote:
| 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.
| mindcrime wrote:
| _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
| al2o3cr wrote:
| 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...
___________________________________________________________________
(page generated 2023-01-25 23:01 UTC)