The concept of a Turing machine has been well defined. It would be sufficient to show that Bitcoin uses a dual stack architecture that acts as a dual counter machine. Such systems have already been demonstrated as being Turing complete.
Home » A Proof of Turing Completeness in Bitcoin Script