8 ms·

SVG Is Turing Complete

101 points by pentestercrab 7y ago

saagarjha 7y ago
> Runs in Chromium 73.0.3683.103 after several seconds, seriously, this thing is slow! 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/script https://developer.mozilla.org/en-US/docs/Web/SVG/Element/scr...
- jorams 7y ago
  In Chromium 76.0.3809.132 it renders instantly for me as well. I wonder what changed. It doesn't render correctly in Firefox, though that finishes instantly as well.
- jansan 7y ago
  Javascript should have never been added to SVG. IMHO Javascript should always be outside the SVG.
  - nightfly 7y ago
    Javascript in SVGs only gets executed when the top-level document is an SVG, never when the SVG is used as an img.
- ttctciyf 7y ago
  > you can embed JavaScript in an SVG I guess that settles the Turing complete issue then!
grenoire 7y ago
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.'
- Dylan16807 7y ago
  I say no, by far. The ability to add and multiply is "Turing complete" if you add external looping. Or in this case, the ability to XOR and NOT. But nobody is going to click on "SVG/CSS/HTML is arithmetic-complete". Or "ring-complete".
  - fourthark 7y ago
    I hope the author made a mistake and didn't make a false claim for clicks.
    - Dylan16807 7y ago
      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.
Gehinnn 7y ago
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. However, it's nice to see how expressive SVG is.
- eequah9L 7y ago
  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. EDIT: grammar.
  - TheDong 7y ago
    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.
    - Gehinnn 7y ago
      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.
      - TheDong 7y ago
        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.
londons_explore 7y ago
On Chrome android I get a SIGSEGV in the GpuWatchdog process of Chrome. No stack gets decoded. Interestingly, it only happens if I plug in or remove the power cable while the page is loading. It happens reliably.
- concerned_user 7y ago
  Switching between GPU is taking place when you do that.
  - londons_explore 7y ago
    Not on Android as far as I'm aware?
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 ago
  You 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 ago
    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.
    - OskarS 7y ago
      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.
      - CDSlice 7y ago
        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.
  - DSingularity 7y ago
    What is the difference? The point is to be able to take a transition back to an earlier state.
im3w1l 7y ago
SVG can contain javascript, so yeah. E.g. http://srufaculty.sru.edu/david.dailey/svg/clipdrag12.svg http://srufaculty.sru.edu/david.dailey/svg/clipdrag12.svg
jasonhansel 7y ago
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.
odomojuli 7y ago
It seems trivial as a naive guess that SVG is TC if it can contain JavaScript, which is TC. 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/issues/1 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.

101 points by pentestercrab 7y ago

> Runs in Chromium 73.0.3683.103 after several seconds, seriously, this thing is slow! 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/script https://developer.mozilla.org/en-US/docs/Web/SVG/Element/scr...

jorams 7y ago
In Chromium 76.0.3809.132 it renders instantly for me as well. I wonder what changed. It doesn't render correctly in Firefox, though that finishes instantly as well.
jansan 7y ago
Javascript should have never been added to SVG. IMHO Javascript should always be outside the SVG.
- nightfly 7y ago
  Javascript in SVGs only gets executed when the top-level document is an SVG, never when the SVG is used as an img.
ttctciyf 7y ago
> you can embed JavaScript in an SVG I guess that settles the Turing complete issue then!

grenoire 7y ago

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.'

Dylan16807 7y ago
I say no, by far. The ability to add and multiply is "Turing complete" if you add external looping. Or in this case, the ability to XOR and NOT. But nobody is going to click on "SVG/CSS/HTML is arithmetic-complete". Or "ring-complete".
- fourthark 7y ago
  I hope the author made a mistake and didn't make a false claim for clicks.
  - Dylan16807 7y ago
    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.

Gehinnn 7y ago

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. However, it's nice to see how expressive SVG is.

eequah9L 7y ago
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. EDIT: grammar.
- TheDong 7y ago
  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.
  - Gehinnn 7y ago
    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.
    - TheDong 7y ago
      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.

londons_explore 7y ago

On Chrome android I get a SIGSEGV in the GpuWatchdog process of Chrome. No stack gets decoded. Interestingly, it only happens if I plug in or remove the power cable while the page is loading. It happens reliably.

concerned_user 7y ago
Switching between GPU is taking place when you do that.
- londons_explore 7y ago
  Not on Android as far as I'm aware?

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 ago
You 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 ago
  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.
  - OskarS 7y ago
    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.
    - CDSlice 7y ago
      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.
- DSingularity 7y ago
  What is the difference? The point is to be able to take a transition back to an earlier state.

im3w1l 7y ago

SVG can contain javascript, so yeah. E.g. http://srufaculty.sru.edu/david.dailey/svg/clipdrag12.svg http://srufaculty.sru.edu/david.dailey/svg/clipdrag12.svg

jasonhansel 7y ago

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.

odomojuli 7y ago

It seems trivial as a naive guess that SVG is TC if it can contain JavaScript, which is TC. 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/issues/1 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.