Most functional programming languages provide functions that convert input arguments into output arguments without any means of converting outputs back to inputs. I have been working on instead building a system of reversible computing.
In 2012 I found two types of reversible functions that are considerably important: place forms and enumerations. Enumerations are bijections that use the natural numbers as inputs and place forms are bijections that like the cons function split up and put together objects. I have a sophisticated system of places in place.clj and enumerations in the enum.clj file.
Lists, which are an essential structure in Lisp, combine both of these two principles by defining data structures that associate values with an enumerated set of places. The nth function enumerates the places of the Lisp list structure.
Tuesday, January 1, 2013
Wednesday, December 26, 2012
Enumerative combinatorics
I have successfully enumerated a variety of mathematical structures by establishing a bijection between them and the natural numbers. Here are the first few sets and multisets:
(#{} #{0} #{1} #{0 1} #{2} #{0 2} #{1 2} #{0 1 2})
({} {0 1} {0 2} {1 1} {0 3} {1 2} {1 1, 0 1} {2 1})
The integers can be enumerated by defining the sign place as the first bit in a number and the absolute value as the value defined by the other bits:
(0 -0.0 1 -1 2 -2 3 -3 4 -4 5 -5)
The positive rational numbers can be enumerated by mapping over the enumeration of the multisets with an enumeration of the prime numbers and the enumeration of the integers.
(1 2 1/2 3 4 1/3 6 5 1/4 9)
All rational numbers can enumerated by using three places: a sign place with cardinality two, a natural part, and a fractional part. The fractional part is enumerated using eulers totient function.
Friday, December 14, 2012
Finite lattices
I have implemented the means to get the greatest upper bound and lowest upper bound of elements of a finite partial ordering relation. This can be used to completely define finite lattices such as the boolean lattice:
(transform-lattice
(enum false true)
(finite-lattice
[[0 1]
[1 1]]))
The partial ordering relation of a set is described by its adjacency matrix. This implies that the lattices module requires the adjacency matrices library as a dependency.
Thursday, November 29, 2012
Representations of monoid elements
Using place forms data structures may have different representations with respect to different monoids, for example, with respect to or the false value is equal to nil and the true value is a collection with a single element. Exclusive disjunction uses the same representation except its single generator is an involution rather then an idempotent element:
{false {}
true {1 1}}
Logical conjunction uses the negation of logical disjunction because these are the two elements of the boolean algebra with two distinct elements. Integers may be represented as the multiplicity of a single generator in an additive monoid, but in a multiplicative monoid they are a multiset with prime numbers as keys and exponents as values:
{1 12}
{2 2, 3 1}
Polynomials also have their on additive and multiplicative representations based upon factorization. The essential point here is that there may be many different representations of a single data structure depending upon the monoid that it is currently being handled by and these representations can be described by place forms.
Monday, November 26, 2012
Collections of monoid elements
All collections can be produced by monoids, for example, the concat operation produces ordered collections:
(= (concat '(1 2 3) '(4 5))
'(1 2 3 4 5))
Although monoids describe how to build these collections, places are needed in order to describe how to represent them. The nth place is used to describe ordered collections:
(= '(1 2 3)
{(nth 0) 1
(nth 1) 2
(nth 2) 3})
Multisets are produced by commutative monoids, and sets are produced by idempotent commutative monoids. Unordered collections are described by multiplicities. Furthermore, nil represents the empty collection.
(= (list-to-multiset '(1 1 2 3))
{1 2, 2 1, 3 1})
In partially commutative monoids unordered collections and ordered collections can be combined together to form a partially commutative collection.
Thursday, November 15, 2012
Logical operations
The values true and false form a boolean lattice with logical disjunction and logical conjuction as meet and join operators and not as complement: (lattice. #{false true} or and not). This lattice induces the total ordering relation false < true which corresponds to logical implication. There is a dual lattice based upon the ordering relation true < false which uses converse implication.
The disjunction and conjunction operators are commutative monoids with a single non-trivial idempotent element. We can also form abelian groups with a single non-trivial involution element: logical biconditional and exclusive disjunction.
These abelian groups can be extended with a multiplication operation to form the finite field. The logical biconditional uses disjunction as multiplication and the exclusive disjunction uses conjunction as multiplication.
Exponentation has no effect in this finite field, so all polynomials can be reduced to binomials. Using zero as false and one as true all the polynomials in this field can be expressed as 0, 1, x, and x+1.
The disjunction and conjunction operators are commutative monoids with a single non-trivial idempotent element. We can also form abelian groups with a single non-trivial involution element: logical biconditional and exclusive disjunction.
These abelian groups can be extended with a multiplication operation to form the finite field. The logical biconditional uses disjunction as multiplication and the exclusive disjunction uses conjunction as multiplication.
Exponentation has no effect in this finite field, so all polynomials can be reduced to binomials. Using zero as false and one as true all the polynomials in this field can be expressed as 0, 1, x, and x+1.
Friday, November 2, 2012
Local extrema of continuous functions
Reversible continuous functions such as the increment function and the cube function have no extrema and therefore they are either monotone increasing or monotone decreasing on their entire domain. The square function has a single extrema at the origin because it is monotone increasing on the positive numbers and monotone decreasing on the negative numbers.
Local extrema can be determined by the first derivative of a function. For example, polynomials with positive coefficients always have derivative with positive coefficients so they can never have any positive extrema. For example, the exp function we has coefficients that are all positive reciprocals of the factorial numbers, is always reversible on the positive real numbers by the ln function.
Local extrema can be determined by the first derivative of a function. For example, polynomials with positive coefficients always have derivative with positive coefficients so they can never have any positive extrema. For example, the exp function we has coefficients that are all positive reciprocals of the factorial numbers, is always reversible on the positive real numbers by the ln function.
Subscribe to:
Posts (Atom)