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:
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.