Hacker News Reader

Comment by c-linkage | Hacker News Reader

Maybe it's time for me to switch to a text-only browser.

When CSS becomes Turing-complete it seems that even NoScript won't help me from nefarious web pages.

It is Turing Complete.[0] And before anyone says otherwise, Turing Completeness does not preclude a “crank” used in that post.

[0]: https://stackoverflow.com/a/5239256/1350209

That’s definitely not Turing complete. Not because of the crank, but the fact the exact number of memory cells is hard coded. I can run an n-cell Rule 110 simulation on a DFA, which is obviously not Turing complete.

The exact number of memory cells in your computer is also bounded.

Yes, but things we actually care and prove to be Turing complete are not. There’s no up front memory limitation in the lambda calculus or Javascript or Prolog.

But you can increase the “hard-coded” amount of memory in this CSS demo too.

To a finite amount, as part of the program itself. If I write a JS program that loops infinitely, pushing a number to an array, that will consume infinite memory by the standards of the JS spec. There’s no hard, upfront bound on memory.

If we can hardcode memory limitations in our programs, then every ‘uncomputable’ problem just becomes a lookup table.

Isn’t it somewhat arbitrary to draw lines between “the JS spec” (which might not directly specify any bounds on memory usage) and the actual specifications of any given machine running JS? I’m pretty sure JS tends to run on a 64-bit architecture, for example.

In fact, I’m pretty sure it’s not even true that “the JS spec” has no such limits. I’m reading that an array can’t be longer than 2^32. And apparently string length cannot exceed 2^53 - 1.

If we're going to be pedantic, then yes, no Turing Machines exist and everything is just a Finite Automaton. It's more helpful when talking about programming languages to assume an unbounded memory. For example, the desktop I'm at right now has only 16 billion memory cells (16 GiB), but I don't think of it as a Finite Automaton.

The linked StackOverflow answer does not preclude adding more memory cells. It was just capped at 900 for an arbitrary reason.

"Bounded Turing complete" or more accurately a "linear bounded automaton" is usually considered a practical enough form of Turing equivalency. No real-world computer is actually a universal Turing machine.

Turing completeness means literally nothing. It’s all about the APIs.

But JS is still required to for this to work, the title is a bit misleading

CSS is already Turing-complete if you set up an execution environment of some checkboxes and require user interaction to ‘advance the tape’: https://stackoverflow.com/a/5239256/453783

What does Turing completeness have to do with anything? Physical computers aren't even Turing complete themselves.

Under what definition is a physical computer not Turing Complete? The lack of infinite memory? That requirement would preclude literally everything but theoretical computers. It’s a lot more logical to talk in terms of “if there was infinite tape, would this thing Turing Complete?”

Brainf** is famously Turing Complete and can be executed on any desktop you can think of. That alone is enough to prove that your desktop itself is Turing Complete.

I think that the parent comment is actually supporting your point. It does not need to be Turing Complete to be extremely useful. Conversely, a model of computation (CSS) could be Turing Complete (with infinite memory, etc.) and lack arbitrary access the host filesystem (e.g., it only allows to read specific read-only files), thus being useless.

Turing completeness is a mathematical concept, why try and extend it to physical devices? Ever computer I can think of corresponds to a finite state machine.

Even if you let computers have infinite memory it still doesn't matter that much if a language is Turing complete. The person I replied to seemed to be more worried about CSS reading localstorage compared to being able to recognize a recursively enumerable language.

CSS is already Turing-complete.

https://lemire.me/blog/2011/03/08/breaking-news-htmlcss-is-t...

It may really be time to re-examine the text-only proposition (gemini style). There is this fear of missing out on visual content but I suspect this too could be handled.

we have come full circle! you should now browse websites with the terminal just to be secure. but then you get blocked for not having the right headers....

I wonder if there are any vulnerabilities in terminals which could be exploited

Or at a minimum, don't use Chrome ...

Reply on news.ycombinator.com