Hacker News Reader

Comment by adrianN | Hacker News Reader

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.

View on HN

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.

This is also the issue with the CSS "proof" of turing completeness. It does not actually work for the same reason.

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

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.

Linear progression from one state to another without conditionals is not even DFA.

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

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.

An element can reference itself and perform calculations which would be a looping construct though? That `url` reference includes itself.

How about using automatic page reload? Can that be used or is there no way to pass all the state?

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.

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.

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.

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.

What is the difference? The point is to be able to take a transition back to an earlier state.

It's just a jump that can be used as a loop.

Reply on news.ycombinator.com