📅 Original date posted:2011-12-29
🗒️ Summary of this message: OP_EVAL proposal makes the script language Turing complete, with no limit on recursion depth, allowing arbitrary computation, and looping.
📝 Original message:On Thu, 29 Dec 2011, theymos wrote:
> On Thu, Dec 29, 2011, at 01:55 AM, roconnor at 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.''
roconnor at theorem.ca [ARCHIVE] /
npub1a3…zue3f
2023-06-07 02:53:09
in reply to nevent1q…68t6
Author Public Key
npub1a39ym06slzfdspsuxq2jqcf2u8cddq6sml6w8c28ql28gxw42grqlzue3fPublished at
2023-06-07 02:53:09Event JSON
{
"id": "7979c4250db244762ea6eb9e602c057986aa1f6c419c52bc49ca379bc5c16b8d",
"pubkey": "ec4a4dbf50f892d8061c301520612ae1f0d68350dff4e3e14707d47419d55206",
"created_at": 1686106389,
"kind": 1,
"tags": [
[
"e",
"9a940b93a02313cdd87199fd3d7a873bc06ba92e835205564dcc696f8e0046db",
"",
"root"
],
[
"e",
"680c271c6a80a77ee670cf8da13540c1c166e5f605dd941144a36f16e6659c13",
"",
"reply"
],
[
"p",
"7b17a27b7a85e67ba7923c452fbb08ed536244f667a20168dfc3172a83c992df"
]
],
"content": "📅 Original date posted:2011-12-29\n🗒️ Summary of this message: OP_EVAL proposal makes the script language Turing complete, with no limit on recursion depth, allowing arbitrary computation, and looping.\n📝 Original message:On Thu, 29 Dec 2011, theymos wrote:\n\n\u003e On Thu, Dec 29, 2011, at 01:55 AM, roconnor at theorem.ca wrote:\n\u003e\u003e The number of operations executed is still bounded by the number of\n\u003e\u003e operations occurring in the script. With the OP_EVAL proposal the\n\u003e\u003e script language becomes essentially Turing complete, with only an\n\u003e\u003e artificial limit on recursion depth preventing arbitrary computation\n\u003e\u003e and there is no way to know what code will run without executing it.\n\u003e\n\u003e Even if OP_EVAL allowed infinite depth, you'd still need to explicitly\n\u003e specify all operations performed, since there is no way of looping.\n\nThat's not true. Gavin himself showed how to use OP_EVAL to loop:\nOP_PUSHDATA {OP_DUP OP_EVAL} OP_DUP OP_EVAL.\n\nBasically OP_DUP lets you duplicate the code on the stack and that is the \nkey to looping. I'm pretty sure from here we get get Turing completeness. \nUsing the stack operations I expect you can implement the SK-calculus \ngiven an OP_EVAL that allows arbitrary depth.\n\nOP_EVAL adds dangerously expressive power to the scripting language.\n\n-- \nRussell O'Connor \u003chttp://r6.ca/\u003e\n``All talk about `theft,''' the general counsel of the American Graphophone\nCompany wrote, ``is the merest claptrap, for there exists no property in\nideas musical, literary or artistic, except as defined by statute.''",
"sig": "d9d54edf4aa7e50f10a5e0cc907e1595a3dfca04a3348f783e7c8881747c5868f952fb51fb000f8daf6a0511ae72817b2c953aa03f9b6ed620540d5392fcf937"
}