Computing with Infinite Objects

Computing with infinite objects

Hannes Diener
9th October

Computational barriers are important, but they are also often not quite located where we think they are.

There are

things that we think are computable that are not; and
things that we think are non-computable that are.

The general impression is that we have to work with finite objects or approximations on a computer:

integers are fine (we do have INT after all)
finite graphs are fine (we do have arrays, lists)
instead of reals we have to use floating point numbers

However, notice that INT is not the same as $ {\mathbb{Z}} $.

(Even Python's integers are not $\mathbb{Z}$.)

What if we wanted to work with subsets of the natural numbers?

Naive approach would be via lists.

A = [1,2,3]
B = [2,3,4]
print(3 in A) 
print(A+B)

Slightly better even:

A = set([1, 2, 3])
B = set([2,3,4])
print(3 in A) 
print(A.union(B))

However, what about infinite subsets of $\mathbb{N}$?

Idea: we have to change the characterisation.
Don't represent $A \subset \mathbb{N}$ as a collection of objects, but as its characteristic function.

Computers are good with functions, bad with sets

This leads to our updated version:

class menge:
  def __init__(self, chi): 
      self.chi=chi
  def __contains__(self,n): 
    return self.chi(n)

A=menge(lambda n : n%2 == 0)
B=menge(lambda n : n <= 20000)

print(20002 in A)
print(20002 in B)

What about unions, intersections, and other operations?

If we represent our objects by functions these are then functions taking functions as an input.

But that's exactly what functional programming languages can do.

Functional programming languages

"treat functions as first class citizens".

The final version:

class dec_set:
  def __init__(self, chi): 
    if type(chi) is set:
      self.chi=lambda n: n in chi
    else:
      self.chi=chi
  def __contains__(self,n): 
    return self.chi(n)
  def union(self,other):
    return dec_set(lambda n: n in self or n in other)
  def intersection(self,other):
    return dec_set(lambda n: n in self and n in other)
  def setminus(self,other):
    return dec_set(lambda n: n in self and not n in other)

B=dec_set(lambda n : n <= 20000)
A=dec_set(lambda n : n%2 == 0)

print(3 in A.union(B))

Pros

We can compute with infinite objects!
We can can guarantee results automatically.

Cons

We cannot test (among other things) for equality!
Somewhat slow.
We actually didn't capture all subsets of $\mathbb{N}$

But wait, there's more

We can represent a real number by a fast converging Cauchy sequence of rationals $ \left(r _{n} \right)_{n \geqslant 1}$, i.e. a sequence such that \[ |r_n - r_{n+m}| < \frac{1}{2^n} \]