Fixed Points


Functions & Functionals


Fixed point of a Function is defined as an input that is equal to its output. If  f(x) =x for a particular value of x, then that value of x is a fixed point of the function f(x). Some functions have no fixed points, some have one and some have many fixed points. Fix(f) denotes the set of fixed points of a function f. Example- f(x) =x2 - 2 has fixed points at x=(-1,2). When the input x is not a number but a function, the output also becomes a function at the fixed points if any and such functions are called Functionals. Hence functionals are functions that take a function for its input. Functional is also defined as a  function from a  vector space into its underlying scalar field, or a set of functions to the real numbers. If it is a Linear function from a linear vector space into its underlying scalar field, it is called linear functional. In other words, it is a function that takes a vector as its input argument, and returns a scalar. Commonly the vector space is a space of functions, thus the functional takes a function for its input argument, then it is sometimes considered a function of a function. Functionals are additive -> f(x+y) =f(x) + f(y). Functional derivatives are used in Lagrangian mechanics. Functional integrals were used by Feynman for path integral formulation of his quantum mechanics. Suppose in real coordinate space, the vector x is represented as column vector then the linear functional f(x) is where     



Using the concept of functionals and fixed points, one can eliminate explicit recursion for a function through 2 steps--

(1) Find a functional whose fixed point is the recursion function we select.

(2) Find the fixed point of a function without recursion.

A simple source transformation takes care of 1st method and Y combinator takes care of the 2nd step. Y combinator is expressed through λ calculus which is a programming language but contains only anonymous functions, function applications and variable references. Remarkably, this language is Turin -complete. The notation λ ν , e stands for the function that maps input ν to output e. Javascript supports anonymous functions.  λ ν. e = function(ν) {returns e;}. So if we can find a way to express Y Combinator  in the λ calculus, we can express it in JavaScript too. F ->a function, Y -> Y combinator, then Y(F) = F(Y(F)), in JavaScript function, Y(F) {returns FY(F) ;}. If we try to use it, it would never work because the function Y immediately calls itself leading to infinite incursion.We use λ calculus to wrap the call to Y such that Y(F) = F(λx,(Y(F))(x)). When we invoke the function Y, it immediately calls function F and passes it as λx.(Y(F))(x)) which is equivalent to Fixed point. This function will actually find fixed point of a functional and we could use it to eliminate recursion. We have not eliminated recursion but shifted it to function Y.