Turing “complete enough”

post by markmc on Feb 11, 2021

A Turing complete protocol can perform any computation or data manipulation. Ethereum is Turing complete, Algorand is not. Does this matter? Is it a strike against Algorand, or is Algorand Turing “complete enough” to perform all envisioned DeFi use cases - stablecoins, CBDCs, tokenizations, etc? Is Turing completeness an advantage for Ethereum, or does it mean Ethereum is bloatware?

post by tsachi on Feb 11, 2021

@markmc, Ethereum and Algorand were designed with very different approaches, and hence ended up with very different solutions.

Ethereum virtual machine is executing EVM bytecode, as long as you’ve provided the proper amount of gas (fee). So, while it’s true that it’s Turing complete, some types of programs could be inherently too expensive to be executed. Current Ethereum gas prices are a proof for that.

Algorand took a very different approach. The core contract language, TEAL, is not Turing complete. Nevertheless, it still allows you to implement (almost) any computation needed for DeFi applications. That allows Algorand to operate at a high speed, providing low-latency L1 contracting solution. For few solutions, look here - Algorand Developer Portal.

That L1 solution would meet the needs of 99% of the users/applications. For the remainder, there are two different approaches being explored (no official products around these yet): one is to create a co-chain that would exchange tokens with the mainnet. This would allow the co-chain to run slower than the mainnet and perform heavy computations. Another solution is to implement a layer 2 (L2) application that would interact with some L1 primitives to ensure operational atomicity.

Last, there are companies that attempt to bridge the gap by providing a smooth transition between building for Ethereum vs. building for Algorand. See Reach - https://algorand.foundation/news/reach-development

post by markmc on Feb 13, 2021

Thank you @tsachi. Maybe I’m stating the obvious, but the fact that 99% of use cases and applications can be achieved in Layer 1 smart contracts (with no gas equivalent) is a massive advantage for Algorand over all other programmable blockchains. The cost to Ethereum of being Turing complete - and therefore able to address the remaining 1% of applications - is steep in terms of complexity. Moreover, isn’t Ethereum doomed to be a victim of its own success? As the price of ETH climbs, the full capability of the EVM will be cost prohibitive. And this will continue to be the case even under Ethereum 2.0, when it becomes PoS. If I understand Algorand correctly, it seems to dodge both bullets (unnecessary complexity & costly contract execution) elegantly and only at the cost of being unable to address a tiny percentage of applications.

post by innomon on May 27, 2021

@tsachi, I completely agree with Algorand’s approach of being non-Turing complete by design. Some other DSLs also have followed this approach like DAML & Google CEL. Having said that, I see that in the post 2.6.0 master branch, where the Teal 4 code resides, it seems to me that Teal 4 is Turing complete.

My reason for this is data/transactions/logic/opcodes.go

const backBranchEnabledVersion = 4

The branch opcodes & assembler programs also check this and allow back branching, thus making it Turing complete. There are opcodes added for function calls as well.

My question is: What made Silvio & team rethink the Turing completeness aspects? Is there any blog or doc you can point me to? Else, correct me if I am reading the code out of context!

post by tsachi on May 27, 2021

@innomon,

I don’t know if you noticed, but the code around that implementation is still gated by a consensus release, so it won’t be available for use before a consensus release that would include that feature would become available.

The goal in implementing this feature (along with a few additional features, some are review-pending) was to improve the programmability on Algorand. I’m having a hard time qualifying this as Turing complete since a program runtime is strictly bounded to a specific cost, and that cost (as of this time) is pretty low.

From an academic perspective, it might be qualified to be considered Turing complete, but note that this wasn’t the direct intent here. I believe that one of the goals here was code reusability, which would allow more efficient programs to be written within the program size constraints.