43 ms·

Interesting to note that since sCrypt's "loop" construct simply unrolls the loop the constant number of times, proposed implementation will grow in size proport

Interesting to note that since sCrypt's "loop" construct simply unrolls the loop the constant number of times, proposed implementation will grow in size proportionally to the number of state transition rules (8 in the example in the article). So a contract with 50 transition rules (or just carelessly bumped up constant N in the source code) would be much larger as it has to repeat its inner loop N times -- and there is nothing you can do about it, as functions and function calls are syntactic sugar as well, and function bodies are immediately inlined at the call site.

stephanfeb 5y ago
Where looping is concerned, you can either externalise the cost of looping by requiring some other entity with more resources to perform your computation for you, or you can pay upfront and commit satoshis to your computation. Regardless, you're still looping. All that is moot in my opinion though. The issue was settled a long time ago before Bitcoin's founding. “If a language L is accepted by a Turing Machine, then L is accepted by a two-stack machine” - Theorem (8.13) - Introduction to Automata Theory, Languages, and Computation - Hopcroft, Motwani & Ullman. Bitcoin's Script Interpreter is an implementation of 2-PDA (two-stack pushdown automata). What often happens in these debates is that folks conflate the Program, Language and Machine. Teasing these out to their discrete parts where Program is what sCrypt produces, Language is Bitcoin Script, and Machine is the Bitcoin Script Interpreter leads to more precise discussions. My position is that as per the Minsky Theorem, Bitcoin's Script Interpreter is Turing Equivalent. Memory and resource-constraints aside. Anyone who thinks that resource-constraints precludes a Machine from being "Turing Complete" should read papers like these: (Turing machines with restricted memory access) https://www.sciencedirect.com/science/article/pii/S0019995866800037 https://www.sciencedirect.com/science/article/pii/S001999586... If you want to dig deeper, then you can solve Bitcoin's State Transition function yourself. Here's a good worked example, but it requires that you have knowledge of Automata Theory: https://www.chegg.com/homework-help/questions-and-answers/machine-push-automata-2-stacks-diagram-example-push-automata-pda-two-stacks-septuple-m-k-1-q34191104 https://www.chegg.com/homework-help/questions-and-answers/ma...
- nullc 5y ago
  Thanks for giving us a concrete in-thread example of a person claiming the script interpreter is turing complete. The claim you're making regarding "two stacks" is technobabble initially created by Wright which was clearly discredited many years ago, e.g. https://www.reddit.com/r/btc/comments/6hjxiy/new_craig_wright_interview_part_2_on/diz9g69/ https://www.reddit.com/r/btc/comments/6hjxiy/new_craig_wrigh... In Bitcoin script the additional stack doesn't increase its computational power at all: Ignoring the operation count limits, any script using the altstack can be converted with the addition of some extra stack manipulation operations to one that doesn't use it at all.
  - stephanfeb 5y ago
    I disagree with @roconnor's assessment in the link provided. Just like that, I've "discredited" @roconnor. Folks are now free to reference this link in future posts as a claim that @roconnor's post has been discredited. See how that logic works ?
    - nullc 5y ago
      Roconnor explains his position, you do not. Roconnor is a published expert in this domain, in fact his PHD thesis ( https://r6.ca/thesis.pdf https://r6.ca/thesis.pdf ) was on formalizing and machine proving Gödel's incompleteness theorem. Instead, without justification or argument, you would like us to take the word of a person who failed the only theory of computation class he's taken and has been found by multiple courts to be an unreliable witness, a liar, and a forger-- a person for who has collected astounding sums on money on the promise of someday sharing some storied treasure which he-- as he's recently been forced to admit in court-- has no access to. I see how your logic works, and I expect that most readers of this thread will as well.
      - stephanfeb 5y ago
        Dude, you seem to have some personal beef with someone. In my above response to truth_machine I laid out a technical response on why I hold my point of view regarding the Turing Equivalence of Bitcoin. I suggest you stick to the tech (like I'm doing), and leave the personal drama at home, 'cause I'm not interested in hearing about whatever bun-fights you are engaged in with whoever it is you're referencing above. If you have a technical position of your own, I'd be glad to hear it. So far I've only heard appeals to the authority of a poorly-written, zero-detail, no-technical analysis opinion of someone I've never heard of until you started leaning on their opinions for claims in support of your position.

stephanfeb 5y ago

Where looping is concerned, you can either externalise the cost of looping by requiring some other entity with more resources to perform your computation for you, or you can pay upfront and commit satoshis to your computation. Regardless, you're still looping. All that is moot in my opinion though. The issue was settled a long time ago before Bitcoin's founding. “If a language L is accepted by a Turing Machine, then L is accepted by a two-stack machine” - Theorem (8.13) - Introduction to Automata Theory, Languages, and Computation - Hopcroft, Motwani & Ullman. Bitcoin's Script Interpreter is an implementation of 2-PDA (two-stack pushdown automata). What often happens in these debates is that folks conflate the Program, Language and Machine. Teasing these out to their discrete parts where Program is what sCrypt produces, Language is Bitcoin Script, and Machine is the Bitcoin Script Interpreter leads to more precise discussions. My position is that as per the Minsky Theorem, Bitcoin's Script Interpreter is Turing Equivalent. Memory and resource-constraints aside. Anyone who thinks that resource-constraints precludes a Machine from being "Turing Complete" should read papers like these: (Turing machines with restricted memory access) https://www.sciencedirect.com/science/article/pii/S0019995866800037 https://www.sciencedirect.com/science/article/pii/S001999586... If you want to dig deeper, then you can solve Bitcoin's State Transition function yourself. Here's a good worked example, but it requires that you have knowledge of Automata Theory: https://www.chegg.com/homework-help/questions-and-answers/machine-push-automata-2-stacks-diagram-example-push-automata-pda-two-stacks-septuple-m-k-1-q34191104 https://www.chegg.com/homework-help/questions-and-answers/ma...

nullc 5y ago
Thanks for giving us a concrete in-thread example of a person claiming the script interpreter is turing complete. The claim you're making regarding "two stacks" is technobabble initially created by Wright which was clearly discredited many years ago, e.g. https://www.reddit.com/r/btc/comments/6hjxiy/new_craig_wright_interview_part_2_on/diz9g69/ https://www.reddit.com/r/btc/comments/6hjxiy/new_craig_wrigh... In Bitcoin script the additional stack doesn't increase its computational power at all: Ignoring the operation count limits, any script using the altstack can be converted with the addition of some extra stack manipulation operations to one that doesn't use it at all.
- stephanfeb 5y ago
  I disagree with @roconnor's assessment in the link provided. Just like that, I've "discredited" @roconnor. Folks are now free to reference this link in future posts as a claim that @roconnor's post has been discredited. See how that logic works ?
  - nullc 5y ago
    Roconnor explains his position, you do not. Roconnor is a published expert in this domain, in fact his PHD thesis ( https://r6.ca/thesis.pdf https://r6.ca/thesis.pdf ) was on formalizing and machine proving Gödel's incompleteness theorem. Instead, without justification or argument, you would like us to take the word of a person who failed the only theory of computation class he's taken and has been found by multiple courts to be an unreliable witness, a liar, and a forger-- a person for who has collected astounding sums on money on the promise of someday sharing some storied treasure which he-- as he's recently been forced to admit in court-- has no access to. I see how your logic works, and I expect that most readers of this thread will as well.
    - stephanfeb 5y ago
      Dude, you seem to have some personal beef with someone. In my above response to truth_machine I laid out a technical response on why I hold my point of view regarding the Turing Equivalence of Bitcoin. I suggest you stick to the tech (like I'm doing), and leave the personal drama at home, 'cause I'm not interested in hearing about whatever bun-fights you are engaged in with whoever it is you're referencing above. If you have a technical position of your own, I'd be glad to hear it. So far I've only heard appeals to the authority of a poorly-written, zero-detail, no-technical analysis opinion of someone I've never heard of until you started leaning on their opinions for claims in support of your position.