Hacker News new | ask | show | jobs
by kaba0 646 days ago
> That is because CSS is a different Chomsky Grammar than HTML and EMCA - intentionally not Turing complete, nor-self referential - why the "has(" puedo property was so problematic.

It will be a nitpicky comment, and I’m sure you mean it this way, but it wasn’t clear to me: a language’s syntax being in one type of grammar class is irrelevant to its execution semantics corresponding to a recognizing automaton. So you can have a language with a regular syntax that is Turing complete just fine.

In fact, most languages’ syntaxes are context-free (sometimes with some escape hatches), but are semantically Turing-complete.

1 comments

  nitpicky comment,
I even put an asterisk! Oh wait, not the usual "unlimited tape finite universe"

I was unclear. It is intentionally not Turing Complete, by way of avoiding self-references, as self-references would make it a higher-order grammar, and Turing-complete because it then it can innately loop, making it impossible to flatten to a lower, Labeled Push down automaton.

Although they are mutually exclusive, I implied causality.

Its the implicit loop and requirement of a heap/stack of variables self-referencing requires that is Turing-Complete itself.