McCarthy's Amb Cannot Implement Fair Merge
Panangaden, Prakash; Shanbhogue, Vasant
In this paper, we establish that fair merge is a powerful non-deterministic primitive that cannot be implemented in terms of other well-known primitives. It is well known that fair merge embodies countable non-determinism. It is also been known that McCarthy's amb embodies countable non-determinism. It had not been known, however, whether amb could implement a fair merge. We show that countable non-determinism together with angelic non-determinism cannot implement fair merge even in dynamic dataflow networks. This settles a question posed by Abramsky over four years ago. Earlier work had suggested this result by showing that for static dataflow networks, one cannot implement fair merge using angelic merge.
computer science; technical report
Previously Published As