3 ms·
I saw an HN comment recently saying that CSS is Turing complete; this sort of example makes me wonder if there's a formal model of side-effects and ability to d
by OJFord 5y ago
I saw an HN comment recently saying that CSS is Turing complete; this sort of example makes me wonder if there's a formal model of side-effects and ability to do things like interface with I/O including NICs in order to make web/db/etc. requests?
Or maybe it doesn't even need (a separate) one, because all a Turing machine needs is some other 'networking machine' to be looking at some designated area on tape (I'm describing DMA essentially, I suppose)? And maybe what else happens externally in response to what's on the designated tape area is uninteresting/completely arbitrary and doesn't need to/inherently can't be formally modelled?
- erk__ 5y agoOne idea a bit in this direction I have heard about is if a language is "Pacman-Complete" that is it can be used to implement Pacman
- SamBam 5y agoI thought Doom was the standard game people try to get working on all manner of ridiculous devices. So Doom-complete.
- colonwqbang 5y agoThe tape machine model is one way of looking at it. Another is the type of functions (expressions) that can be computed. A turing complete process can compute general recursive functions. I think of this very informally as having not only for() loops with fixed bounds on the loop index, but also while() loops where you don't know beforehand how many loops it will take to compute something. Alternatively you can express the same thing in terms of recursion. One characteristic is that it's possible to describe computations that never finish. Another is that you cannot always tell from looking at a particular program if it will ever finish. Exactly how or if the result of a computation becomes apparent to the outside world, I think is not part of the theoretical description.