3 ms·
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
by foxes 7y ago
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.
- nabla9 7y agoLinear progression from one state to another without conditionals is not even DFA.
- MontyCarloHall 7y ago>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/issues/1#issuecomment-531740473 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.