Difference between revisions of "Talk:Script"

From Bitcoin Wiki
Jump to: navigation, search
m
(Common confusion on Turing-completeness.)
Line 28: Line 28:
  
 
It's absolutely important for the Bitcoin system that script's execution has an quickly checkable, bounded, and very short runtime. The relevance of turing completeness to any of that is easily and often overstated. The greater limits of script's expressiveness come from the computation bound, not the computational model. --[[User:Gmaxwell|Gmaxwell]] ([[User talk:Gmaxwell|talk]]) 05:47, 28 March 2015 (UTC)
 
It's absolutely important for the Bitcoin system that script's execution has an quickly checkable, bounded, and very short runtime. The relevance of turing completeness to any of that is easily and often overstated. The greater limits of script's expressiveness come from the computation bound, not the computational model. --[[User:Gmaxwell|Gmaxwell]] ([[User talk:Gmaxwell|talk]]) 05:47, 28 March 2015 (UTC)
 +
: I think that often when people talk about "Turing completeness", they mean that any program written in a normal programming language can ~always be compiled into any "Turing complete" language, even though this isn't really the definition of Turing completeness. You can write a program in C to calculate pi to the n<sup>th</sup> digit, and even if you were using regular C integers n could be pretty large without needing to modify the program. But the equivalent Script program would need to increase in size every time you increase the maximum size of n by 1, and this is what makes Script much weaker than C or any other normal programming language. [[User:Theymos|theymos]] ([[User talk:Theymos|talk]]) 18:32, 28 March 2015 (UTC)

Revision as of 18:32, 28 March 2015

xOP_IFDUP 115 0x73 x x / x x If the input is true or false, duplicate it.

Shouldn't it be: "If the input is true, duplicate it."? --ThePiachu 11:37, 20 December 2011 (GMT)

The byte vectors in the stack are specified as being signed integers of variable-length. Then there's an explanation that these integers are considered false if they are either zero or negative zero, which is 0x80. For this to be the case, the elements should be represented in an old binary format called sign-magnitude, which is important to state explicitly, since today virtually all computers use two's complement as representation, and there's no such thing as a negative zero. There's even another representation, one's complement, where negative zero looks like 0xff.

Reading the source code of the application, I see that arithmetic operations expect unsigned integers, for example, operations OP_2MUL and OP_2DIV are implemented as byte-shifting, which wouldn't work with signed representations.

It seems to me that, at best, variable-length sign-magnitued integer format is only used for testing for truth, although I haven't read all the code yet.

--Jean-Pierre Rupp 10:43, 4 March 2012 (GMT)

Provably Unspendable/Prunable Outputs

If im not mistaken this kind of transaction would not result in donating the output to the miner. It would instead make the output unusable by anyone forever. In my opinion the best and easiest way to donate to miner is just transfer BTC between your own addresses and set a high fee. Norill (talk) 22:32, 14 April 2013 (GMT)

norill: Fixed wording for OP_RETURN; it is mining fee in the example because the output value is zero, not 0.125BTC as I think you thought. Sorry about that.
Peter Todd (talk) 02:51, 23 July 2013 (GMT)

Common confusion on Turing-completeness.

Script isn't turing-complete under the precise definition of the term because it executes with bounded time and memory.

But by the precise definition a conventional desktop computer is also not "turing-complete": there are functions a universal turing machine can compute that a desktop cannot because the desktop computer runs out of memory first.

The precise definition isn't terribly useful for most people, since it excludes most things we think of as computers. Many people read the "not Turing-complete" as a statement that Script is only as expressive as a regular language or only capable of expressing monotone functions or something like that. Not so, if you ignore the time/memory bounds script is technically universal for computation. Consider the fragment "2 OP_PICK OP_IF OP_SWAP OP_ENDIF": This implements a fredkin gate which is universal and could just be wired up and repeated up to the operation limit Q.E.D.

It's absolutely important for the Bitcoin system that script's execution has an quickly checkable, bounded, and very short runtime. The relevance of turing completeness to any of that is easily and often overstated. The greater limits of script's expressiveness come from the computation bound, not the computational model. --Gmaxwell (talk) 05:47, 28 March 2015 (UTC)

I think that often when people talk about "Turing completeness", they mean that any program written in a normal programming language can ~always be compiled into any "Turing complete" language, even though this isn't really the definition of Turing completeness. You can write a program in C to calculate pi to the nth digit, and even if you were using regular C integers n could be pretty large without needing to modify the program. But the equivalent Script program would need to increase in size every time you increase the maximum size of n by 1, and this is what makes Script much weaker than C or any other normal programming language. theymos (talk) 18:32, 28 March 2015 (UTC)