# Difference between revisions of "Talk:Script"

m (→Provably Unspendable/Prunable Outputs: also fix spelling for peter. :)) |
(→Common confusion on Turing-completeness.: new section) |
||

Line 18: | Line 18: | ||

: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. | :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. | ||

:[[User:Petertodd|Peter Todd]] ([[User talk:Petertodd|talk]]) 02:51, 23 July 2013 (GMT) | :[[User:Petertodd|Peter Todd]] ([[User talk:Petertodd|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 some kind only capabile 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 [[w:fredkin gate]] which is universal 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. --[[User:Gmaxwell|Gmaxwell]] ([[User talk:Gmaxwell|talk]]) 05:47, 28 March 2015 (UTC) |

## Revision as of 05:47, 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 some kind only capabile 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 w:fredkin gate which is universal 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)