Received: from sog-mx-3.v43.ch3.sourceforge.com ([172.29.43.193] helo=mx.sourceforge.net) by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1RgJ4I-00031F-Nn for bitcoin-development@lists.sourceforge.net; Thu, 29 Dec 2011 16:43:02 +0000 X-ACL-Warn: Received: from erdos.theorem.ca ([72.2.4.176] helo=theorem.ca) by sog-mx-3.v43.ch3.sourceforge.com with smtp (Exim 4.76) id 1RgJ4H-0001YU-NW for bitcoin-development@lists.sourceforge.net; Thu, 29 Dec 2011 16:43:02 +0000 Received: (qmail 20239 invoked by uid 603); 29 Dec 2011 16:42:56 -0000 Received: from localhost (sendmail-bs@127.0.0.1) by localhost with SMTP; 29 Dec 2011 16:42:56 -0000 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: References: <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 X-Spam-Score: -1.6 (-) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -1.3 RP_MATCHES_RCVD Envelope sender domain matches handover relay domain -0.3 AWL AWL: From: address is in the auto white-list X-Headers-End: 1RgJ4H-0001YU-NW Subject: Re: [Bitcoin-development] Alternative to OP_EVAL X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 29 Dec 2011 16:43:02 -0000 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 ``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.''