News for hackers. Stuff that matters.
Re:SVG Is Turing Complete by adrianN on Monday September 16, 2019 @04:23AM (#20982071)
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.
Re:SVG Is Turing Complete by nabla9 on Monday September 16, 2019 @05:39AM (#20982411)
You 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.
Re:SVG Is Turing Complete by inglor on Monday September 16, 2019 @05:44AM (#20982436)
This is also the issue with the CSS "proof" of turing completeness. It does not actually work for the same reason.
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.

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

  <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.
Re:SVG Is Turing Complete by nabla9 on Monday September 16, 2019 @06:22AM (#20982642)
Linear progression from one state to another without conditionals is not even DFA.
Re:SVG Is Turing Complete by tyingq on Monday September 16, 2019 @05:39AM (#20982410)
You 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.
Re:SVG Is Turing Complete by inglor on Monday September 16, 2019 @05:43AM (#20982431)
An element can reference itself and perform calculations which would be a looping construct though? That `url` reference includes itself.
Re:SVG Is Turing Complete by phkahler on Monday September 16, 2019 @09:32AM (#20983815)
How about using automatic page reload? Can that be used or is there no way to pass all the state?
Re:SVG Is Turing Complete by bemeurer on Monday September 16, 2019 @04:56AM (#20982214)
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.
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 DSingularity on Monday September 16, 2019 @07:23AM (#20982974)
What is the difference? The point is to be able to take a transition back to an earlier state.
Re:SVG Is Turing Complete by k__ on Monday September 16, 2019 @08:06AM (#20983216)
It's just a jump that can be used as a loop.