mxgmn / MarkovJunior

Probabilistic language based on pattern matching and constraint propagation, 153 examples
MIT License
7.53k stars 317 forks source link

This is turing complete #63

Open CrispyPin opened 6 months ago

CrispyPin commented 6 months ago

The README states

We lose Turing completeness because our new procedure is not deterministic, but practice shows that this formalism still allows to describe a huge range of interesting random processes.

But you can create a deterministic system with strict enough patterns.

Example of conways game of life in an async CA https://www.youtube.com/watch?v=oXiqMGhn9rk&t=749s

Rule 110 (which is turing complete) implemented in MarkovJunior:

https://github.com/mxgmn/MarkovJunior/assets/54243225/8e8aa845-fa32-428f-9392-0173e338e5ab

rule_110.xml

mxgmn commented 6 months ago

That is an interesting question indeed! I'm a little swamped at the moment, but I'll answer as soon as I have time.