Re:SVG Is Turing Complete
by ghusbands on Monday September 16, 2019 @09:47AM
(#20983945)
Perhaps 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.)
Re:SVG Is Turing Complete
by foxes on Monday September 16, 2019 @06:00AM
(#20982536)
The 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.
Re:SVG Is Turing Complete
by MontyCarloHall on Monday September 16, 2019 @08:48AM
(#20983491)
>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.
Re:SVG Is Turing Complete
by maxdamantus on Monday September 16, 2019 @05:07AM
(#20982254)
For 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.
Re:SVG Is Turing Complete
by OskarS on Monday September 16, 2019 @05:57AM
(#20982526)
To 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.
Re:SVG Is Turing Complete
by CDSlice on Monday September 16, 2019 @07:23AM
(#20982978)
Lambda 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.
Re:SVG Is Turing Complete
by Gehinnn on Monday September 16, 2019 @03:58AM
(#20981955)
I wouldn't say this proves that SVG is turing complete.
I don't see why a perfect (i.e. correct and complete) SVG interpreter could solve the halting problem using this idea.
Computationally speaking, specifying each iteration manually is equivalent to directly drawing the final image - the difference is just the representation.
Re:SVG Is Turing Complete
by eequah9L on Monday September 16, 2019 @04:33AM
(#20982120)
Halting problem is fundamental and applies to Turing complete languages as well. You cannot solve halting problem in, say, Python, but nobody would argue that as a language ideal (disregarding physical limitations of the machine that it is being interpreted on) it is not Turing complete.
Re:SVG Is Turing Complete
by TheDong on Monday September 16, 2019 @05:26AM
(#20982346)
The parent should have said "couldn't"; the halting problem isn't an issue for most non-turing complete languages.
With svg, I think it's fair to say that the halting problem is solvable trivially: every svg program halts. Any language which has a trivial solution to the halting problem is not turing complete. That's the point the parent comment is trying to make I believe.
Re:SVG Is Turing Complete
by Gehinnn on Monday September 16, 2019 @05:42AM
(#20982425)
I meant to say "could", but referred to the halting problem of turing machines.
The browser can clearly decide whether an arbitrary SVG program halts (the answer is always "yes"). If you can reduce every turing machine M to an SVG image so that they are semantically equivalent, but can decide for every SVG program whether it halts, your reduction must be uncomputable as your SVG interpretation could otherwise solve the halting problem.
However, the authors reduction is clearly computable for a given TM/CA rule, so something is wrong here.
Re:SVG Is Turing Complete
by TheDong on Monday September 16, 2019 @07:48AM
(#20983109)
At this point we're agreeing about everything except "could" vs "couldn't"
You wrote "I don't see why a ... SVG interpreter could solve the halting problem using this..."
The "don't" and "could" imply that given this, an svg interpreter could not solve the halting problem, and thus can't give an answer of "yes".
I was saying you want either "I don't see why it couldn't" (a double negative to say that it could), or "I think an svg program could (removing the "don't").
I'm being incredibly pedantic here, yes. I think we're both on the same page, and you just flipped your thoughts from a double negative sentence to a single positive thought, but didn't fixup the part you had already written.
Re:SVG Is Turing Complete
by jasonhansel on Monday September 16, 2019 @07:10AM
(#20982903)
If SVG were actually Turing complete, that would be a serious bug in the SVG spec, since it would be possible for the SVG layout algorithm to never terminate.
Re:SVG Is Turing Complete
by grenoire on Monday September 16, 2019 @03:24AM
(#20981788)
Unfortunate about the performance. A side question I have is whether or not this is Turing complete given the lack of looping and recursion possible (at least in this example). The author defines each iteration 'manually.'
Re:SVG Is Turing Complete
by Dylan16807 on Monday September 16, 2019 @10:41AM
(#20984517)
I won't accuse them of doing it on purpose when many other people have made essentially the same claim. "Turing complete" is a somewhat vague term that is tricky to evaluate in certain contexts.
It is mentioned that they intend to demonstrate this using feComposite in the source code.
There are bits and pieces of how one would prove TC for SVG.
A first step, would be identifying basic operations, as they have done. The next step would be compiling to a tag system, and simulate cyclic tag behavior.
It is expressed elsewhere that the lack of loops would exempt TC. Perhaps it can still be argued through DOM manipulation.
-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.
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/issu...
Edit: more explicitly, for each state, the user has to manually add the line
manually updating n themselves each time. This means that the transition function is "encoded" by the human, not the SVG code itself.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.
However, it's nice to see how expressive SVG is.
EDIT: grammar.
With svg, I think it's fair to say that the halting problem is solvable trivially: every svg program halts. Any language which has a trivial solution to the halting problem is not turing complete. That's the point the parent comment is trying to make I believe.
The browser can clearly decide whether an arbitrary SVG program halts (the answer is always "yes"). If you can reduce every turing machine M to an SVG image so that they are semantically equivalent, but can decide for every SVG program whether it halts, your reduction must be uncomputable as your SVG interpretation could otherwise solve the halting problem.
However, the authors reduction is clearly computable for a given TM/CA rule, so something is wrong here.
You wrote "I don't see why a ... SVG interpreter could solve the halting problem using this..."
The "don't" and "could" imply that given this, an svg interpreter could not solve the halting problem, and thus can't give an answer of "yes".
I was saying you want either "I don't see why it couldn't" (a double negative to say that it could), or "I think an svg program could (removing the "don't").
I'm being incredibly pedantic here, yes. I think we're both on the same page, and you just flipped your thoughts from a double negative sentence to a single positive thought, but didn't fixup the part you had already written.
But nobody is going to click on "SVG/CSS/HTML is arithmetic-complete". Or "ring-complete".
Interestingly, this renders on my iPad almost instantly.
Also, fun fact: you can embed JavaScript in an SVG. Just add a script tag: https://developer.mozilla.org/en-US/docs/Web/SVG/Element/scr...
I guess that settles the Turing complete issue then!
It doesn't render correctly in Firefox, though that finishes instantly as well.
However, the posted solution seems inelegant and uncompelling. Simply iterating in SVG, which can infinitely scalable.
The author expresses apprehension in this closed issue: https://github.com/tom-p-reichel/svg-is-turing-complete/issu...
It is mentioned that they intend to demonstrate this using feComposite in the source code.
There are bits and pieces of how one would prove TC for SVG.
A first step, would be identifying basic operations, as they have done. The next step would be compiling to a tag system, and simulate cyclic tag behavior.
It is expressed elsewhere that the lack of loops would exempt TC. Perhaps it can still be argued through DOM manipulation.
E.g. http://srufaculty.sru.edu/david.dailey/svg/clipdrag12.svg
Interestingly, it only happens if I plug in or remove the power cable while the page is loading. It happens reliably.