1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
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 <roconnor@theorem.ca>) 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: <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
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: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=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 <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.''
|
