6
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • $\begingroup$ What do you mean by "test"? How is the language or instruction set represented? $\endgroup$
    – Raphael ♦
    Sep 13 '16 at 21:12
  • 2
    $\begingroup$ One way to determine that something is Turing-complete is to create a Turing machine emulator with it. $\endgroup$
    – user253751
    Sep 13 '16 at 22:31
  • 2
    $\begingroup$ @immibis And it must be emulatable on a Turing machine. There is no proof whether there are Turing-powerful models of computation that are not Turing-complete. $\endgroup$
    – Rhymoid
    Sep 13 '16 at 23:14
  • 2
    $\begingroup$ @Rhymoid "In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if it can be used to simulate any single-taped Turing machine." - Wikipedia, see also the "Formal definitions" section. $\endgroup$
    – user253751
    Sep 13 '16 at 23:51
  • 1
    $\begingroup$ @immibis I know. Except that "computationally universal" is a presumptious title, as there is no proof that there isn't anything 'stronger' (i.e. a model of computation that can simulate any TM, but which can't be simulated by any TM). $\endgroup$
    – Rhymoid
    Sep 14 '16 at 0:00
12
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you. That makes sense, however, showing that an instruction set can do infinite search seems like a problem that could also be a undecidable one. I found something called "cyclic tag system" that seems to have history of proving Turing completeness of cellular automata. $\endgroup$
    – Gabriel Tigerström
    Sep 13 '16 at 21:45
  • 2
    $\begingroup$ This is a weirdly artificial counterexample. It's basically, If M1 halts given x, run known Turing Machine; else, do nothing. I also doubt its correctness, the line: "if (M1 halts running on x)" is quite dubious because of the halting problem. In other words, you've assumed you have a general solution to the halting problem. So I think all this really proves is that, if the halting problem has a solution then it's impossible to tell if an arbitrary system is Turing complete. Then this proof is vacuous since you've started from a false hypothesis. (p->q) is always true if p is false. $\endgroup$
    – user2264247
    Sep 14 '16 at 0:44
  • 2
    $\begingroup$ @user2264247 It's not a counter-example, it's a reduction, so specific or not, you only need one to prove something undecidable. The "if M1 halts running on x" is basically just a way to say "run M1 on x, and do the following if it halts". Obviously we'll never hit the loop line. But the important thing is, we never actually run this code, we just use it as an input to the hypothetical "is this system Turing Complete" algorithm, deriving a contradiction to disprove its existence. $\endgroup$
    – jmite
    Sep 14 '16 at 1:06
  • 1
    $\begingroup$ @user2264247 I've fixed it to not explicitly call a halting problem solver. But you should review Rice's Theorem, its proofs look basically like this. $\endgroup$
    – jmite
    Sep 14 '16 at 1:08
4
$\begingroup$

Is there an automatic test for Turing Completeness? I'm not sure. I'm going to guess not since it feels like an analog of the halting problem.

Is there a way for humans to tell if a system is Turing Complete? Yes.

It all boils down to the Church-Turing thesis. The TLDR version is that two systems can solve the same set of problems if they can run emulators of each other.

So one way to prove that a system is Turing complete is to emulate a universal Turing machine. The game of life for example was proven to be Turing complete by emulating a universal Turing machine.

Side note: An actual Turing machine has infinite tape length. Therefore no physical system is technically Turing complete (at minimum the universe has a maximum number of electrons). The usual caveat goes something like: this CPU/programming language is Turing complete if we assume infinite memory.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ Nitpicking: You don't need infinite memory. You need unbounded memory. $\endgroup$
    – Bakuriu
    Sep 14 '16 at 9:39

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.