Post #824348

Two years ago in connection with SAT-solver optimization of cascading stylesheet files (https://mathstodon.xyz/@11011110/112112644240620023) I briefly mentioned the possibility that CSS might be Turing-complete, with a link to some attempts at demonstrating this via simulation of the Rule 110 cellular automaton (https://stackoverflow.com/questions/2497146/is-css-turing-complete). But these attempts were unsatisfactory for a couple of reasons: Rule 110's completeness requires an infinite array of cells and a mostly-repeating pattern of initial cell values, the demonstrations had only finite arrays of cells of fixed size implemented as html objects, and each step of the simulation required some user interaction. But since then Clement Cherlin has found a better solution (https://mooninaut.github.io/css-is-turing-complete/): a CSS Turing machine simulator whose only interaction requirement is that you move the mouse to a starting position within 5 seconds of opening the page. It still appears to use html elements as tape cells, so the tape has a predetermined size, though. Having a fixed and finite tape is less of a problem for Turing machines than for Rule 110. You can still do arbitrary computations for which you already know how much tape you're going to need (which I guess can be described as Turing completeness). But determining whether the computation terminates is not an undecidable problem, because with a fixed tape size the total number of machine–tape states is finite.