5 ms·

https://link.springer.com/chapter/10.1007%2F11494645_21 https://link.springer.com/chapter/10.1007%2F11494645_21 seemingly states ODEs can simulate turing machin

https://link.springer.com/chapter/10.1007%2F11494645_21 https://link.springer.com/chapter/10.1007%2F11494645_21 seemingly states ODEs can simulate turing machines. Is the simulation enough proof ofit's turing completeness, and in what sense can PDEs be called a language?

gnulinux 8y ago
Being able to simulate a Turing machine is the definition of being Turing complete. So that proof is sufficient. In mathematics (and computer science) a language is just a set of strings, and a machine is just a language attached to a semantics. I.e. whatever symbols you need to represent PDEs, inductively generated by the axioms and inference rules of mathematics and theoretical physics (like for lambda-calculus: lambda, x0,x1,... '(', ')' and reduction and construction rules)
- SubiculumCode 8y ago
  Simulation has a number meanings, depending on the field. I tend to loosely think of a simulation as a model with an acceptable level of error, but I am not a mathmatician.
  - 0-_-0 8y ago
    To simplify, in algorithm theory _simulating a Turing machine_ means the ability to execute any program "written" for a Turing machine. Turing machines, neural networks, cellular automata, computer programs and (apparently) ODEs can execute each other's "programs" (among any others).
  - gnulinux 8y ago
    This is true, thanks. As the other answer said, in this field we say given any machine M, "M2 simulates M" if M2 computes the same function as M i.e. given any input i, iff M(i) halts then M2(i) halts and M(i) == M2(i) otherwise they both loop. This can also be called "compiling" informaly: given any Turing machine, you can "compile" it to C (i.e. constructing a C program that simulates M) which means C is Turing-complete. Note that this is a very handwavy definition. The "types" of input, output, and what it means to "compute" will depend on your language, semantics and encoding. (E.g. for lambda calcus "compute" means appying reduction rules until the machine halts, if ever)
    - SubiculumCode 8y ago
      I appreciate the explanation. Clearly in this context simulation does not equal approximation !!

gnulinux 8y ago

Being able to simulate a Turing machine is the definition of being Turing complete. So that proof is sufficient. In mathematics (and computer science) a language is just a set of strings, and a machine is just a language attached to a semantics. I.e. whatever symbols you need to represent PDEs, inductively generated by the axioms and inference rules of mathematics and theoretical physics (like for lambda-calculus: lambda, x0,x1,... '(', ')' and reduction and construction rules)

SubiculumCode 8y ago
Simulation has a number meanings, depending on the field. I tend to loosely think of a simulation as a model with an acceptable level of error, but I am not a mathmatician.
- 0-_-0 8y ago
  To simplify, in algorithm theory _simulating a Turing machine_ means the ability to execute any program "written" for a Turing machine. Turing machines, neural networks, cellular automata, computer programs and (apparently) ODEs can execute each other's "programs" (among any others).
- gnulinux 8y ago
  This is true, thanks. As the other answer said, in this field we say given any machine M, "M2 simulates M" if M2 computes the same function as M i.e. given any input i, iff M(i) halts then M2(i) halts and M(i) == M2(i) otherwise they both loop. This can also be called "compiling" informaly: given any Turing machine, you can "compile" it to C (i.e. constructing a C program that simulates M) which means C is Turing-complete. Note that this is a very handwavy definition. The "types" of input, output, and what it means to "compute" will depend on your language, semantics and encoding. (E.g. for lambda calcus "compute" means appying reduction rules until the machine halts, if ever)
  - SubiculumCode 8y ago
    I appreciate the explanation. Clearly in this context simulation does not equal approximation !!