<p>When in doubt, consult the original source: <a href="http://dspace.mit.edu/handle/1721.1/6935" rel="nofollow">Clinger's Thesis</a>. Clinger shows that fair merge cannot be written in a nondeterministic dataflow program. He does this by considering the semantic domains in which such a function would be defined, ultimately deriving a contradiction to the assumption that fair merge exists.</p>

<p>Firstly, as Daniel Apon points out, $merge(\bot,1^\omega)=\{1^\omega\}$. This is the only reasonable definition of merge for these arguments (see page 84 of Clinger's thesis). </p>

<p>Secondly, $merge(\bot,1^\omega)\subseteq merge(0,1^\omega)$, because  $\bot\le 0$, as stream $0$ is a possible extension of stream $\bot$ (bottom of page 73),  and by assumption $merge$ is monotone. In more detail, the ordering on the domain of strings states that any prefix of a string, is $\le$ the string, thus the empty string $\bot$ is the smallest element, and hence $\bot\le 0$, where $0$ is the string with just the element $0$. The function $merge$ has type $S\times S\to\mathcal{P}(S)$, where $S$ is string and $\mathcal{P}(-)$ is powerset.  The assumption that $merge$ is monotone means that if $a\le b$ then $merge(a,s)\subseteq merge(b,s)$. (Similarly for the second argument.) </p>

<p>Now $1^\omega\in merge(0,1^\omega)$ violates the assumption that $merge$ is fair – a fair merge of $0$ and $1^\omega$ should to contain the $0$. In more detail, $merge(S,T)$ is interleaving the "cards" from $S$ and $T$, without shuffling them. The significance of the stream $1^\omega$ is that it is infinite. $0$ is simply some character different from $1$. A fair merge of $0$ and $1^\omega$ should result in a string such as $1^*01^\omega$. Fairness means that within some finite time it selects elements from each string, thus the character $0$ is eventually chosen.</p>

<p>Hence $merge$ cannot be written as a nondeterministic dataflow program. </p>

CC BY-SA 2.5
2011-01-23T19:49:52.243Z
<p>Thanks, Dave Carke, I still do not understand why 1<sup>ω</sup> ∈ <i>merge</i>(0,1<sup>ω</sup>). The <i>merge</i>(S,T) is similar shuffling cards, if I understand correctly. Is there some special significance to either of the streams 0 or 1<sup>ω</sup>? </p>
Edwin Earl Ross
CC BY-SA 2.5
2011-01-23T23:55:25.240Z
I've expanded my answer. I hope it helps.
Dave Clarke
CC BY-SA 2.5
2011-01-24T23:17:57.290Z
Thanks for your patience Dave. It finally dawned on me, I haven't looked critically at a proof in a very long time; otherwise, I might have got it in the first place.
Edwin Earl Ross
CC BY-SA 2.5
2011-01-25T07:51:20.007Z
My pleasure, Edwin.
Dave Clarke
CC BY-SA 2.5
2011-01-23T18:18:49.653Z
2011-01-24T00:11:44.143Z
2011-01-24T00:11:44.143Z
Dave Clarke
<p>While reading Wikipedia, I ran across a proof given on <a href="http://en.wikipedia.org/wiki/Unbounded_nondeterminism" rel="nofollow noreferrer">Unbounded Nondeterminism</a> that I do not understand.</p>
<p>
The proof is given as,<blockquote>
An example of the role of fair or unbounded nondeterminism in the merging of strings was given by William D. Clinger, in his 1981 thesis. He defined a "fair merge" of two strings to be a third string in which each character of each string must occur eventually. He then considered the set of all fair merges of two strings merge(S, T), assuming it to be a monotone function. Then he argued that merge(⊥,1<sup>ω</sup>)⊆ merge(0,1<sup>ω</sup>), where ⊥ is the empty stream. Now merge(⊥,1<sup>ω</sup>) = 1<sup>ω</sup>, so it must be that 1<sup>ω</sup> is an element of merge(0,1<sup>ω</sup>), a contradiction. 
</blockquote>
</p>
<p>
My misunderstanding is, "merge(⊥,1<sup>ω</sup>) = 1<sup>ω</sup>." Previously it said that "merge(S, T)" is "the set of all fair merges of two strings". 
</p>
<p>
Why is "merge(⊥,1<sup>ω</sup>) = 1<sup>ω</sup>," instead of merge(⊥,1<sup>ω</sup>) = {1<sup>ω</sup>}. If so, isn't {1<sup>ω</sup>} ⊆  merge(0,1<sup>ω</sup>)? What am I missing?
</p>

CC BY-SA 2.5
2011-01-23T17:27:10.027Z
Looks like a typo... "If merge(⊥,$1^ω$) = {$1^ω$} and merge(⊥,$1^ω$) $\subseteq$ merge(0,$1^ω$), then $1^ω$ is an element of merge(0,$1^ω$)." would appear to be the correct step in the proof.
Daniel Apon
<dc.parallel-comp><proofs>
No Fair Merge via Nondeterminstic Data Flow Streams
Edwin Earl Ross
# No Fair Merge via Nondeterminstic Data Flow Streams

(Asked by: username_0 on 2011-01-23)

While reading Wikipedia, I ran across a proof given on [Unbounded Nondeterminism](http://en.wikipedia.org/wiki/Unbounded_nondeterminism) that I do not understand.

The proof is given as,
> An example of the role of fair or unbounded nondeterminism in the merging of strings was given by William D. Clinger, in his 1981 thesis. He defined a "fair merge" of two strings to be a third string in which each character of each string must occur eventually. He then considered the set of all fair merges of two strings merge(S, T), assuming it to be a monotone function. Then he argued that merge(⊥,1ω)⊆ merge(0,1ω), where ⊥ is the empty stream. Now merge(⊥,1ω) = 1ω, so it must be that 1ω is an element of merge(0,1ω), a contradiction.

My misunderstanding is, "merge(⊥,1ω) = 1ω." Previously it said that "merge(S, T)" is "the set of all fair merges of two strings".

Why is "merge(⊥,1ω) = 1ω," instead of merge(⊥,1ω) = {1ω}. If so, isn't {1ω} ⊆ merge(0,1ω)? What am I missing?

**Tags:** dc.parallel-comp, proofs

> **Comments:**
> **username_1**: Looks like a typo... "If merge(⊥,$1^ω$) = {$1^ω$} and merge(⊥,$1^ω$) $\subseteq$ merge(0,$1^ω$), then $1^ω$ is an element of merge(0,$1^ω$)." would appear to be the correct step in the proof.  

---

## 1 answers

### Answer by username_2 on 2011-01-23. Score: 4

When in doubt, consult the original source: [Clinger's Thesis](http://dspace.mit.edu/handle/1721.1/6935). Clinger shows that fair merge cannot be written in a nondeterministic dataflow program. He does this by considering the semantic domains in which such a function would be defined, ultimately deriving a contradiction to the assumption that fair merge exists.

Firstly, as username_1 points out, $merge(\bot,1^\omega)=\{1^\omega\}$. This is the only reasonable definition of merge for these arguments (see page 84 of Clinger's thesis).

Secondly, $merge(\bot,1^\omega)\subseteq merge(0,1^\omega)$, because $\bot\le 0$, as stream $0$ is a possible extension of stream $\bot$ (bottom of page 73), and by assumption $merge$ is monotone. In more detail, the ordering on the domain of strings states that any prefix of a string, is $\le$ the string, thus the empty string $\bot$ is the smallest element, and hence $\bot\le 0$, where $0$ is the string with just the element $0$. The function $merge$ has type $S\times S\to\mathcal{P}(S)$, where $S$ is string and $\mathcal{P}(-)$ is powerset. The assumption that $merge$ is monotone means that if $a\le b$ then $merge(a,s)\subseteq merge(b,s)$. (Similarly for the second argument.)

Now $1^\omega\in merge(0,1^\omega)$ violates the assumption that $merge$ is fair – a fair merge of $0$ and $1^\omega$ should to contain the $0$. In more detail, $merge(S,T)$ is interleaving the "cards" from $S$ and $T$, without shuffling them. The significance of the stream $1^\omega$ is that it is infinite. $0$ is simply some character different from $1$. A fair merge of $0$ and $1^\omega$ should result in a string such as $1^\*01^\omega$. Fairness means that within some finite time it selects elements from each string, thus the character $0$ is eventually chosen.

Hence $merge$ cannot be written as a nondeterministic dataflow program.

> **Comments:**
> **username_0**: <p>Thanks, Dave Carke, I still do not understand why 1<sup>ω</sup> ∈ <i>merge</i>(0,1<sup>ω</sup>). The <i>merge</i>(S,T) is similar shuffling cards, if I understand correctly. Is there some special significance to either of the streams 0 or 1<sup>ω</sup>? </p>  
> **username_2**: I've expanded my answer. I hope it helps.  
> **username_0**: Thanks for your patience Dave. It finally dawned on me, I haven't looked critically at a proof in a very long time; otherwise, I might have got it in the first place.  
> **username_2**: My pleasure, Edwin.  

---

