No, the alt-stack doesn't make bitcoin script a Turing-complete language.
While script has two stacks, in order to simulate a two-stack pushdown automata (which is Turing complete), one has to be able to implement a finite-state control unit. This cannot be done in bitcoin script, since there is no looping or conditional branching available. It is possible to write a script that goes through the motions of running a Turing machine program by unrolling loops, but that will only work for a machine and input combination that terminates. It is very simple to write a Turing machine with a finite input string that loops indefinitely eg. consider the Turing machine defined by
states: q0 (initial), q1 and q3 (final)
and tape alphabet {0, 1}
where the transitions are
(q0, 0) -> (q1, 0, move left)
(q1, 0) -> (q1, 0, move left)
(q1, 1) -> (q1, 1, move right)
Given input 01, this machine will just loop infinitely, as simulated here:
http://turingmachinesimulator.com/shared/ojvubpsgkm
Attempting to "unroll" this as a bitcoin script will never finish.
You can get bonuses upto $100 FREE BONUS when you:
💰 Install these recommended apps:
💲 SocialGood - 100% Crypto Back on Everyday Shopping
💲 xPortal - The DeFi For The Next Billion
💲 CryptoTab Browser - Lightweight, fast, and ready to mine!
💰 Register on these recommended exchanges:
🟡 Binance🟡 Bitfinex🟡 Bitmart🟡 Bittrex🟡 Bitget
🟡 CoinEx🟡 Crypto.com🟡 Gate.io🟡 Huobi🟡 Kucoin.
Comments