<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">
<div><br>
</div>
<div> At least in an impredicative metatheory, the usual normalization argument should extend</div>
<div>to the addition of such positive recursive types in Agda (using Tarski's fixed point theorem</div>
<div>to define the computability at these types).</div>
<div><br>
</div>
<div> Best regards,</div>
<div> Thierry</div>
<div><br>
</div>
PS: This would be however incompatible with the addition of an impredicative universe U,
<div>
<div>since one can then form</div>
<div><br>
</div>
<div> R = mu X. (X-> U) -> U</div>
<div><br>
</div>
<div>and derive a contradiction from this following Reynolds' proof that there is no set theoretical</div>
<div>model of system F. </div>
<div><br>
</div>
<div>
<div>On Dec 18, 2013, at 6:22 PM, Aaron Stump wrote:</div>
<br class="Apple-interchange-newline">
<blockquote type="cite">
<div dir="ltr">
<div>Dear Wojtek,<br>
</div>
<div><br>
</div>
<div>Yes, I know about this example for recursive types which contain negative occurrences of the recursively defined type. But I am asking about positive but not strictly positive recursive types. An example is a type like the one Nils mentioned:</div>
<div><br>
</div>
<div>μA.∀R. (μX. (A → R) + X) → R</div>
<div><br>
</div>
<div>Here, the type variable A occurs to the left of an even number of arrows. This makes it positive (the even number of negations cancel out), but not strictly positive.</div>
<div><br>
</div>
<div>Cheers,</div>
<div>Aaron</div>
<div><br>
</div>
<div><br>
</div>
</div>
<div class="gmail_extra"><br>
<br>
<div class="gmail_quote">On Wed, Dec 18, 2013 at 11:14 AM, Wojciech Jedynak <span dir="ltr">
<<a href="mailto:wjedynak@gmail.com" target="_blank">wjedynak@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hello,<br>
<div class="im"><br>
> Ok, I see. Is it known that supporting non-strictly positive types would<br>
> have bad consequences in Agda? Not that I am suggesting it -- I am just<br>
> curious about what might be possible.<br>
<br>
</div>
Yes, it's possible to write a non-terminating expression using such a<br>
type. For instance, take a look here:<br>
<<a href="http://wiki.portal.chalmers.se/agda/pmwiki.php?n=ReferenceManual.BadInHaskell" target="_blank">http://wiki.portal.chalmers.se/agda/pmwiki.php?n=ReferenceManual.BadInHaskell</a>><br>
<br>
Best,<br>
Wojtek<br>
</blockquote>
</div>
<br>
</div>
_______________________________________________<br>
Agda mailing list<br>
<a href="mailto:Agda@lists.chalmers.se">Agda@lists.chalmers.se</a><br>
https://lists.chalmers.se/mailman/listinfo/agda<br>
</blockquote>
</div>
<br>
</div>
</body>
</html>