Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Alchemist – A non-deterministic programming language based on chemical reactions

esolangs.org

Post reply on HN
Print view View original

11–20 of 29 posts

Re: Alchemist – A non-deterministic programming language based on chemical reactions

#11

Post by a-nikolaev »

andolanra wrote: post #5

After poking around the site, I can't see any specific reference—which makes me suspect it was an independent discovery of a cool idea—but this is very similar to a deliberately-constrained version of the Join Calculus https://www.microsoft.com/en-us/research/wp-content/uploads/... which uses a similar chemical-ish model of computation. There's an implementation of the Join Calculus in an OCaml-like language called (…

Yeah, Stochastic Pi-calculus and chemical reaction networks simulators are doing this this too. They actually precisely define the probabilities of reactions based on the current amount of different molecules and their reaction rates. For instance, I used the tool called Beta Workbench (BetaWB) and hand-written simulators for modeling systems like this. It's a really cool computational model, I think.

Re: Alchemist – A non-deterministic programming language based on chemical reactions

#12

Post by nickodell »

dmos62 wrote: post #3

I don't understand the meaning of nondeterminism in this context. Definition of a nondeterministic language from the linked wiki: > Languages with significant operations (such as execution order) that are predominantly nondeterministic; the same answer cannot always be expected in the same circumstance. What are the significant operations in this language that cannot always be expected to produce the same result?

If you have two rules like this:

    H -> O
    H -> 2O
then the interpreter will pick one at random. It is possible to write entirely deterministic programs, but some programs are non-deterministic.

Re: Alchemist – A non-deterministic programming language based on chemical reactions

#13

Post by afpx »

andolanra wrote: post #5

After poking around the site, I can't see any specific reference—which makes me suspect it was an independent discovery of a cool idea—but this is very similar to a deliberately-constrained version of the Join Calculus https://www.microsoft.com/en-us/research/wp-content/uploads/... which uses a similar chemical-ish model of computation. There's an implementation of the Join Calculus in an OCaml-like language called (…

Here's the author's github with the reference implementation.

https://github.com/bforte/Alchemist

Re: Alchemist – A non-deterministic programming language based on chemical reactions

#14

Post by pacaro »

a-nikolaev wrote: post #11
andolanra wrote: post #5

After poking around the site, I can't see any specific reference—which makes me suspect it was an independent discovery of a cool idea—but this is very similar to a deliberately-constrained version of the Join Calculus https://www.microsoft.com/en-us/research/wp-content/uploads/... which uses a similar chemical-ish model of computation. There's an implementation of the Join Calculus in an OCaml-like language called (…

Yeah, Stochastic Pi-calculus and chemical reaction networks simulators are doing this this too. They actually precisely define the probabilities of reactions based on the current amount of different molecules and their reaction rates. For instance, I used the tool called Beta Workbench (BetaWB) and hand-written simulators for modeling systems like this. It's a really cool computational model, I think.

Adding relative weights to each rule would be a simple extension to the grammar. If only integer weights were permitted it could be a simple preprocessor.

Re: Alchemist – A non-deterministic programming language based on chemical reactions

#15

Post by guiraldelli »

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

Re: Alchemist – A non-deterministic programming language based on chemical reactions

#16

Post by bollu »

guiraldelli wrote: post #15

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…

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/.

Re: Alchemist – A non-deterministic programming language based on chemical reactions

#17

Post by guiraldelli »

nrf1 wrote: post #9
munk-a wrote: post #8

If we have the rule 2H + O -> H2O and the universe consists of 3 H and 2 O atoms, then the rule is applicable. After applying the rule our universe will contain 1 H2O, 1 H and 1 O atoms. At this point the rule would not be applicable anymore. If we have the rule Alice + Bob + 0Eve -> AliceBob and the universe contains 1 atom of each Alice, Bob and Eve. Then that rule is not applicable because it requires the universe…

> I am not certain how it'd be best to define a rule that predicates on an absence of a token but that syntax is terrible. That would be pretty confusing. Instead, transitions can always be allowed to happen if the left hand side is satisfied and then the "don't transition if there's an Eve" semantics -- when necessary/desired -- can be made explicit by adding assertions to each nondeterministic transition. For examp…

I think a set of two equations is enough:

    Eve + AliceBob → Alice + Bob + Eve
    Alice + Bob → AliceBob
I understand with non-deterministic behaviour and 10 Alices, 10 Bobs and 10 Eves I can get in a certain state (Alice, Bob, Eve, AliceBobs) = (1, 1, 10, 9), but if we stick to the evaluation order defined by the language, then the two rules above satisfy the condition.

Re: Alchemist – A non-deterministic programming language based on chemical reactions

#19

Post by guiraldelli »

bollu wrote: post #16
guiraldelli wrote: post #15

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…

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...

Post reply on HN