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)
x_next = AND(PC==40, μ * x * (1.0 – x))
- PC = AND(PC==40,50)
- x_next = AND(PC==20, 1)
- PC = AND(PC==20,30)
- x_next = AND(PC==20, 1) + AND(PC==40, μ * x * (1.0 – x)).
- [state] = AND(PC==l1,AND(A,[expression]))
- PC = AND(PC==l1,l2)
- PC = AND(AND(PC==50, NOT(NOT(x_next – x))), 30)
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.