Is Mathematica a Turing-complete language? If so, how can that be proved? If not, why?

  • 2
    $\begingroup$ Wasn't a machine that could decide nothing more than whether to go forwards or backwards on the tape it was reading, Turing complete? $\endgroup$ – image_doctor Apr 30 '12 at 10:32
  • 7
    $\begingroup$ Well Rule 110 is Turing complete, and Mathematica can implement Rule 110, so... yes? $\endgroup$ – Verbeia Apr 30 '12 at 10:42
  • $\begingroup$ @Verbeia - job done then :) $\endgroup$ – image_doctor Apr 30 '12 at 10:45
  • 7
    $\begingroup$ In practical sense, if a language contains a loop/recursive construction, conditional branches and memory allocation/deallocation, then it is almost certain that it is Turing complete (of course, it is not a formal proof :)). What are practical guidelines for evaluating a language's “Turing Completeness”? And of course Mathematica language is Turing complete. $\endgroup$ – Yu-Sung Chang Apr 30 '12 at 14:47
  • 2
    $\begingroup$ @Yu-SungChang Not neccessarily. There are restrictions you can place on recursion that will not longer make it turing complete. The Coq programming language is an example of this. $\endgroup$ – Searke Dec 17 '14 at 20:55

It has already been proven that the Rule 110 cellular automata is Turing complete. Since Mathematica can implement this cellular automata, it must be true that Mathematica is Turing complete.

Incidentally, it has been claimed that HTML + CSS3 is Turing complete, and Mathematica is a bit more expansive than that combination. So it should not be surprising that Mathematica is also Turing complete.

All this is with the standard limitation that a 'real' turing machine needs unlimited memory and time, both is not available to any physical thing.

  • 4
    $\begingroup$ Another minimalist example for a Turing complete language is Brainfuck, which syntax consists of 8 symbols. $\endgroup$ – sebhofer Apr 30 '12 at 12:37
  • 3
    $\begingroup$ @sebhofer which we've also shown that Mathematica can act as an interpreter for. :) $\endgroup$ – rcollyer Apr 30 '12 at 14:18
  • $\begingroup$ @rcollyer that's quite cool! I wasn't aware of it. $\endgroup$ – sebhofer Apr 30 '12 at 14:39

Something is turing complete if you can simulate a turing machine with it.


There's one just sitting there in the documentation.

  • 1
    $\begingroup$ Well, to be universal you must be able to simulate any turing machine, not just "a turing machine"? Is it so obvious that you can specify all machines with that functions input? I.e. is it clear that the input for the function is defined in a way equivalent to a turing complete grammar? $\endgroup$ – Nikolaj-K Oct 12 '12 at 15:11
  • 2
    $\begingroup$ I apologize. My syntax here wasn't sharp. Given a Turing machine, you can simulate that Turing machine using the TuringMachine function. $\endgroup$ – Searke Oct 15 '12 at 13:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.