Message Boards Message Boards

[WSS18] A Calculus for Infinite Lists


Cellular Automaton with an infinite initial condition


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 is a helpful tool to visualize some elements of infinite lists


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

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

and we get


With InfiniteSelect, we can obtain the prime numbers


with result


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$ Parts of the Infinite matrix

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]

Rule 90. Initial condition: Black cell every seven spaces

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.

Initial conditions are primes

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:

Rule 90. Initial condition: Black cell every seven spaces

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.

rule 90 finite initial condition

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 :)


Hilbert's Parados of the Grand Hotel

11 days ago

enter image description here - Congratulations! This post is now a Staff Pick as distinguished by a badge on your profile! Thank you, keep it coming!

POSTED BY: Moderation Team
10 days ago

This is seriously cool. I would love to work with some infinite initial condition CA (prime number inited CA?? cool) or maybe graphs and such. Is there a way to see some of the code you made these functions in :-D ?

POSTED BY: Eric Parfitt
8 days ago

Group Abstract Group Abstract