Is Mathematica a Turing-complete language? If so, how can that be proved? If not, why?
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.
Something is turing complete if you can simulate a turing machine with it.
There's one just sitting there in the documentation.