On the pedantic points, I echo what tucenaber just said-- and I could not say it better. (Also, see #bitcoin-wizards past logs for commentary about total languages. I also consider that a major useful point for languages for this kind of system).
People looking for "turing complete" smart contracts inside a public cryptocurrency network are deeply and fundamentally confused about what task is actually being performed by these systems.
It's akin to asking for "turing complete floor wax". 'What does that? I don't even.'
Smart contracts in a public ledger system are a predicate-- Bitcoin's creator understood this. They take input-- about the transaction, and perhaps the chain-- and they accept or reject the update to the system. The network of thousands of nodes all around the world doesn't give a _darn_ about the particulars of the computation, they care only that it was accepted. The transaction is free to provide arbitrary side information to help it make its decision.
Deciding if an arbitrarily complex condition was met doesn't require a turing complete language or what not-- the verification of a is in P not NP.
In Bitcoin Script, we do use straight up 'computation' to answer these questions; because that is the simplest thing to do, and for trivial rule sets, acceptably efficient. But when we think about complex rule-- having thousands and thousands of computers all around the world replicate the exact same computation becomes obviously ludicrous, it just doesn't scale.
Fortunately, we're not limited to the non-scalablity-- and non-privacy-- of making the public network repeat computation just to verify it. All we have to do is reconize that computation wasn't what we were doing from the very beginning, verification was!
This immediately gives a number of radical improvements:
"The program is big and I don't want to have to put it in the blockchain in advance." -> P2SH, hash of the program goes into the public key, the program itself ends up being side information.
"The program is big but we're only going to normally use one Nth of it-- the branches related to everything going right" -> MAST, the program is decomposed into a tree of ORs ans the tree is merkelized. Only the taken OR branches ever need to be made public; most of the program is never published which saves capacity and improves confidentiality.
"The program is big, and there are fixed number of parties to the contract. They'll likely cooperate so long as the threat of the program execution exists." ->
Coinswap transformation; the entire contract stays outside of the blockchain entirely so long as the parties cooperate.
"The program is big, and there are fixed number of parties to the contract, and I don't care if everything just gets put back to the beginning if things fail." ->
ZKCP; run _arbitrary_ programs, which _never_ hit the blockchain, and are not limited by its expressive power (so long as it supports hash-locked transactions and refunds.)
"The program is kinda big, and we don't mind economic incentives for enforcement in the non-cooperative case" -> challenge/response verification; someone says "I assert this contract accepts," and puts up a bond. If someone disagrees, they show up and put up a bond to say it doesn't. Now the first party has to prove it (e.g. but putting the contract on the chain) or they lose their bond to the second party, if they're successful they get the bond from the second party to pay the cost of revealing the contract.
"The program is too big for the chain, but I don't want to depend on economic incentives and I want my contract to be private." -> ZKP smart contracts; PCP theorem proves that a program can be proved probabilisticly with no more data than log the size of its transcript.
SNARKS use strong cryptographic assumptions to get non-interactive proofs for arbitrary programs which are constant size (a few hundred bytes). Slowness of the prover (and in the case of snarks, trusted setup of the public key-- though for fixed sets of participants, this can be
avoided) limit the usefulness today but the tech is maturing.
All of these radical improvements in scalablity, privacy, and flexibility show up when you realize that "turing complete" is the wrong tool, that what our systems do is verification, not computation. This cognitive error confers no advantage, outside of marketing to people with a fuzzy idea of what smart contracts might be good for in the first place.
More powerful smart contracting in the world of Bitcoin will absolutely be a thing, I don't doubt. But the marketing blather around ethereum isn't power, it's a boat anchor-- a vector for consensus inconsistency and decentralization destroying resource exhaustion and incentives mismatches. Fortunately, the cognitive framework I've described here is well understood in the community of Bitcoin experts.
