3 ms·
SVG doesn't contain looping constructs AFAIK and is thus not Turing complete. Copy pasting lines that simulate one step of a TM is not the same.
by adrianN 7y ago
SVG doesn't contain looping constructs AFAIK and is thus not Turing complete. Copy pasting lines that simulate one step of a TM is not the same.
- bemeurer 7y agoYou don't need a "looping construct" to be able to perform looping. GOTO is not a looping construct, but with it you can perform looping.
- maxdamantus 7y agoFor the purposes of this discussion, GOTO is a looping construct, because it does allow looping (that is, potentially running forever). As I understand it, the SVG sample does not demonstrate looping, and the parent is saying that SVG does not allow it as far as they know.
- OskarS 7y agoTo be fair, for Turing completeness, "looping constructs" are not actually necessary. None of the "foundational" computational models (Turing machines, lambda calculus, Post tag systems, Magic the Gathering, ...) has any kind of "looping construct". It may not even be enough: the most basic looping construct (i.e. a bounded for-loop) is primitive recursive, but not Turing complete. You couldn't implement the Ackermann function without more sophisticated tools.
- CDSlice 7y agoLambda calculate has a looping construct, recursion. You can make any loop with recursion, just like you can make any loop with goto. SVG appears to have neither of these things.
- DSingularity 7y agoWhat is the difference? The point is to be able to take a transition back to an earlier state.
- k__ 7y agoIt's just a jump that can be used as a loop.
- tyingq 7y agoYou could sort of get a loop with a circular reference, but you would have no control over iteration count...the UA is supposed to stop them.
- nabla9 7y agoYou might have been the first who actually checkd the source <!-- by repeatedly using the line above and applying one more iteration of our filter, we do rule 110 --> <use href="#data" y="30" id="line2" filter="url(#rule110)" /> <use href="#line2" y="30" id="line3" filter="url(#rule110)" /> <use href="#line3" y="30" id="line4" filter="url(#rule110)"/> <use href="#line4" y="30" id="line5" filter="url(#rule110)" /> <use href="#line5" y="30" id="line6" filter="url(#rule110)"/> <use href="#line6" y="30" id="line7" filter="url(#rule110)" /> <use href="#line7" y="30" id="line8" filter="url(#rule110)"/> <use href="#line8" y="30" id="line9" filter="url(#rule110)" /> <use href="#line9" y="30" id="line10" filter="url(#rule110)"/> SVG is not Turing complete.
- inglor 7y agoAn element can reference itself and perform calculations which would be a looping construct though? That `url` reference includes itself.
- inglor 7y agoThis is also the issue with the CSS "proof" of turing completeness. It does not actually work for the same reason.
- foxes 7y agoThe simplest definition of a Turing Machine is a tuple: -a set of states -symbol set -initial state -set of accepting states -a transition function (plus blank symbol, and an alphabet, but not so important here) Evaluation (computation) is faithfully applying the transition function on the states. Effectively just a set of rules you need to follow. This definition doesn't include a "crank" that you have to turn to make it run. I think copying and pasting could be justified as "evaluating". \mu-Recursive functions (so allowing primitive recursion) are the types of functions Turing machines can compute, but that is not the definition of a Turing machine.
- nabla9 7y agoLinear progression from one state to another without conditionals is not even DFA.
- MontyCarloHall 7y ago>I think copying and pasting could be justified as "evaluating". Infinitely copying and pasting is justified to encode the state, but not to encode the transition function, as is the case here to emulate loops. To encode an infinite loop would require an infinitely long SVG, but a Turing machine requires that the transition function be finitely encoded. As someone on the GitHub commented, "If you can not construct an SVG that never halts (finishes drawing) SVG can not be turing complete." https://github.com/tom-p-reichel/svg-is-turing-complete/issues/1#issuecomment-531740473 https://github.com/tom-p-reichel/svg-is-turing-complete/issu... Edit: more explicitly, for each state, the user has to manually add the line <use href="#line[n - 1]" y="30" id="line[n]" filter="url(#rule110)"/> manually updating n themselves each time. This means that the transition function is "encoded" by the human, not the SVG code itself.
- phkahler 7y agoHow about using automatic page reload? Can that be used or is there no way to pass all the state?
- ghusbands 7y agoPerhaps the title here on HN should be changed to reflect the truth, as "SVG Is Turing Complete" is clearly false. (I wish there were a way to suggest/do that other than via commenting.)