Looking for counterexamples to optimality by Levy - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T08:19:02Z http://mathoverflow.net/feeds/question/109762 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109762/looking-for-counterexamples-to-optimality-by-levy Looking for counterexamples to optimality by Levy Anton Salikhmetov 2012-10-15T21:06:37Z 2012-10-17T21:40:46Z <p>Let us encode \$λ\$-expressions into interaction nets as</p> <p><img src="http://ic.pics.livejournal.com/codedot/11832244/21617/21617_original.png" alt="usual"></p> <p>with both abstraction and application nodes being interaction combinator \$γ\$.</p> <p>For sharing nodes, let us choose such an agent \$ψ\$ that</p> <p>\$\$ ψ[γ(x, y), γ(z, t)] \bowtie γ[δ(x, z), δ(y, t)] \$\$</p> <p>and</p> <p>\$\$ ψ[δ(x, y), δ(z, t)] \bowtie δ[ψ(x, z), ψ(y, t)], \$\$</p> <p>with interaction combinator \$δ\$ involved.</p> <p>Please provide a counterexample to the resulting interaction system's optimality by Levy.</p>