CSS3 proven to be Turing complete?
my-codeworks.com
my-codeworks.com
2. The 'crank' here is not part of CSS. Computer languages that are declared 'Turing complete' need to be able to crank themselves. You need to be able to tell them to go, and wait. I accept that magic the gathering Turing machine, (at least as long as you remove the word 'may'), because it's part of the MtG rule set that you continue performing all the state transitions until you reach a halt.
3. Allowing this completely external pump means that anything that can add and multiply three numbers and then exit would be counted as Turing complete, because you can then instantiate an infinite number of these and pump data through. The Turing complete nature of that construction lies mostly in that pump. It is not at all just a crank that say 'go'.
And 3 is really the important part here. None of the scary implications of 'Turing complete' come into play, because you can't take the result of one arithmetic statement and feed it into more. All of that playing around is roughly O(n) in terms of page size. Not O(unlimited) as 'Turing complete' might imply.
Layout in a web browser, which includes CSS styling, is implemented as just a top down + bottom up tree traversal. 2 tree traversals do not a turing machine make.
Maybe an analogy will help. I like the multiplier mentioned in the grandparent. Consider the multiplication circuit. I hope you agree that a multiplication circuit is not turing complete. However, if you apply a "pump" and feed its results into one of its inputs, you can calculate the factorial of any number!
This concept can be extended to take any sequence of steps and calculate recursive functions with them. This doesn't mean a linear sequence of instructions is turing complete! The feedback is a fundamental part of what makes the system turing complete.
The headline would better read "CSS + user input which can trigger a reflow is turing complete", but that wouldn't be nearly as interesting.
In fact, if CSS _was_ turing complete, I can solve the halting problem!
Step 1) Encode a turing machine as CSS + html.
Step 2) Run CSS and layout. This is O(size of css + size of html), since it's two tree traversals.
Step 3) It halts. CSS styling is finished.
CSS is just a tree traversal. It has a lot of rules, but the structure is simple. It is not turing complete.
> 1. Feeding infinite HTML is not the same as feeding
> tape. A million tape cells can keep a typical Turing
> machine running indefinitely. A million rows only keep
> this running for a million execution steps
[0] http://www.toothycat.net/~hologram/Turing/HowItWorks.html
2. In Turings own paper he envisions the "crank" to be a human. I think we can all agree that a human is more than turing complete. The process of feeding the next cell etc isn't part of what makes something Turing complete. There is no requirement that it be self-cranking in Turings papers, nor the current formal definitions I have read. Could you supply an example of where this is brought up as a formal requirement?
3. Well, yes. The point here lies in the _rules_. The method of executing the rules doesn't really matter, as discussed in 2. Humans are > Turing complete ...
Because, the fact that computers exist is not a surprise. I mean, the original concept of a Turing machine is literally a tape and a read head.
But as I understand it a Turing machine is a physical impossibility because it is defined as having an infinite stream of data being inputted. And the physical presence of an infinity of information is a physical impossibility (I also wasn't a physics major, so I'm not sure if this violates physical laws or is just a practical impossibility, but either way it's obviously impossible).
So instead of an infinite stream of input, we usually define something as "Turing complete" if it's possible for it perform arbitrary computations on arbitrary input supplied in real time. CSS3 cannot do this; programming languages with real-time I/O can do this.
So CSS3 is "weakly" Turing-complete because it can perform arbitrary computations on arbitrary data input supplied ahead of time. With an infinite amount of random HTML-formatted data input ahead of time (same as a Turing machine), it can be equivalent to a Turing machine. C or Javascript are "strongly" Turing-complete because they can perform arbitrary computations on arbitrary, properly-formatted data input supplied ahead-of-time or in real time.
2. But the behavior upon turning the crank is defined as part of the machine. The human can emulate it mentally, but they're not whole-cloth adding something that wasn't already in the machine.
3. The point here lies in the _rules_.
I agree. Which is why CSS is not Turing complete. CSS + a specific web page of enormous unending length + someone holding down a few keys is the minimum to reach Turing complete.
CSS is like "110", the number, by itself. It's not Turing complete without a bunch of rules that have absolutely nothing to do with CSS itself to push it along.
1) it's not surprising: a lot of very simple systems can compute. It seems to naturally happen as you add flexibility to your rules. See for instance Wang Tiles or some cellular automata.
2) it's not a good thing: it means that the behavior of CSS3 is undecidable in general, which makes it much harder to build tools that can meaningfully analyze it.
Anyone who has worked with CSS long enough knows that:
1) Rule priority can get out-of-hand very quickly. 2) It's a nice thought to have more powerful selectors, but, taking #1 into consideration, perhaps limiting its power isn't such a bad idea after all.
I was already on-board with using PostCSS modules, https://github.com/postcss/postcss, to selectively import functionality for use in CSS rather than the heavy-handed approach of bringing all of SASS, LESS, or Stylus. Leaving powerful expression to languages built for it seems natural -- especially when CSS and JS intermingle so heavily.
GUI toolkit and renderer development should begin with the humble admission that building a good GUI system is incredibly hard, on par with massive distributed systems and AI, and that the problem should be tackled with that level of difficulty as an expectation. A good analogy would be between a GUI toolkit and a mature 3d virtual world game engine. Those are probably roughly equivalent problem domains.
I'm just saying it's a problem domain that is consistently underestimated.
Also, as others have pointed out, it doesn't "run" unless an external thing is pressing buttons. If you allow what are essentially external programs to run, you might as well have Javascript doing the job, and then the headline becomes a lot less interesting.
So you could write your style sheets in x86 if you were so inclined.
Now there's a thought that doesn't bear too much thinking about...
CSS is primarily a declarative abstraction that grew complex enough to be Turing-complete. You would hope that by paying that complexity you would at least get an abstraction that was convenient enough to write by hand. But CSS has neither the static-analysis benefits of a non-Turing-complete language nor the convenience benefits of a fully Turing-complete language.
In practice it's probably not a problem since you don't have infinite HTML, but it is theoretically slightly disturbing.
I'm an advocate of provably-correct, non-Turing-complete languages, which really should include CSS....
You don't need Turing completeness to have trouble caused by user input. Imagine a million check boxes where the only rule is that they shrink by a pixel when checked. That should be about the same difficulty to analyze as the 110 rule checkboxes. Each input only affects the styling of 1-3 nodes.
I am one of those few.
I could easily share that knowledge, but for one to fully understand, one must walk such a path thyself guided by the voices from the source that flows over the stacks of such knowledge.
Good luck and God speed. There's no shame in turning back.
https://philipwalton.github.io/solved-by-flexbox/demos/verti...
"Assume that the amount of HTML currently loaded is finite but sufficient for all of the state to be properly rendered."
So consider <html> <div class="myContainer"> <div>1</div> <div>2</div> <div>3</div> . . .
I've never met an HTML streaming solution that won't just stream this sequentially, which means no </div> for myContainer will ever be emitted (and therefore the HTML will never be well-formed, and the CSS will never have sufficient information to lay out).
If the HTML were streamed such that <html><div class="myContainer"></div></html> were received, and then the interior of myContainer were streamed, that'd be a different story, but that doesn't exist. So I don't think this blog post's argument that CSS3 is Turing complete works for any real implementation.
And yes, there could come an yet as to unknown element later that changes the display, displays on top of using position:absolute; for example, of current content. But not that changes how current content itself is displayed.
body { -webkit-align-items: center; -ms-flex-align: center; align-items: center; display: -webkit-flex; display: flex; }
Thanks Google, Apple and Microsoft.
Meanwhile, I have web pages on my hard drive that I designed in 1999 with vertical alignment (amongst other tricks), that worked in Netscape 4.x, Seamonkey 0.86, and still work in Firefox 42. and I never needed a -moz prefix.
Maybe it's time to stop blaming the standard and start blaming 1. Users who do not use modern browsers or 2. Developers that don't update/use the new toys out there :)
Furthermore, it's best that features are behind prefixes to be used for progressive enhancement and any major browser implements new features behind a prefix before it is accepted.
There is no "cross browser hacks" for any evergreen browser. Except, ironically given your statement, IE has a buggy implementation. Edge supports it and Microsoft is deprecating IE<11 and will hopefully fix the issues in IE11. The big issues can be avoided by not declaring a min-height.
However, if vertical alignment is still prefixed in 2015, I don't think I need to submit more for my case, downvoted as it may be.
Although the outdated example is largely to blame.
There is this too: http://willkoehler.net/2014/08/28/vertically-align-content-w...
There are a lot of ways, really.
As someone who writes CSS daily (css, less and scss), I've yet to understand how some people can have any issues at all with CSS. Sure, it's quirky but you can pretty much master it in a few months at most.
(That being said, I make my life a lot more easier by using tools such as autoprefixers, library of mixins that allow me to summon arcane CSS declarations at will, etc.)
display: table-cell; vertical-align: middle;
position: absolute; top: 50%; transform: translateY(-50%)
Doing something like "if(browser width:height ratio is less than 3:2) keep a video in an aspect ratio of 3:2 and vertically-center it on the screen, else make the video width 100% and crop the video evenly on the top and bottom" is arguably a potentially common design task, yet a convoluted headache in CSS. Now add to that, "place an 'X' button in the upper right corner of the video, leaving a 20-pixel margin", and you're downright waging war with your browser.
Both of your examples don't work in all situations, by the way.
Yes, it's still inelegant and nonobvious, but it's also better than throwing document semantics out the window.