top | item 43811755

(no title)

a_cardboard_box | 10 months ago

Rule 110 is only Turing-Complete if you have an infinitely large array of cells, and are able to initialize it with an infinite repeating pattern. If I'm not mistaken, HTML+CSS can only do a fixed-sized array.

With a Turing-Complete language, if a program runs out of memory on one machine, you can run the same code on a bigger machine without modifying it, and it can use the additional memory. With fixed-length rule 110, you need to modify the code if you want to use more memory.

discuss

order

256_|10 months ago

This is addressed in the second paragraph of TFA:

"Stuff which is somehow limited (stack overflows, arbitrary configuration, etc) is still considered Turing complete, since all "physical" Turing machines are resource limited."

In my opinion, worrying about infinite memory, in regards to Turing completeness, makes the task of implementing computation much less interesting.

Also, I'm pretty sure CSS only does one generation (or a finite number of them) before stopping anyway.