Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

For those interested in the subject, the field that formalises the computation of chemical-reaction-like grammars is called P systems (or Membrane Computing) [1], which are known to be super-Turing devices [2].

Well, given the resistance to accept the practicality of super-Turing devices, a simpler model exists, MP systems [3], with simplified semantics and practical for biological applications.

MP systems are proved to be Turing-equivalent and there is a nice paper [4,5] (shameless promotion) that shows how to convert each type of "chemical reaction equation" into basic, sequential "assembly" (set of instructions for register machines).

In [5], a compiler and a simulator is implemented, but the source code is not yet available (I will eventually do so).

[1]: http://ppage.psystems.eu/

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

[3]: http://www.scholarpedia.org/article/Metabolic_P_systems

[4]: https://link.springer.com/chapter/10.1007/978-3-319-28475-0_...

[5]: https://arxiv.org/abs/1505.02420



Please explain to me how these systems can solve the Halting problem --- Everything I've tried to find on "Hypercomputation" has either been philosophical, or computability theorists playing with halting oracles for fun. I don't know of thing that seriously claims that hypercomputation is /physically realisable/.


I am very sorry, but I cannot: I am not an expert in super-Turing P systems.

(I can answer questions on MP systems, however.)

On the other hand, there are two papers that can answer your questions:

1. Bio-steps beyond Turing [1], from Calude and Pǎun.

2. Membrane system models for super-Turing paradigms [2], from Gheorge and Stannet.

From [2], referring to [1], there is this excerpt that might interest you:

> Calude and Pǎun (2004) introduced the first super-Turing model of computation rooted in biology rather than physics, and it is this work that we extend in this paper; their model also uses accelerated computation to solve the Halting Problem (and others), based this time on the observation that reaction rates are essentially proportional to molecular concentrations, and hence inversely proportional to the volume of the containing compartment when the number of molecules remains constant.

[1]: https://researchspace.auckland.ac.nz/bitstream/handle/2292/3...

[2]: https://www.researchgate.net/profile/Mike_Stannett2/publicat...


You left out the part where the paper states that it's still an open problem whether hypercomputation is physically realisable.

If some device can solve the Halting Problem, then it can solve every single unsolved mathematical conjecture that can be encoded as a Turing machine that halts if the conjecture is true (so about all of them?). This is an insanely bold claim, so please forgive the scepticism.


> This is an insanely bold claim, so please forgive the scepticism.

I am interested in the concept of hyper-computation and I would like it to be physically constructable, but in the present moment I also see it as an intellectual construct only.

Thus, I am as sceptical as you. :)

If, someday, super-Turing devices will be built, I imagine it will (first) come as analog devices (e.g. Siegelmann's Analog Neural Networks [1,2]), not as biological ones.

But this discussion is slightly off-topic, I guess.

[1]: https://binds.cs.umass.edu/anna_cp.html

[2]: https://www.researchgate.net/profile/Arthur_Younger2/publica...


It was not my intention to argue that the entire concept will never fly (I'm nowhere near qualified for that), nor that it shouldn't be researched. It's just that the post by bollu that you've responded to specifically asked if this is physically possible, and the paper you linked quite clearly answers "we have no idea yet".

Personally, I wouldn't be actually all that surprised if mathematics and computer science ended up solved some day by a system of chemical membranes, since, to put it extremely crudely, it was developed by systems of chemical membranes in the first place ;) That would raise some serious philosophical questions, though.




Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: