Introduction and motivation

In Computer Science a Problem (such as finding a shortest path in a graph) can be addressed by many Algorithms, and each algorithm can be implemented by many Programs. Regardless of what algorithm or program is chosen, all correct programs will possess the same number and types of Fixed Points or Halting Conditions. One way to say this mathematically is that the Dynamical Systems corresponding to each program are Topologically Conjugate. The dynamical systems are themselves related by a series of nonlinear coordinate transformations.

It would be fundamentally valuable to be able to automatically map out the solution space of any problem in terms of its fixed points. (This problem is itself NP-complete and so it may not be practical to do this for complex problems, but it is still of theoretical interest to have a mathematical framework that allows this). Applications are numerous, including automatic program and circuit verification, circuit routing, and numerical optimization.

This note talks about the basic problem of representation -- how a program is modeled as a dynamical system. It gives one example of a universal mapping.

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.