10 sats \ 1 reply \ @random_ 16 Oct 2023 \ parent \ on: BitVM Online - Play with tapleaf-circuits (by supertestnet) bitcoin
Consider it a challenge. There may be no constraints on the string such as "must be odd length" or "must be even length" or "must have a middle marker".
In theory of computation, Turing Machines describe recursively enumerable languages. Anything less is... not.
there will need to be one constraint: a length constraint
if there was no length constraint then you could make the program process a string many googols in length until it exceeds the 2^127 logic gates our virtual machine must fit in
A length checker seems fair because the palindrome checking functions here also have length constraints
BTW the BitVM is not turing complete, it is "functionally complete." That is, it is capable of executing any computable function. A turing machine can get stuck executing an uncomputable function, such as "find the last digit of pi," and forever loop a subprocess that never gets to halt. The BitVM cannot get stuck executing an uncomputable function so it is not a turing machine.
But like I said earlier, I don't think that matters because it can execute any program created by a turing machine -- as long as that program doesn't require more than 2^127 boolean logic operations.
reply