Is Bitcoin still running on a Turing-Incomplete system? What's the deal?

Recently, I stumbled upon the term "Turing completeness". Alan Turing popped into my mind since I saw that movie "The Imitation Game" a while back. Lucky for me, the ideas of Turing Complete and Incomplete come up in various contexts, especially when talking about Bitcoin and Ethereum. I’ve been stuck trying to wrap my head around these Turing concepts for some time now, almost getting discouraged and wanting to move on to something else. But my curiosity about Bitcoin keeps pulling me back to its Blockchain aspects. So here I am, trying to figure out how all this connects to Bitcoin. From the basic definitions I found, Turing complete refers to a system's ability to perform complex calculations if it has enough resources like memory and time. This was pretty straightforward and I could relate it to something like smart contracts. Next, I wanted to see its connection to Bitcoin. Most articles I read labeled Bitcoin as Turing incomplete and Ethereum as Turing complete, but I’m not really getting why. They say this because Ethereum can run smart contracts. Of course, we know that Ethereum was built not just for token transactions but also for creating DApps and implementing smart contracts. But this reasoning doesn’t seem fair to Bitcoin, which has its own capabilities. I still find the whole Turing complete/incomplete discussion a bit confusing, and I’m curious about what actually led to these conclusions.

Yes, Bitcoin's Script language is still "Turing incomplete". And it is deliberately so, because of fears that Turing completeness could create attack vectors. A simple way to understand this is that in a Bitcoin transaction, you can't set conditions which result in a loop. Loops are one of the aspects a Turing-complete programming language usually offers. For example you can't create the following transaction (stupid example, but that is actually how DEXes work): [1] "Send 2 Bitcoins to each address which send 1 Bitcoin to my address." In Python-like pseudocode this could be something like this: This is very simplified because in Bitcoin a transaction can have various senders, but I hope you get what I mean. In Ethereum such conditions can be created in transactions. This results in "richer" possible smart contracts. On Bitcoin you can only create a single "row" of conditions and they must be fulfilled in the next step. Loops are not possible. You can use if/else branches though with OP_IF. It is however possible to create a Turing-complete language for token transactions on the Bitcoin blockchain. However, that would not be the Bitcoin protocol anymore, but a protocol "on top" of it. Counterparty tried this and released an alpha software, but they gave up due to high transaction fees. A newer idea is the BitVM protocol. [1] Ah, I forgot something: A DEX with Bitcoin is actually possible, but you need various linked transactions (Atomic swaps), or a transaction signed by all participants of the trade. But it works actually a bit different than the Ethereum-like example I gave.

compare how with ethereum, a transaction can cost you gas even if it fails. with bitcoin if the transaction doesn't succeed then it doesn't cost you anything. that's the difference.

Aside from what what @d5000 said, there are few other limitation of Bitcoin script which described here, https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-September/017306.html. Yes. No, there are other blockchain / layer which also support Solidity. But it's initially created for Ethereum.

How about the most basic reason, it does not need it. BTC is working fine and adding complexity and features like this would not change it's use. Just add more issues. -Dave

Yes. Because of the halting problem. If your program is turing-complete, then you have no way to determine, if it will terminate, and when it will terminate. If you have only "if" statements, then they are executed once or never. If you have "while" loops, then they can never execute, execute once, execute forever (halt), or execute different number of times, depending on the input script. It is easier to recognize it by examples. If you need a minimal working example, then a full BF-language implementation is Turing complete. If you want a Bitcoin-related example, then imagine that the current Script would have not only OP_IF, but also OP_WHILE. That would be sufficient to make it Turing-complete. Because BTC has no loops, while ETH has them. And because of that, there are some kind of limits, to not have some EVM script, which would execute forever, like "OP_TRUE OP_WHILE OP_ENDWHILE <pubkey> OP_CHECKSIG". And also, this is another reason, why users are charged, even if their scripts fail. The advantage is that if something is Turing-complete, then you don't need any network upgrades. You can do everything inside your scripting language. The disadvantage is that you cannot quickly check, if some script will terminate in a given time, and how many resources it will consume. The current solution for Bitcoin is to repeat opcodes as many times, as the maximum number of loop iterations. But because it is expensive, people often execute their contracts on second layers, to avoid those costs, and then they only commit the end result on-chain.

I think the example fits well in this context... took a while to process this. Could a version of this python pseudocode be replicated in C, because I am quite familiar with the basics of C. Yes, I do. Pardon if my questions are quite unrealistic. This single row of conditions, is it also applicable to Lightening Network transactions?, Where two individuals create a channel and begin to make transactions till they are ready to broadcast?. About four were mentioned, but it seems there are more relevant ones. Have they been able to come up with any solutions for the relevant ones?, Because i noticed it was written about since 2019. Further Addition I think this explanation has helped in relieving some doubts as well. In contrast to the last paragraph from your explanation, those it in anyway relates or answer this question I asked d500 previously?.

In C, "Send 2 Bitcoins to each address which send 1 Bitcoin to my address" would look like this: The good question is how could this be implemented in Script, if OP_WHILE existed? Bounty 50 merits for whoever answers this correctly.

Not sure if I relate it well with the C code. I doubt if this would work.

