Super Testnet created some Bitcoin addresses where coin withdrawals cause nodes to execute two generations of an elementary cellular automaton, he thinks it might be a universal turing machine.
Rule 110 in Bitcoin Script Explanation
What is Rule 110?
It is an object of study by computer scientists because if you modify the top line of the image, the pattern it produces changes in predictable ways, and you can use this predictable behavior to write programs that allow people to supply any sequence of black squares and white squares as input and get an output on some lower line of the image. If users supply real information to a Rule 110 program, the Rule 110 program can manipulate that information however the programmer wants it to, and you can always tell the users that they will find the result of the computation on some pre-agreed line lower down in the image. What I think is cool is that the rules for creating a Rule 110 machine can be written in Bitcoin Script and executed by bitcoin nodes. - Super Testnet
Does this mean bitcoin's programming language, Bitcoin Script, is turing complete?
Super Testnet explains why he built this tiny virtual machine on Bitcoin
0:00
/0:43
I think so, but I am not an expert on these things and I am probably missing something. Last year a guy did a similar thing on the Bitcoin SV network and there was an interesting thread on Hacker News about it. In that thread, someone smarter than me thinks it doesn't count as turing complete for several reasons. One of them (the lack of loops) is dealt with below, another one is that you have to prepare these addresses with lots of parameters that are usually not known in normal turing machines. For example, I knew that my program would process 4 bits of data so I manually instructed it to halt after processing those four bits. A normal turing machine could process varying numbers of bits, even billions of bits. There would be some code inside the program that checks if there is any more input and that checker function would automatically tell the program to halt when there is none. But my implementation lacks that feature so maybe it's still not a real turing machine. - Super Testnet
On the other hand...
On the other hand, I think I could probably implement an input length checker like that very easily, and I don't think such a checker is really necessary for a machine to count as turing complete. All real-world turing machines have limited resources, such as memory, and therefore they cannot process an unlimited number of bits. If they try to process a program that consumes more resources than they have available, their checker will never fire and the turing machine will just break after it runs out of memory or a source of energy or after its mechanical parts wear out. Bitcoin's security measures help prevent breakage by severely limiting the number of operations you can do, as well as how much data you can process, but since all real world turing machines have limits too (just much larger ones) I think it's fair to call my Rule 110 simulator a universal turing machine, even without something that checks the length of the user's input and automatically tells it to halt when all the data is processed. - Super Testnet
Peep the full Github here
