0

I'm conscious that Bitcoin's script is not turing complete, as multiple answers point out (e.g., this answer and this one). But I'm wondering if script can express the language of a PDA or equivalently, of a context-free-grammar.

I think it should be so, because of script's stack, but I'm not sure and therefore I ask for some clarifications/confirmations.

2

No, it's much less expressive than a PDA, or even a DFA. There's a stack, but what you don't have is the ability to return to the same program state with different stack contents, or for that matter, to return to the same program state at all.

Execution is linear and there are no loops, so any given instruction in the script is executed at most once. And each instruction can only inspect a bounded number of stack or input elements. So a Bitcoin script cannot even recognize the language x* (any number of xs) because a script of length n will only ever be able to look at, say, 4n elements of input, and it cannot distinguish xxxx....xx from xxxx....xy if both strings have length greater than, say, 4n+1. Even a DFA can recognize that language.

  • Now I know that there is a language that script cannot accept and DFA accepts. I am wondering if there is an example that works for script and not for DFA. – Briomkez Jul 22 '18 at 20:10
  • 1
    @Briomkez: There can't be; you can encode any script as a DFA in a very straightforward fashion. – Nate Eldredge Jul 23 '18 at 6:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.