News for hackers. Stuff that matters.
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.

However, it's nice to see how expressive SVG is.

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.

EDIT: grammar.

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 ktpsns on Monday September 16, 2019 @04:37AM (#20982136)
I share this view. Of course, adding a line

    <use href="#line[N+1]" y="30" id="lineN" filter="url(#rule110)" />
is trivial, this basically translates to

    result[N+1] = rule110(result[N])
in any imperative pseudo code. It is lacking a simple loop, but that's the point.