How Bitcoin and Ethereum solved the Halting Problem differently

This article attempts to explain the roaring success of the Ethereum Ecosystem by examining its approach to solving fundamental problems related to blockchain transaction execution.

Why is this important?

• Ethereum Network natively supports complex arbitrary bytecode. Bitcoin Network does not. Complex arbitrary turing-complete bytecode language is necessary for ‘colored coins’ (tokens) and for trustless DeFi because it allows for smart contracts which can perform multi-asset atomic swaps (DEX swaps) in which Asset A is sent from Alice to Bob and Asset B is sent from Bob to Alice in one transaction and which can also perform programmatic escrow of liquidity in trustless ‘vaults’.
• The Bitcoin Network does not support complex arbitrary bytecode and does not have many custom assembly instructions, so ‘colored coins’ (tokens) and DEX swaps are not possible on the network. All transactions can only be uni-directional, requiring a trusted third party custodian for all transactions. Either you trust Bob to uphold their end of the ‘deal’ (whatever it is) when you pay them, or you use a centralized trusted third party to help conduct the deal.

How did each network solve the Halting Problem?

A blockchain that processes transactions from users is a computing machine. Consider the following:

In 1936, Alan Turing proved the Halting Problem which states that “it is impossible for a [computer machine] to predict whether an input will or will not halt during execution.”

When a blockchain network processes any Transaction, if the TX has the executional complexity to potentially be able to halt (loop) forever, then eventually the network will attempt to process a transaction that will halt the network. When this happens, the entire blockchain network will crash and will be taken offline.

• Bitcoin Network solved this problem by reducing the potential complexity of assembly instructions so that it is impossible for a transaction to halt. By disallowing loops and by limiting the bytecode instructions such that the execution machine is not ‘Turing complete’, the halting problem is avoided. However, this deeply limits the capabilities of the network. With this paradigm, transactions can never roll back atomically because they never need to rollback as there can never be a halt.
• Ethereum Network solved this problem in a way that maintains the complexity of assembly instructions such that the EVM is fully ‘Turing complete’ and able to process arbitrary executable bytecode uploaded by users (smart contracts.) Ethereum solves the Halting Problem by requiring that each executed instruction requires payment of ‘gas’ and by running out of gas or by erroring, the transaction atomically rolls back to the beginning and rewinds state.

I theorize that it is impossible to operate a blockchain network that supports complex Turing-complete execution without the concept of gas, simply because Alan Turing proved his Halting Problem in 1936. Due to these reasons, I personally decided years ago to focus all of my developmental efforts on Ethereum Network due to the increased capabilities of the bytecode instruction set. While I admire the innovation of Bitcoin, that does not warrant the limitation to develop software in a sub-turing-complete execution environment. A programmer who artificially limits themselves will be beaten to innovation by those who do not.