4 ms·

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 a

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.

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.