16
$\begingroup$

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

$\endgroup$
5
  • 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$ Apr 30, 2012 at 10:32
  • 7
    $\begingroup$ Well Rule 110 is Turing complete, and Mathematica can implement Rule 110, so... yes? $\endgroup$
    – Verbeia
    Apr 30, 2012 at 10:42
  • $\begingroup$ @Verbeia - job done then :) $\endgroup$ Apr 30, 2012 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$ Apr 30, 2012 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, 2014 at 20:55

2 Answers 2

23
$\begingroup$

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.

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

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

http://reference.wolfram.com/mathematica/ref/TuringMachine.html

There's one just sitting there in the documentation.

$\endgroup$
2
  • 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, 2012 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, 2012 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.