This is good. A proof that current computing model isn't the only one for computation.
Appreciate for sharing your work.
Alchemist – A non-deterministic programming language based on chemical reactions
21–29 of 29 posts
Re: Alchemist – A non-deterministic programming language based on chemical reactions
#22This is good. A proof that current computing model isn't the only one for computation. Appreciate for sharing your work.
A feedback so that others will think clear before providing a comment, because I saw lot of comments asking for proof on how your project is better, whether it is computationally correct or not.
Here is my suggestion. Let me know whether it makes sense or i misunderstood the project. I tried my best to explain it, please don't hesitate to correct my understanding.
Wiki page can have an introduction in form of an animated video or images that depicts comparison between typical computing model and yours.
1. What's the current computing about ? - binary -> input (processing )output -> input + (neural processing) + output -> quantum.
2. How is your computing changed from that ? The way I see it, we can build and solve problems in a different paradigm.
Re: Alchemist – A non-deterministic programming language based on chemical reactions
#23Earlier quoted context omitted.
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…
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.
Re: Alchemist – A non-deterministic programming language based on chemical reactions
#24Earlier quoted context omitted.
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…
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...
Re: Alchemist – A non-deterministic programming language based on chemical reactions
#25Earlier quoted context omitted.
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 Network…
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.
Re: Alchemist – A non-deterministic programming language based on chemical reactions
#26Earlier quoted context omitted.
> 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.
> but if we stick to the evaluation order defined by the language
Is this true? According to the linked page:
"The program will continually pick rules at random from the set of applicable rules, until there are no such rules."
In your encoding, we could end up transition from state {3Eve, 1Alice, 1Bob} to state {3Eve, 1AliceBob}. I agree that, in the next time step, we might transition back to {3Eve, 1Alice, 1Bob}. But there are two problems with this formulation:
1. We often (in many domains always) really care about the intermediate behaviors of the model, not just the final state. Which means that an observation of the trace:
{3Eve, 1Alice, 1Bob} ~> {3Eve, 1AliceBob} ~> {3Eve, 1Alice, 1Bob}
2. We might end up back in the "right" state, but only for those two rules! In particular, we might not actually end up back in state {3Eve, 1Alice, 1Bob} after all if there are other transition rules. For example:
Eve + AliceBob → Alice + Bob + Eve
Alice + Bob → AliceBob
AliceBob + Eve → WEIRDNESS
{3Eve, 1Alice, 1Bob} ~> {3Eve, 1AliceBob} ~> {2Eve, WEIRDNESS}
One additional problem: this encoding is not equivalent to the guarded version if transitions can have side-effects (e.g., if transitions consume a global implicit "fuel" or some other abstract representation of cost).
Re: Alchemist – A non-deterministic programming language based on chemical reactions
#27Earlier quoted context omitted.
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.
Grammar yes, but sampling reaction with appropriate rates makes the choice of the next reaction a little harder than arbitrary selection.
The time to each possible event must be drawn from the exponential distribution (https://en.wikipedia.org/wiki/Exponential_distribution), and the event with the smallest waiting time fires next.
Re: Alchemist – A non-deterministic programming language based on chemical reactions
#28Nice. If you would combine '->' operator with copy element 'I' and terminator element 'O' you could manipulate the syntax with category equations ( pure impelementation here https://github.com/kummahiih/python-category-equations and if you like to think as cats and balls, then usage example here: https://github.com/kummahiih/python-domain-equations ).
Re: Alchemist – A non-deterministic programming language based on chemical reactions
#29Nice. If you would combine '->' operator with copy element 'I' and terminator element 'O' you could manipulate the syntax with category equations ( pure impelementation here https://github.com/kummahiih/python-category-equations and if you like to think as cats and balls, then usage example here: https://github.com/kummahiih/python-domain-equations ).
I mean the notion here is of type "connect this source to this sink". Source -> Sink. That kind of setting is called category in mathematics, but the notation is a bit clumsy and can be made a bit more clear by introducing those copy 'I' and terminate 'O' -symbols to the mix. The python library above does that and it could be perhaps possible to plug it into this syntax easily.