Prove or disprove that a machine is Turing Complete

computabilityturing-machines

Given a set of operations machine can perform, how to prove or disprove it's Turing Completeness? Is the definition of a set of operations and corresponding state changes is enough or should I add something to prove or disprove Turing completeness of the machine?

From the definition of Turing completeness, to be Turing complete the machine should implement all algorithms Turing machine can. Would it be enough if I show in my work that operations of Turing machine could be implemented on my machine too?

I'm implementing some algorithm on some machine and it seems to be workable and seems to be correct (at least I have an invariant and a proof that it is being kept during execution).

But if this machine is not Turing complete, would be my proof of correctness incorrect and weak?

Thanks for the explanation! Please excuse me if my question looks inappropriate.

Best Answer

I'll try to write a detailed answer. In order to prove Turing completeness of some model of computation it's much easier to use partial recursive functions or, maybe, untyped lambda-calculus than Turing machines. Let us fix the partial recursive functions (PRF) as basic model of computation (of course, it's well known fact that PRF are Turing complete). If you take a glance on a definition PRF, you'll notice its inductive nature. All you have to do is:

  • Show that you can implement such functions on your machine: $$o(x)=0,\ s(x)=x+1,\ I^n_m(x_1,\ldots,x_m,\ldots,x_n)=x_m,\text{ for all } m\leq n\in\mathbb{N}.$$
  • Show that implementable on your machine functions are close under composition and primitive recursion.
  • Finally, show that your functions are closed under minimization.

All these guarantee Turing completeness of your model.

Assuming Church-Turing thesis, you can't create an algorithmic process, which cannot be computed on Turing machine (you may just write an emulator of your model on Turing machine). That's why your proof is not affected by the matters of Turing completeness, but both time and memory bounds may be affected greatly.

Related Question