11
My question comes from the following implementation of Rule 110 in CSS (Yes! In CSS!).
The doubt comes from the definition of Turing completeness, which says that a system is Turing-complete if it is capable of solving any computational problem. However Rule 110 is used to test this hypothesis and CSS apparently passed.
But, I can’t do so much with CSS (maybe because my knowledge is limited... in which case, it would be extremely limited).
1
I would like to know more about the Rule from a practical point of view.
Well, Automaton 110 is, in short, a cellular automaton with very simple rules, and yet it’s quite versatile - after all, it’s Turing-complete. With this, the Turing completeness of a given system can be demonstrated by simply emulating a 110 automaton on it. In this sense, there is nothing deeply special about this automaton.
It’s like asking "can I build an Assembler for the x86 architecture using this programming language?". Only the x86 manual is huge - over two thousand pages! So it’s (theoretically) easier to use a simpler language.
A strong candidate is the Brainfuck language. Let’s try to hypothetically reformulate your question in Brainfuck:
My question comes from the following implementation of Rule 110 in Brainfuck (Yeah, in brainfuck!).
The doubt comes from the definition of Turing completeness, which says that a system is Turing-complete if it is capable of solving any computational problem. However Rule 110 is used to test this hypothesis and Brainfuck apparently passed.
But, I can’t do so much with Brainfuck (maybe because my knowledge is limited... in which case, it would be extremely limited).
Looking like this, it doesn’t seem like a deep demerit not knowing how to program in Brainfuck. On the contrary, it is easier to build a program that transpile C to Brainfuck. I still don’t completely understand this Quicksort made in Brainfuck!.
My practical point of view on this is: "Nice curiosity, but never in life I will use this". CSS will continue in its web page configuration niche, and surely we won’t see an operating system made in CSS anytime soon.
Going straight to your question, the idea is that Rule 110 describes a machine with few rules and easy to understand, so the rule can be used as a test of the capabilities of a language.
1
No, there’s also the Game of Life which can be used to know if the system is Turing-complete.
It may be a good way to identify a language such as Turing-complete using Rule 110 due to its universality.
For example if we have a computational function S that for program P receives an entry X S(P,X) then P will stop when it reaches X, and if S(P,X) stops then its result will always be similar to from P to X. Rule 110 - English
Rules 30 and 90 do not know whether they are universal or not.
Browser other questions tagged computer-science
You are not signed in. Login or sign up in order to post.
Thanks for the comment, but I re-asked my question, because it’s not quite the answer I expect. I would like to know more about the Rule from a practical point of view.
– StillBuggin