Date: Thu, 29 Dec 2011 11:42:56 -0500 (EST)
From: roconnor@theorem.ca
To: bitcoin-development@lists.sourceforge.net
In-Reply-To: <1325148259.14431.140661016987461@webmail.messagingengine.com>
Message-ID: <alpine.LRH.2.00.1112291135040.22327@theorem.ca>
References: <alpine.LRH.2.00.1112290111310.22327@theorem.ca>
	<1325148259.14431.140661016987461@webmail.messagingengine.com>
User-Agent: Alpine 2.00 (LRH 1167 2008-08-23)
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; format=flowed; charset=US-ASCII
Subject: Re: [Bitcoin-development] Alternative to OP_EVAL
Precedence: list

On Thu, 29 Dec 2011, theymos wrote:

> On Thu, Dec 29, 2011, at 01:55 AM, roconnor@theorem.ca wrote:
>> The number of operations executed is still bounded by the number of
>> operations occurring in the script.  With the OP_EVAL proposal the
>> script language becomes essentially Turing complete, with only an
>> artificial limit on recursion depth preventing arbitrary computation
>> and there is no way to know what code will run without executing it.
>
> Even if OP_EVAL allowed infinite depth, you'd still need to explicitly
> specify all operations performed, since there is no way of looping.

That's not true.  Gavin himself showed how to use OP_EVAL to loop:
OP_PUSHDATA {OP_DUP OP_EVAL} OP_DUP OP_EVAL.

Basically OP_DUP lets you duplicate the code on the stack and that is the 
key to looping.  I'm pretty sure from here we get get Turing completeness. 
Using the stack operations I expect you can implement the SK-calculus 
given an OP_EVAL that allows arbitrary depth.

OP_EVAL adds dangerously expressive power to the scripting language.

-- 
Russell O'Connor                                      <http://r6.ca/>
``All talk about `theft,''' the general counsel of the American Graphophone
Company wrote, ``is the merest claptrap, for there exists no property in
ideas musical, literary or artistic, except as defined by statute.''