07 – SmartContracts: Turing completeness

From a conversation in Komodo Discord

PHBA2061 – I’m curious about the Turing completeness of Komodo smart contract, will it be Turing-complete ?

jl777 – I dont design things to meet abstract litmus tests, like “Turing complete” (which i think actually requires infinite storage which no practical system can have). Rather, I design to solve the actual things that need to be solved. So describe a specific useful smart contract and I can tell you if it will be supported.

From wikipedia: To show that something is Turing complete, it is enough to show that it can be used to simulate some Turing complete system. For example, an imperative language is Turing complete if it has conditional branching (e.g., “if” and “goto” statements, or a “branch if zero” instruction; see one instruction set computer) and the ability to change an arbitrary amount of memory (e.g., the ability to maintain an arbitrary number of data items). Of course, no physical system can have infinite memory; but if the limitation of finite memory is ignored, most programming languages are otherwise Turing complete.

So an incomplete Turing completeness litmus test? I ask why is that important?

Let us make a list of specific smart contracts and then just make sure all of them are supported, i.e. be able to change parameters and other practical customizations that real world usages will want to do.

Atomic swaps are a smart contract, it does the job it is supposed to do, yet it isn’t Turing complete, even the incomplete definition. So does that make atomic swaps not useful?

If the problem at hand is solved, I claim that the problem at hand is solved, regardless of its Turing completeness

Also, notice that if we don’t have to make a Turing complete contracts, we can avoid a massive amount of security issues not to mention the effort required to make it Turing complete. So why build something that will certainly create security issues if it isn’t needed?

I like to iterate from the simplest possible solution and, if that isn’t sufficient, to add a bit more. I stop when the problem is solved. I expect we won’t have to go to full Turing completeness (with finite mem) in order to be able to run 99% of the useful smart contracts.

I think the logic used is that: “A Turing complete contracts system can solve any smart contract, so if we had a Turing complete system we are golden”.

This misses the very real risks Satoshi designed the Bitcoin script system to avoid and then disabled most of those opcodes!

But the Turing question is a misdirection!! The better question is: “Can the smart contract system solve the problem it needs to solve without creating giant security attack vectors and unknowns?”

So while a Turing complete system would be able to say it can implement “any contract”, it isn’t without a giant caveat, i.e. “any contract” includes a lot of contracts with undesirable behavior.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s