Working on Real Computation, it is unavoidable to face multivaluedness. Considering the fact that real numbers have undecidable equality, (speaking in terms of Bishop’s, it’s LPO), the following simple algorithm is not computable:

if(x > 0) ... else ...

if the variable x represents a real number. Instead, with some tolerance factor \(e\),
iRRAM supports such syntax:

if(choose(x > - e, e > x) == 1) ... else ...

The iRRAM choose function returns the index whose corresponding expression gets evaluated to be True; it can be implemented via parallel evaluation of the both expressions, returning the index of whose expression happens to hold first. Hence, even if one expression leads to Bottom, e.g., when x = - e , the choose function works! But, what does happen if both expressions happen to be truth?

Obviously, the one which holds first would be returned. If both are evaluated to be true at the same time, we can make some protocol which to return. This is the matter of the fact of implementation of the language; we can design the language to evaluate the second expression two steps whereas the first expression one step. Therefore, an abstract semantic of the choose function should be a set function whose output is a set of all indexes whose corresponding expressions hold; in abstract semantics, we do not want to talk about how the choose function and real number representations are implemented.

One common mistake in first understanding this multivaluedness is that the nondeterminism is an illusion which is only the matter of implementation; some think that when we fix a real number \(x\), the nondeterminism does not occur. However, this is not the case! Let us fix \(x=0\) and let \(e=0.1\). Let us consider two representations of the \(x\):

  1. \[x = [0,1] :: [0,0.5] :: [0,0.25] :: \cdots\]
  2. \[x = [-1,0] :: [-0.5,0] :: [-0.25,0] :: \cdots\]

The two sequences of closed intervals are valid names for \(0\) as they both converges to \(0\). However, we can see that choose(x > - e, e > x) == 1 is True for the case 1 and False for the case 2. Even if we fix a real number \(x\) and the way of implementing the choose function, multivaluedness happens.

Now, let us take this into the view of representation. With \(N\) denoting a set of natural numbers, \(B := N^N\) is a Baire space. Let \(n_A : B \rightharpoonup A\) be a surjective partial function. If \(n_A(x) = a\) we say \(x\) realizes \(a\) and put \(x \Vdash_A a\). Similarly, for a function \(f : A \to C\), if \(\tau : B \to B\) exists such that \(\forall a b. b \Vdash_A a \to \tau(b) \Vdash_B f(a)\) we call that \(\tau\) tracks the function \(f\).

Now, let us think in the opposite direction. Consider we have a function \(\tau : B \to B\). What does the function \(\tau\) mean? We can notice that this is just a boring function that receives an infinite sequence of natural numbers and just keep printing endless sequence of natural numbers. In order to give a meaning of the boring function, we can try to give meanings to its domain and codomain. Suppose we let \(n_A\) and \(n_C\) be the representations of its domain and codomain.

Since \(n_A\) does not need to be injective, for an element \(x \in A\), there can be several different names \(n^{-1}_A(\{x\})\); see that a real number is such a case. If \(n_C(\tau(n^{-1}_A(\{x\})))\) is a singleton for all \(x\), then we can define the meaning of \(\tau\); let \(\chi : P(A) \rightharpoonup A\) be a trivial choice function from singleton subsets of \(A\). Then, \(Meaning(\tau, n_A, n_C) := x \mapsto \chi(n_C(\tau(n^{-1}_A(\{x\}))))\).

If the set \(n_C(\tau(n^{-1}_A(\{x\})))\) is not a singleton, which is the case of the displayed simple iRRAM program, then, its meaning becomes the multivalued map which can be understood as a set valued function: \(Meaning(\tau, n_A, n_C) : A \to P(C) := x \mapsto n_C(\tau(n^{-1}_A(\{x\}))).\) It is a little unsatisfactory for me that its meaning is a function to \(P(B)\)… What we compute with the \(\tau, n_A, n_C\) given \(x \Vdash_A n_A(x)\) is an element of \(\tau(x) \Vdash_C n_C(\tau(x))\) not a set of elements.

See more:

[1] iRRAM is a C++ library which enables the computation of real numbers. See the link for the further information, Click

[2] For the further information and studying materials for real computation via computable analysis, see Weihrauch, Klaus. Computable analysis: an introduction. Springer Science & Business Media, 2012.

[3] The notions of realizability/functions in baire space tracking, can be studied in Bauer, Andrej. “Realizability as the connection between computable and constructive mathematics.” Proceedings of CCA. 2005.