If you have BF language, mentioned above, then it has simple while loops. The difference between OP_IF and OP_WHILE is simple: OP_IF is executed once, and then forgotten. OP_WHILE is executed constantly, as long as the top element of the stack is true. Which means, that you can have a valid Script: <condition> OP_IF <code> OP_ENDIF And a valid loop is quite similar: <condition> OP_WHILE <code> OP_ENDWHILE This can be splitted into: 1. You send me 1 BTC. 2. I send you back 2 BTC. Let's see, how it would look like, purely transaction-wise, without any Script: In practice, it can be done today, if you know, how to use something more than SIGHASH_ALL. No Turing-completeness is needed. First, let's assume that Bob has some funds, which he wants to send to Alice. He can craft this transaction, signed with SIGHASH_ANYONECANPAY: Obviously, it has negative fee, equal to -1.00 BTC. It simply creates coins out of thin air. However, it is not fully signed. It has ANYONECANPAY flag, which means, that "anyone can pay", meaning that "anyone" can "add more coins as inputs". So, Bob provides his signature, and sends this transaction into Alice (without using P2P Bitcoin network, because it would reject this transaction, because of "negative fee"). Then, Alice can grab hex bytes of this transaction, and add her input: As you can notice, it can be anything: sent into Bob, sent into Alice, just anything at all. It does not matter, because Alice will not receive her 2 BTC, if she will not attach her coins. In practice, the most convenient way is to attach original Alice's coins there, without sending them to Bob at all. In this way, everything can be compressed into a single transaction, and serve the same purpose ("sign my transaction, and I will give you my coins"). Because what Bob can achieve in this contract, is to have his own coins signed with Alice's signature (yes, she can also use different sighashes than SIGHASH_ALL, but it would be unsafe for her). I have enough merits, I am more interested in doing that in practice, for example in testnet3 or testnet4. So, do you want to receive some test coins for sending some? As you can see above, I need Alice's address as a destination. Edit: I am ready, I got some coins from Garlo Nicon for this experiment: https://mempool.space/testnet4/tx/45b74f6032d6f5869326a7c4bca54efd7f6248c0d9782599b969f4913ec97046#vout=0 https://mempool.space/testnet/tx/9f523a213550f813e049c0ef9489e2739eada990e2e37e17caeb1ae4527390cd#vout=0

It's a good attempt, but here's a few questions: Would this be an unlocking or locking script? The sender would somehow need to know that he'll get the 2 BTC beforehand. This implies, to me, that the sender will lock his bitcoin to this condition.What does OP_ADD add? You say that you add transactions, but OP_ADD adds the top two numbers in the stack. That's indeed a smart solution to our problem, but I was wondering if it can be implemented non-interactively, meaning, without having to interact with Alice. Could this work by playing with Script? For example, Alice constructs an address which, if ever receives 1 BTC, an unlocking script can be constructed by the sender, so that he can spend that bitcoin, plus another (from another UTXO).

With OP_CAT? Sure. Then, you require a valid signature, and you explore the currently executed transaction to check, if Alice's address is on both sides, with proper amounts (which means, that you just OP_CAT some pre-defined bytes, with some user input from the stack, you hash it, and then you use OP_CAT to combine it with OP_CHECKSIG, to act like OP_CHECKSIGFROMSTACK). Edit: Sure, here you are: This means "if I receive 1 BTC here". Now, we can sign it properly: And then, my job here is almost done. Almost, because now I am 100% sure, that I can receive 1 tBTC in a decentralized way, just from anyone. And then, if I wouldn't care, I could just release my coins, without any conditions: Well, almost there. Why almost? Because without SIGHASH_ANYPREVOUT (or rather: SIGHASH_PREVOUT_REPEAT, which would consider previously used sighashes), the user cannot really touch our initial transaction, because it will change transaction ID, and our SIGHASH_NONE | SIGHASH_ANYONECANPAY signature would be suddenly invalid. So close! But with SIGHASH_ANYPREVOUT, it can be signed, as shown above, and then no interaction from Alice is needed.

This should work as a locking script, since there is a condition that has been set or must be met before the sender gets the 2 Btc. You are right. I just couldn't express the explanation using comment, but here is another trial: From the code I could come up with, The op_add is basically adding the OP_PUSHNUM 1 with value 1 to the stack, and remember that the stack already contains a value 0 from OP_PUSHNUM 0(tx_sum) as specified in line 2, leading to the addition of 0+1, since they are the top two numbers available in the stack. This would then give rise to a new sum( tx_sum==1), which I think matches the condition, before the next OP_PUSHNUM 2 is exceuted. Kind of contradicting, but this is just what I could come up with. Am looking forward to all corrections.

At least the individual transactions on "pure" Lightning network do use Bitcoin Script, even if they are exchanged offchain between the participants. So they can also contain no loops but only a "row" of conditions. You wrote in the OP that you read that Lightning uses "smart contracts", and yes, that is true: the HTLCs are smart contracts. But these contracts do not need a Turing-complete environment, because their conditions are executed one after another, with if-else branching. In Lightning's HTLCs, for example it is typical to require either a secret (hashlock) or a waiting time (timelock), but once one of both is provided the coins can be transferred. It is still a "row" even if it has if-else branches. You can however build a protocol on top of Bitcoin and Lightning to allow loops of conditions. AFAIK that is what RGB is attempting. But also AFAIK (I'm not 100% sure but only 90% ) this protocol could never affect Bitcoin UTXOs, i.e. "Bitcoin transactions", but only token transactions based on this protocol "on top of Bitcoin". You could for example imagine such a system allowing loops for Counterparty transactions or Runes. On sidechains, loops are possible if the sidechain protocol provides a language/VM to execute contracts with loops/recursion. That's actually what Rootstock's goal is, although their system is still quite centralized.

@vjudeu: Contract executed: https://mempool.space/testnet/tx/70f8a2d9e01f8603cc0301fe5b3b809c5a9acfc975a5f122393b1c900b977cba As everyone can see, the recipient can simply publish some partially-signed transaction, and then the sender can do the rest, without any interaction. Challenge for readers: repeat the same thing on testnet4. It is easier to get them, because each block will give you at least 50 new coins.