Tell me more ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.
up vote 12 down vote favorite
1

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

share|improve this question
2  
Wasn't a machine that could decide nothing more than whether to go forwards or backwards on the tape it was reading, Turing complete? – image_doctor Apr 30 '12 at 10:32
7  
Well Rule 110 is Turing complete, and Mathematica can implement Rule 110, so... yes? – Verbeia♦ Apr 30 '12 at 10:42
@Verbeia - job done then :) – image_doctor Apr 30 '12 at 10:45
5  
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. – Yu-Sung Chang Apr 30 '12 at 14:47

2 Answers

up vote 19 down vote accepted

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.

share|improve this answer
4  
Another minimalist example for a Turing complete language is Brainfuck, which syntax consists of 8 symbols. – sebhofer Apr 30 '12 at 12:37
2  
@sebhofer which we've also shown that Mathematica can act as an interpreter for. :) – rcollyer Apr 30 '12 at 14:18
@rcollyer that's quite cool! I wasn't aware of it. – sebhofer Apr 30 '12 at 14:39
up vote 18 down vote

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.

share|improve this answer
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? – Nick Kidman Oct 12 '12 at 15:11
I apologize. My syntax here wasn't sharp. Given a Turing machine, you can simulate that Turing machine using the TuringMachine function. – Searke Oct 15 '12 at 13:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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