3
$\begingroup$

While reading Wikipedia, I ran across a proof given on 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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Daniel Apon Jan 23 '11 at 17:27
4
$\begingroup$

When in doubt, consult the original source: Clinger's Thesis. 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 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).

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.

$\endgroup$
  • $\begingroup$ <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> $\endgroup$ – Edwin Earl Ross Jan 23 '11 at 19:49
  • $\begingroup$ I've expanded my answer. I hope it helps. $\endgroup$ – Dave Clarke Jan 23 '11 at 23:55
  • $\begingroup$ 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. $\endgroup$ – Edwin Earl Ross Jan 24 '11 at 23:17
  • $\begingroup$ My pleasure, Edwin. $\endgroup$ – Dave Clarke Jan 25 '11 at 7:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.