1. Overview

These notes concern modeling computer programs as discrete dynamical systems. In this discussion the trace of a computation corresponds to the trajectory of a dynamical system.

A computer program executing on a digital computer with electronic memory is a finite state automaton, equivalent to a Turing machine with a finite tape. The state space of the automaton is the space of variables defined by the program, along with environmental information such as a program counter. At every instant of discrete time the automaton transitions from one state to another based on the instructions of the program. The computer program is thus a discrete map on the state space of the program variables.

The next section shows how to represent any computer program as a differentiable discrete dynamical system, and present an example of a program that computes the logistic map.

2. Compilation to differentiable map.

Our goal is to convert a computer program into a differentiable map. We will construct the map using arithmetic, exponentiation and trigonometry. The set of functions {and, or, not} is Turing complete, that is, it is sufficient to represent any computable function. So we can achieve Turing completeness by representing this set of functions in a differentiable form and then reducing computer programs to these elementary functions.

We will assume our computer has real arithmetic and will ignore the consequences of finite precision arithmetic. This is a technicality. Represent TRUE by the value 1 and FALSE by 0. Then

AND(A,B) = A*B
  • OR(A,B) = (1+e-t)-1, t = (A+B)*12-6 // sigmoid function
  • NOT(A) = cos(A*pi/2)

Note that these three functions are differentiable.

Consider the program that computes values of the logistic map xn+1 = μ xn(1-xn) in figure 1. It’s a convenient example because we can control its behavior with a single parameter.
10 μ = 1.0
20 x_next = 1
30 x = x_next
40 x_next = μ * x * (1.0 – x)
50 if((x_next – x) != 0) goto 30
60 goto 60 // terminating fixed point

Figure 1: Program 1.

We want to convert this program into a single map constructed from our three differentiable functions and arithmetic. The arithmetic expression can be translated directly, as can be the assignments. In addition to the program variables there is a program counter which points to the currently active program statement. We will call this variable PC. Every statement in the program generates terms in the map of the form

[state] = AND(PC==l1,[expression])
  • PC = AND(PC==l1,l2)
Here l1 and l2 are line numbers in the program. [expression] is a computable expression involving arithmetic and the three differentiable functions, and [state] is the set of variables modified by [expression]. The equality operator A==B is shorthand for NOT(A-B). For example, line 40 of the program generates the terms

x_next = AND(PC==40, μ * x * (1.0 – x))
  • PC = AND(PC==40,50)
The terms for the same state are combined, so for example the assignment of x_next in line 40 is combined with the assignment in line 20 which has the terms
  • x_next = AND(PC==20, 1)
  • PC = AND(PC==20,30)
In addition to combining the terms that result from program statements each state variable has a term of the form “else [state] = [state]”. The terms for variables that involve only logical expressions are combined using OR functions. In contrast when a variable involves arithmetic expressions, as is the case for x_next, the terms are summed together. The map for x_next is thus
  • x_next = AND(PC==20, 1) + AND(PC==40, μ * x * (1.0 – x)).
The statement “goto X” generates the assignment “PC=x”. A statement of the form “if(A)B” generates terms of the form
  • [state] = AND(PC==l1,AND(A,[expression]))
  • PC = AND(PC==l1,l2)
Line 50 is a slightly more complex example of this, since it has to handle both the TRUE and FALSE values of the conditional expression.
  • PC = AND(AND(PC==50, NOT(NOT(x_next – x))), 30)
PC = AND(AND(PC==50, NOT(x_next – x)), 60)

A complete hand-compilation of program 1 in the form of a differentiable map appears in figure 2. In terms of the form “AND(else,[state])” “else” is shorthand for the negation of all of the other AND conditions for that [state].

PC= OR(OR(OR(OR(OR(OR(OR(OR(
AND(PC==10,20),
AND(PC==20,30)),
AND(PC==30,40)),
AND(PC==40,40)),
AND(PC==40,50)),
AND(AND(PC==50, NOT(NOT(x_next – x))), 30)),
AND(AND(PC==50, NOT(x_next – x)), 60)),
AND(PC==60,60),
AND(else,PC))
μ= OR(AND(PC==10,1.0), AND(else, μ))
x_next = AND(PC==20,1) + AND(PC==40, μ * x * (1.0 – x)) + AND(else, x_next)

Figure 2: Complete compilation of program 1 in terms of elementary functions.