Is there a way to test "Turing completeness"?

Problem Detail: 

I asked my algorithms teacher today the very same question that is stated in the title, but he seemed a bit unsure, either on the question or on the concept, so I thought I'd try here too.

Is there a minimal test that could determine whether a language or instruction set is Turing compete, or does a test of that sort fall into the domain of undecidability?

It might seem like a trivial or stupid question, but the reason I ask is that it would be a good way to test whether the instructions of a cellular automaton is Turing complete, and if there is such a test, maybe it could help when generating cellular automata.

I'm quite new to both cellular automata and undecidability problems, so go easy on me.

Asked By : Gabriel Tigerström

Answered By : jmite

I don't know about specific models. It's pretty easy to become Turing Complete, since all you need is infinite search. So I can imagine a model where searching for finite vs. infiniteness boils down to Turing Completeness, but I don't know if any actually exist.

But a general algorithm "look at an arbitrary systems and tell if it's Turing Complete" can't exist. Otherwise we could do this:

RunTuringMachine = lambda (M1) . lambda (x). lambda (M2) .    run M1 on x and discard the result   run M2 //we only get to this line if M1 halts on x 

Then, for any inputs M1, x, RunTuringMachine M1 x is a Turing-complete system if and only if M1 halts on input x, and we've solved the halting problem.

We could also prove this by Rice's theorem: if we can decide if any system is Turing Complete, then we can decide of a Turing Machine is a Universal Turing Machine, which is impossible by Rice's Theorem.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/63428