pull down to refresh
0 sats \ 5 replies \ @random_ 15 Oct 2023 \ parent \ on: BitVM Online - Play with tapleaf-circuits (by supertestnet) bitcoin
How to add recursion so it will actually be Turing Complete?
I don't see a way to do that
And I don't think it matters
You can write any program with a real turing complete computer, then convert the program to a tapleaf circuit for use in bitvm, and -- if your program has a valid "solution" and doesn't halt -- the bitvm can execute it.
It may not be turing complete itself, but who cares when it can execute any valid program that a turing machine can produce?
reply
Can you make a program for palidrome checking?
reply
definitely
I'm just learning circuit based programming for the first time so I won't be able to do it quickly
but in theory yeah, for sure, because you can run any computable function, and palindrome checkers already exist as computable functions, so we can just port one (once we have tools for stuff like that)
reply
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".
but in theory yeah
In theory of computation, Turing Machines describe recursively enumerable languages. Anything less is... not.
reply
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