Hacker News new | past | comments | ask | show | jobs | submit login

While I question the tone of the original post, it is correct.

The difference between being Turing complete and implementing rule 110 is crucial, and any discussion on the subject needs to make clear that these are not the same.

You are obfuscating the role of the driver. In the Turing machine, the driver is part of the Turing machine. In CSS, it is not, and has to be done by the user (or presumably a JS script).

As another post by Grue3 points out, almost any language can implement rule 110, including languages that are not Turing complete, and are explicitly said not to be Turing complete in the CS literature/community.

For example, Coq, Agda, Idris (with totality checking) and other languages based on Martin Lof type theory, are not Turing complete. That it why they are able to prove totality of their functions. But they can all implement rule 110 with no problem.




Just some more on dependently typed languages: The article actually mentions them in footnote 1. So as it stands, the CSS part really doesn't make sense, because everything written about CSS applies to these dependently typed languages.

In particular, you could write some Agda/Coq/Idris program that implements rule 110, and has some trivial user interaction to repeat this until a stable pattern is reached. This simulates a Turing machine.




Join us for AI Startup School this June 16-17 in San Francisco!

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

Search: