https://xiaohuiliu.medium.com/turing-machine-on-bitcoin-7f0ebe0d52b1 Get started Open in app sCrypt Sign in Get started 434 Followers About Get started Open in app Turing Machines on Bitcoin Bitcoin Turing-Complete Proof sCrypt sCrypt 2 days ago*4 min read We have empirically demonstrated that any Turing machine can be simulated on Bitcoin and thus definitively proven it is Turing-complete1. We have implemented a Turing machine that recognizes balanced parentheses and deployed it on the Bitcoin blockchain. Any other Turing machines can be simulated in the same way. Introduction to Turing Machine A Turing machine consists of the following components (simplified): * A current state, out of a limited set of states (with one state marked as initial state, some states as accepted states) * An tape with storage cells and a read/write-head that can move on the tape * A so-called transition function that tells the machine what to do and when. In the example below, we show an Turing machine for checking balanced parentheses. Its initial state is A and it contains one accepted state. The transition function says, for instance, if the machine is at state A and its head reads symbol ")", it should write "X" in that cell and move left, transitioning to state B. [1] [1] A Turing Machine checking balanced parentheses Church-Turing Thesis The Church-Turing Thesis states that the Turing machine can compute anything that can be computed. It is the very definition of computation and the fundamental tool for reasoning about computers. Simulate Turing Machines on Bitcoin We show a generic way to simulate Turing machines on Bitcoin. We take snapshots of a running Turing machine: head position, current state, and tape. Snapshots are stored in a stateful Bitcoin smart contract. More specifically, they are in the outputs of Bitcoin transactions. Each step in running the Turing machine is triggered by a Bitcoin transaction. The Turing machines can keep running, unless it enters an accepted state. [1] [1] Simulating Turing Machines (TM) Implementation To demonstrate the feasibility of simulating Turing machines on Bitcoin, we have implemented the aforementioned Turing machine to check balanced parentheses, as shown below. A Turing Machine contract checking balanced parentheses Each time the public function transit() is called in a transaction, the machine advances one step. * Line 3-6: define states, including initial state and accepted state * L9-12: define all symbols * L19-30: define the transition function as a table * L37: read the symbol from head * L40-43: use the current state and head symbol, we look up in the transition function table to find the new state (L46), write to the tape (L48), and move the head (L50). * L51-59: initially the tape contains only the input string, such as "(())()()." If any time the tape runs out, either on the left (L52) or right (L56), a blanked cell is added. This ensures the tape can be arbitrarily long and is unbounded (but not infinite2). Deployment We have deployed the Turing machine above to Bitcoin and run it on the input string "(())()()." The complete execution is shown below. [1] [1] Turing Machine Accepting (())()() This is Turing Machine at step 0: [1] [1] Turing Machine at Step 0 You can see the snapshot of the Turing machine is encoded in this transaction. [1] [1] Step 0: txid Similarly, this is step 3: [1] [1] Turing Machine at Step 3 And it is encoded as follows: [1] [1] Step 3 txid Turing Complete Proof It is straightforward to adapt the Turing machine contract above to implement any other Turing machines, by simply changing the states, the symbols and transition function. Thus, any Turing machine can be simulated on Bitcoin, conclusively proving Bitcoin is Turing-Complete by definition. QED. In computability theory, a system of data-manipulation rules is said to be Turing-complete if it can be used to simulate any Turing machine. Acknowledgements Thanks goes to Pasquale Valentin for helping deploying the contract on Bitcoin. [1] We have preciously shown Bitcoin is Turing-complete by implementing Turing-compele systems on it, such as Conway's Game of Life and Rule 110. [2] Infinite and Unbounded By Craig Wright | 14 Sep 2021 sCrypt sCrypt Inc (https://scrypt.io) is a company with a mission to provide integrated on-chain smart contracting solutions using the original BitCoin Protocol on BSV Follow 539 539 539 * Bitcoin * Scrypt * Bitcoin Sv * Turing Machine * Smart Contracts More from sCrypt Follow sCrypt Inc (https://scrypt.io) is a company with a mission to provide integrated on-chain smart contracting solutions using the original BitCoin Protocol on BSV More From Medium Zelcore --Claiming the VBK Distribution David - (All_systems_go @ Team Zel) in Zel Insights [1] [1] The Ethereum Casper protocol explained Elena in StormGain_crypto [0] [0] Top 5 Cryptocurrencies To Look Out For Invest In 2020 Saikiran Reddy K [1] [1] The GRMTK Launch -- LIVE -- Nov. 9! SingularDTV in SingularDTV [1] [1] Secure Multiparty Computations on Bitcoin sCrypt [0] [0] ReddCore Dev Update (Q3 2021) Tech Adept in ProjectRedd [1] [1] What is a blockchain fork? Qtum in Qtum [1] [1] Bitcoin Gold(BTG) Reviewed -- Is It Truly Decentralizing Bitcoin? Nigeria Bitcoin Community in Nigeria Bitcoin Community [0] [0]