Discrete Dynamical Systems and the mapcode approach to Algorithmic Problem Solving
Table of Contents
1 Introduction:
We study discrete dynamical systems, which are then used as a framework for algorithmic problem solving. Much of this material is from Chapters 1-2, "An introduction to Mathematical Computer Science, K Viswanath. Orient Blackswan, India 2008."
1.1 Discrete Dynamical System
A discrete dynamical system, also called a discrete flow, or a discrete process, is a tuple \(\pair{X,F}\) where \(X\) is a set called the state space and \(F\) is a function from \(X\) to \(X\), called the program map.
Here are simple examples of a dynamical system:
- \(\pair{\N,\id{incr}}\), where \(\id{incr}(x) = x+1\).
- \(\pair{\set{t, f},\id{inv}}\), where \(\id{inv}(x) = \set{t\mapsto\ f, f\mapsto\ t}\).
- \(\pair{\Z, \id{dim}}\) where
1.2 Trajectory
Let \(x\in X\). The trajectory of \(x\) wrt to the dynamical system \(\pair{X,F}\), written \(\id{tr}(x)\) is the infinite sequence
\[ \id{tr}(x) = [x, F(x), F(F(x)), F^{3}(x), \ldots]\]
1.3 Examples
- Consider \(\pair{\N, \id{incr}}\). Then
\[\id{tr}(4) = [4, 5, 6, \ldots]\]
Consider \(\pair{\Bool, \id{inv}}\). Then
\[ \id{tr}(t) = [t, f, t, \ldots]\]
- Consider \(\pair{\Z, \id{dim}}\). Then
\[ \id{tr}(4) = [4, 3, 2, 1, 0, 0, 0, \ldots]\]
\[ \id{tr}(-4) = [-4, -3, -2, -1, 0, 0, 0, \ldots]\]
\[ \id{tr}(0) = [0, 0, 0, \ldots]\]
1.4 Reachability
Let \(x,y\in X\). We say \(y\) is reachable from \(x\), if \(y=F^{n}(x)\) for some \(n\in N\). We also say that \(x\) reaches \(y\).
If \(x\) is an element of \(X\) and \(Y\) is a subset of \(X\), then we say that \(x\) reaches \(Y\) if \(x\) reaches some element of \(Y\).
1.5 Fixed point
Let \(F:X\rightarrow X\). An element \(x\in X\) is a fixed point of \(F\) if \(F(x) = x\). Let \(\id{fix}(F)\) denote the subset of \(X\) containing all fixed points of \(F\). Note that a function \(F\) may have 0, finite, or infinite number of fixed points.
1.6 Invariant sets
A subset \(A\) of \(X\) is an invariant set for \(F\) if for all \(x\in X\): \(x\in A\) implies \(F(x)\in A\). Another way of saying this is that \(F(A)\subseteq A\).
1.6.1 Examples
Consider the following system \(\pair{\N, x\mapsto x+2}\). Then both the subsets \(\id{evens} = \set{0, 2, 4, 6, \ldots}\) and \(\id{odds} = \set{1, 3, 5, 7, \ldots}\) are invariants for \(F\).
1.7 Convergent set
\(\id{con}(F)\) denotes the set of all elements \(x\) such that \(x\) reaches \(\id{fix}(F)\). We say that \(x\) is converges or terminates for \(F\) if \(x\in \id{con}(F)\).
1.8 Final state
Let \(x\) converge for \(F\). Let \(n\) be the smallest natural such that \(F^{n}(x)\) is a fixed point. Then, \(n\) is called the runtime of the computation starting with \(x\). \(F^n(x)\) is called the final state of the initial state \(x\).
1.9 Limit map
The function \(F^{\infty}:\id{con}(F)\rightarrow \id{fix}(F)\) is called the limit map of \(F\). If \(x\in \id{con}(F)\), we say that \(x\) terminates at \(F^\infty(x)\).
2 Algorithmic Problem Solving
Computers are useful for solving problems. That said, however, algorithmic problem solving requires that we first identify the problem precisely. Second, we mention the primitive operations that may be used by the algorithm to solve the problem.
A problem specification consists of
- An input space \(A\)
- An output space \(B\)
- A function \(f:A\rightarrow B\)
Note that this is the function for which we need to design an algorithm. We know the function, but not an algorithm that computes it.
2.1 Example: The factorial problem
Consider the factorial function \(!:\N\rightarrow \N\). Here the input and output spaces are both \(\N\). We are required to compute the factorial of a number using the following primitive operations:
- decrement operator on natural numbers \(n\mapsto n-1\)
- multiplication operator on naturals
- comparison with the natural number 0
2.2 The mapcode approach to problem solving
2.2.1 Problem
The mapcode approach to algorithmic problem solving starts with identifying a problem specification. This includes an input space \(A\), an output space \(B\) and a function \(f\) from the input to the output space.
2.2.2 Solution
The next step is to construct a solution. The solution is in two parts. The first consists of defining three components:
- A discrete dynamical system \(D=\pair{X,F}\)
- The state space \(X\) of \(D\) may be thought of the input space \(A\) augmented with more variables.
- An input map \(\rho:A\rightarrow X\)
- \(\rho\) maps the input space of the problem to the state space of \(D\).
- An output map \(\pi:X\rightarrow B\)
- \(\pi\) maps the state space of \(D\) to the output space of the problem.
2.2.3 Correctness
The second part of the solution requires proving that the trip \(\pair{\rho, D, \pi}\) solve the problem \(f\). This requires verifying the following properties.
- 0. \(\rho\), \(F\) and \(\pi\) use only the primitive operators.
- 1. \(\id{fix}(F)\) is non-empty.
- 2. \(\id{con}(F)\) is non-empty.
- 3. \(\id{codomain}(\rho) \subseteq \id{con}(F)\). (Termination)
- 4. \(\rho;F^\infty;\pi = f\) (Commute property)
The idea is that given an element \(a\) from \(A\), \(\rho\) maps \(a\) to \(\id{con}(F)\). This means that \(x=\rho(a)\) reaches a fixed point, say \(x^\infty=F^\infty(x)\). Then \(\pi\) maps \(x^\infty\) to an element in \(B\). The result of this should be equivalent to computing \(f\). That is, we expect, \(\rho; F^\infty; \pi = f\).
2.2.4 Commutative Diagram
The following commutative diagram summarizes the commute property \(\rho;F^\infty;\pi=f\).
\begin{array}{c} A & \ra{f} & B\\ \da{\rho} & & \ua{\pi} \\ X & \ra{F^\infty} & X \end{array}2.2.5 Invariant
The process of establishing the commutativity step usually requires designing an invariant. The invariant is true for the trajectory starting with \(\rho(a)\).
2.3 Mapcode framework to algorithmically solve the factorial problem
- Problem specification
- Input space is \(A=\N\).
- Output space is \(B=\N\).
- The function to be computed is \(!:\N\rightarrow \N\), the factorial function.
- Solution
Discrete Dynamical system \(D=\pair{X,F}\) where
- State space \(X\) is \(\N\times \N\).
- Program map is \(F:X\rightarrow X\) is defined as
- \(\rho: A\rightarrow X\) defined where \(\rho(n) = (n, 1)\).
- \(\pi: X\rightarrow B\) where \(\pi(i,a) = a\).
2.3.1 Sample Trajectories
2.3.2 Proof of Correctness
- \(\rho\), \(F\) and \(\pi\) use only the primitive operators
- This is true by inspecting the definitions of each of these functions.
- \(\id{fix}(F)\) is non-empty
- Note that every fixed point of \(F\) is of the form \((0, a)\) for \(a\in \N\). In other words, \(\id{fix}(F)= \set{0}\times \N\), which is non-empty.
- \(\id{con}(F)\) is non-empty
- Note that every initial state \((i,a)\) reaches a final state \((i, a^\infty)\) after exactly \(i\) steps. Hence \(\id{con}(F) = \N\times \N\), the entire state space, which is non-empty.
- \(\id{codomain}(\rho) \subseteq \id{con}(F)\) (Termination)
- Note that \(\id{con}(F) = X\), so this is trivially true. This implies termination, since an input \(n\in A\) is mapped to an element \((n,1)\) which converges after \(i\) steps.
- Invariant
- Given \(n\in \N\), let \(P(n)= \set{(i,a)\ |\ a*i! = n!}\). We show that \(P(n)\) is an invariant for \(F\). Assume \((i,a)\in P(n)\). We need to show that \(F(i,a)\in P(n)\). Now, \(F(i,a)=(i-1, a*i)\). Clearly, \((a*i)*(i-1)! = a*i! = n!\). The second equality is due to the assumption that \((i,a)\in P(n)\). Therefore \(F(i,a)\in P(n)\).
- \(\rho ; F^{\infty}; \pi = f\) (Commute Property)
- Let \(n\in A\). Then \(\rho(n) = (n, 1)\). Clearly, \((n,1)\in P(n)\). By induction on \(k\), \(F^{k}(n,1) \in P\). We know that \((n,1)\) terminates at \((0, a)\) for some \(a\) after \(n\) steps. Since \((0,a)\in P(n)\), it means that \(a*0! = n!\). From this, it follows that \(a = n!\). Since \(\pi(0,a)=a\), this just proves that \((\rho; F^{\infty};\pi)(n) = n!\).
3 Implementing the mapcode combinator
;;; fixed-point? : [F:[X -> X], x:X] -> boolean?
(define fixed-point?
(lambda (F x)
(equal? (F x) x)))
;;; mapcode : [init:[A -> X], F:[X -> X], done:[X -> B]] -> B
(define mapcode
(lambda (init F done) ;; \rho, F, \pi
(lambda (a)
(letrec ([loop
(lambda (x)
(if (fixed-point? F x)
(done x)
(loop (F x))))])
(loop (init a))))))
4 Factorial using mapcode
5 Factorial using mapcode
Here is factorial using mapcode
;;; !: nat? -> nat?
(define !
(mapcode
;; init
(lambda (n)
(list n 1))
;; next
(lambda (x)
(match x
[(list 0 a) x]
[(list i a) (list (sub1 i) (* a i))]))
;; done
second))
;;; test cases
(check-equal? (! 0) 1 "!0")
(check-equal? (! 2) 2 "!2")
(check-equal? (! 3) 6 "!3")
6 Tangle noexport
#lang racket
(provide (all-defined-out))
(require racket/list)
(require racket/match)
(require rackunit)
(require rackunit/text-ui)
(require "mapcode.rkt")
;;; !: nat? -> nat?
(define !
(mapcode
;; init
(lambda (n)
(list n 1))
;; next
(lambda (x)
(match x
[(list 0 a) x]
[(list i a) (list (sub1 i) (* a i))]))
;; done
second))
;;; test cases
(check-equal? (! 0) 1 "!0")
(check-equal? (! 2) 2 "!2")
(check-equal? (! 3) 6 "!3")