Comment by bidirectional | Hacker News Reader

Comment by bidirectional | Hacker News Reader

I disagree that this proves the Turing completeness of CSS. Part of the definition of Turing machines is access to unbounded memory. In Python, for example, we meet this requirement by saying that any underlying request to new memory will succeed, or we can imagine an implementation of Python without a stack limit and lambda-encode everything. Ultimately, Python as an abstract language has no memory limitations, that's just an artifact of us implementing it on real-world machines. The same could be said for Haskell or Javascript.

CSS on the other hand (or at least the encoding presented here), requires us to state upfront, in the CSS file, how many cells we need. This is equivalent to non-Turing complete finite state machines. If we must encode memory bounds in the program, we can solve the halting problem, can't translate certain Python programs, can solve the Busy Beaver problem via a lookup table, etc. One of the main goals of Turing when defining computability was describing potentially infinite processes with a finite language.

That's getting pretty technical. It can execute Rule 110, therefore it's Turing Complete because infinite memory is impossible. Stating how many cells you need beforehand (using `<input type="checkbox"/>`) isn't much different from stating that my laptop only has 16 gigabytes of RAM. Sure, you need to encode that beforehand, but so do the RAM modules.[a]

[a]: This is usually accomplished with a tiny SOIC-8 IC on the module (see the middle of the top of [0])

[0]: https://upload.wikimedia.org/wikipedia/commons/d/db/Swissbit...

Without speaking for the OP, it seems like the case being made is not that the result is executed on a real, finite machine approximation (as all programs are) but that there exists an abstract Python machine wherein the memory does not need to be so described. This does not exist for CSS.

Why not? I can imagine a modified abstract css machine which applies the styles to an infinitely long html document. That's much more contrived than the python case, but if we are going to be making arbitrary changes from finite machines, im not sure under what basis we would draw the line.

The html document is potentially infinite, but its finite length is not encoded in the program (css).

One idea is, to have the same program, and if it terminates, it will terminate if you pick a large enough machine. You don't need to "rewrite" the program to use a larger machine.

So in this case the html document is the tape. Potentially infinite, but not in reality. The css program may handle it as infinite.

>that there exists an abstract Python machine wherein the memory does not need to be so described

This is getting a little esoteric. Python interpreters are created in other languages like C where memory does need to be described. How can this 'abstract Python machine' even be implemented? Python or any higher level interpreted language will always have the same limitations of the language it's implemented in and like anything we do on modern computers, can be reduced to assembly where again memory has to be 'described'. Python may hide it for us but it's there.

>How can this 'abstract Python machine' even be implemented?

It wouldn't be - the machine is abstract. It exists only in terms of a mathematical model, that describes how Python code behaves in a defined mathematical way (its semantics). The real implementations of Python should have the same behaviour as the abstract machine, but the property of Turing-completeness really only exists for the abstract version - the real versions, being bounded in memory, are limited to certain sizes of programs.

Actually, I thought you don’t even need unbounded memory because it’s proven that the register machine [0] with limited memory is still Turing complete.

[0] https://en.wikipedia.org/wiki/Register_machine

Abstract register machines are normally considered to have infinite memory - because even though the number of registers can be bounded, their size is often not. Unlike the fixed-width registers of a real CPU, abstract registers are typically capable of storing any positive integer.

I’m aware and that’s how they are usually introduced. However, there’s also the model of such that have a further restricted set of instructions and only have limited memory.

Could you please give a reference for such a model, and the proof that it's Turing complete? I don't see it described on the Wikipedia page, which explicitly states that registers are unbounded.

This still proves that CSS layout algorithms are O(EVIL).

Enumerating and memoizing all possible states will still be impractical, even for small machines.

(This is also why C is not Turing complete.)

Does there exist any formal terminology for "something that is like a Turing machine if it would have infinite memory"?

I'm asking because since the true definition of a Turing machine requires infinite memory, in theory nothing can be a Turing machine in the observable universe, so this definition doesn't help describe anything that's used in practice.

On the other hand, there's an obvious difference in power of a language like C, versus non Turing-complete languages like regexp. So it's useful to talk about this concept, but we could never formally call any of those Turing complete (C pointers are limited to so many bits, for example).

The discussion about this detail comes up every time, so is there some proper formal term for this?

Something related to how much code is required to use the finite pool of memory you have in any way you want, or so (where a non turing complete language may require enumerating all possibilites and thus too large code size)

You can assume that, if the machine runs out of memory, that someone comes along and installs another gigabyte and sets it going again. Predicting whether programs will halt under those conditions is exactly the same as if they really had an infinite tape.

It's a bit tricky with real programs because eventually you might expect you'd run out of address space, so you might have to relax constraints and say that at least some integer types don't have a defined maximum value, or stuff like that.

It is Turing complete if you access the tape using something like fread/fwrite.

Reply on news.ycombinator.com