Introduction

Mathematician David Hilbert came up with the following thought experiment: In an hotel of infinitely many rooms that is full, find a way to accomodate infinitely many new guests. His idea was to show that infinity can behave in counterintuitive ways. I've implemented a way to work with this kind of concepts using the Wolfram Language.

Computer languages are usually constrained to lists of finite size subjected to operations. For example, one may join, partition, sum, or nest them, and get a finite list as a result. Even though explicit infinite lists cannot be implemented in a computer, in this project I aim to provide the Wolfram Language with a symbolic calculus for lists of (countably) infinite length. That is, one would be able to treat expressions referring to infinite lists as arguments of operations, e.g, the infinite list of the roots of the natural numbers.

The main idea is to treat infinite lists as symbolical objects within the Wolfram Language, consisting of a generating rule for the elements on the list, where operations on infinite lists modify the generating functions, and values are only computed when explicitly asked for. All infinite lists are countably infinite.

Basic list operations

Most of the operations are extensions of the already existing Mathematica fucntions for lists. First I define the infinite list of the integers:

myInfiniteList= InfiniteRange[{-Infinity, Infinity}]
InfinitePrint[myInfiniteList]

InfinitePrint is a helpful tool to visualize some elements of infinite lists

{...,-5,-4,-3,-2,-1,0,1,2,3,4,5,...}

We can reverse this list, or drop all the negative elements to get the infinite list of the natural numbers.

InfiniteReverse[myInfiniteList]//InfinitePrint
(naturalNumbers=InfiniteDrop[myInfiniteList,{-Infinity,-1}]) //InfinitePrint

and we get

{...,5,4,3,2,1,0,-1,-2,-3,-4,-5,...}
{1,2,3,4,5,...}

With InfiniteSelect, we can obtain the prime numbers

 InfiniteSelect[naturalNumbers,PrimeQ]//InfinitePrint

with result

{2,3,5,7,11,...}

Infinite Matrices and Graphs

With the help of infinite lists, it is possible to work with matrices, which are nested infinite lists.

myInfiniteMatrix =
  InfiniteMatrix[ Function[{i, j}, 
    "[row " <> ToString[i] <> ",col " <> ToString[j] <> "]"]];
(*Take the first rows and columns*)
InfiniteTake[myInfiniteMatrix, 2, 3] // MatrixForm
InfiniteTake[myInfiniteMatrix, 4, 4] // MatrixForm

This is the infinite matrix that has "row i col j" in position $i,j$

Infinite matrices allow us to work with infinite graphs!

We can consider the graph with vertices the natural numbers, and where every number is connected its divisors

myGraphMatrix = 
  InfiniteMatrix[ Function[{x, y}, If[Mod[x, y] == 0, 1, 0]]];

Below is an animation of successive subgraphs from 1 vertex to 14 vertices. Of course, the number 1 is always at the center of the graph.

Applications to Cellular Automata

A neat application is that now we can have Cellular Automata that admit infinite initial conditions! For example, rule 90 gives interesting results:

(*Initial condition with a black cell every 7 cells*)
myInitialCondition = 
InfiniteList[0, Function[x,  If[Mod[x, 7] == 0, 1, 0]]];
 (*With a widht of 40 cells to either side, plot the first 10 steps*)
InfiniteCellularAutomatonPlot[90, myInitialCondition, 40, 10]

For a slightly more complicated result, consider an initial condition where only the cells in absolute prime number position (like 2 and -3) are black. This is the picture at the beginning of the post.

Notice there are differences if one uses the implemented Cellular Automata function with a similar but finite initial condition. Notice the extremes of the images below. First with infinite initial condition:

Now with finite initial condition where there is a black cell every 7 cells, but only in a finite range and the rest is white.

Conclusions and Future

I have extended most of the basic Mathematica functions for lists to infinite lists through symbolic manipulation, though partial explicit numerical results can be obtained. Two non trivial applications of this results are the capacity to define infinite graphs, and to work with Cellular Automata with an infinite initial condition.

It is still pendant to extend other Mathematica functions for finite lists to work with this project's approach for infinite lists in an optimal way. Also, an implementation could be explored for systems that in principle accept infinite initial conditions.

Please correct all my typos and grammatical mistakes, as English is not my native language :)

References

Hilbert's Parados of the Grand Hotel