Enzymind Labs

"It is remarkable that the deepest ideas of number theory reveal a far-reaching resemblance to the ideas of modern theoretical physics. ... One would like to hope that this resemblance is no accident, and that we are already hearing new words about the World in which we live, but we do not yet understand their meaning."
Yuri I. Manin, pg. 99 in "Mathematics and Physics" (translation of "Matematika i fizika", Birkhauser, Boston 1981)

"As knowledge increases, the attitude of science toward the things of the invisible world is undergoing considerable modification. Its attention is no longer directed solely to the earth with all its variety of objects, or to the physical worlds around it; but it finds itself compelled to glance further afield, and to construct hypotheses as to the nature of the matter and force which lie in the regions beyond the ken of its instruments."
Annie Wood Besant in "Thought Forms", 1905

 

The simplicity of recursive sequences guarantees that they will be related to many topics. Some of these topics are mathematical, some physical, and some are in relation to modeling physical phenomena. In addition to a short discussion of how recursive sequences show their stripes in various fields of study, the various equivalent formal expressions and descriptive language is briefly described. There are different ways of skinning a cat, but the result is always a skinned cat.

Math, geometry:

Recursive sequences and number theory

[To Do: Recursive sequences and numeral systems]

[To Do: Analysis, infinite series]

[ To Do: Infinite sums examples, and relation to infinte sequences. These systems are just such infinite sequences, so can be viewed as sinfinite sums. 0101... and 1010... example. Aperiodic deterministic sequences are irrational numbers (and at least some are trancendental numbers ).]

[To Do: Finite geometry combinatorics, group theory. e.g. Steven H. Cullinane's geometry of the square and cube , and "Diamond Theory "]

[To Do: Analysis, infinite series]

Symbolic dynamics

In mathematics, symbolic dynamics is the practice of modelling a topological or smooth dynamical system by a discrete space consisting of infinite sequences of abstract symbols, each of which corresponds to a state of the system, with the dynamics (evolution) given by the shift operator.

Recursive sequences and physics

Recursive sequences, human language and formal grammars

[To Do: Computational topics, finite state automaton, context free grammars. ]

L-systems are a small class of a formal grammar (a set of rules and symbols), in particular a Type-3 grammar without a terminating symbol, which Chompsky (1956, and others) characterized with respect to more complex grammars.

A Type-3 grammar generates the regular languages. Such a grammar restricts its rules to a single nonterminal on the left-hand side and a right-hand side consisting of a single terminal, possibly followed (or preceded, but not both in the same grammar) by a single nonterminal. The rule is also allowed here if S does not appear on the right side of any rule. These languages are exactly all languages that can be decided by a finite state automaton.

Cellular automata CA can be modeled by a restricted class of these L-systems. The state change of a single cell is represented by a set of rules that maps every possible 3x3 cell sub-array to a single cell state, where the system is understood to act on every overlapping 3x3 cell array. This results in a one-to-one mapping between generations. [Show example system.]

Finite automata and arithmetic , J.-P. Allouche

The notion of sequence generated by a finite automaton, (or more precisely a finite automaton with output function, i. e. a "uniform tag system") has been introduced and studied by Cobham in 1972. In 1980, Christol, Kamae, Mendes France and Rauzy, proved that a sequence with values in a finite field is automatic if and only if the related formal power series is algebraic over the rational functions with coeffcients in this field: this was the starting point of numerous results linking automata theory, combinatorics and number theory.

Several problems in graph and network theory can be described in terms of chaos theory and emergent self-similarity. For example:

Understanding the Long-Term Self-Similarity of Internet Traffic (2001)

Steve Uhlig, Olivier Bonaventure

Lecture Notes in Computer Science

From the Alan Kay Wikipedia entry:

"On 31 August 2006, Kay's proposal to the United States National Science Foundation, NSF, was granted, thus funding Viewpoints Research Institute for several years. The proposal title is: Steps Toward the Reinvention of Programming: A compact and Practical Model of Personal Computing as a Self-exploratorium [4]. A sense of what Kay is trying to do comes from this quote, from the abstract of a seminar on this given at Intel Research Labs, Berkeley: "The conglomeration of commercial and most open source software consumes in the neighborhood of several hundreds of millions of lines of code these days. We wonder: how small could be an understandable practical "Model T" design that covers this functionality? 1M lines of code? 200K LOC? 100K LOC? 20K LOC?" [5]

The system being developed makes extensive use of parsing via a bottom up rewrite grammar [6], [7], [8]."

[To Do: Dynamical systems]

Sandpile dynamics, an example of self-organised criticality in a simple CA type system. Dynamical systems are also used to model  movements in the Earth's crust, stock market fluctuations, the formation of traffic jams, and many other physical systems.

[To Do: Feedback systems]

[To Do: Information theory]

The Thue-Morse and Period doubling sequence are closely related to Hamming codes and Gray codes, due to the boundaries of anti-symmetries across indices that are powers of two. These codes are used for error detection and correction. The Gray code, also known as the reflected binary code, forms a Hamiltonian cycle on a hypercube, where each bit is seen as one dimension. Also see Gray code Thue-Morse binary fractal and algorithm.

One of the simplest 2-D recursive systems generates Hadamard matrices, which are also related to Walsh codes. The Hadamard code, based on these matrices, is also a system used for signal error detection and correction:

Note that the right column and bottom row are Thue-Morse sequences.

Also see:

Hadamard Matrices and Weaving

 

Redundancy

The patterns generated by all systems considered are near a maximum of redundancy.

[To Do: Fill out and illustrate.}

From Wikipedia's Redundancy (information theory) (accessed 2008-09-27)

Redundancy in information theory is the number of bits used to transmit a message minus the number of bits of actual information in the message. Informally, it is the amount of wasted "space" used to transmit certain data. Data compression is a way to reduce or eliminate unwanted redundancy, while checksums are a way of adding desired redundancy for purposes of error detection when communicating over a noisy channel of limited capacity.

Biological systems and bioinformatics (and other natural processes)

Why aren't these systems commonly used to describe natural processes? Are they rare, or difficult to recognize? Certainly many complex biological processes use processes that are related to recursive replacement systems, for example trees branch and the branches branch, but mechanistic descriptions are hard to come by.

Przemyslaw Prusinkiewicz advanced the idea that instances of the Fibonacci numbers/sequence in nature can be in part understood as the expression of certain algebraic constraints on free groups, specifically as certain Lindenmayer grammars (Prusinkiewicz, Przemyslaw; James Hanan (1989). Lindenmayer Systems, Fractals, and Plants (Lecture Notes in Biomathematics). Springer-Verlag. ISBN 0-387-97092-4).

Erwin Schrödinger's comparison of genes to aperiodic crystals, in his essay "What is Life?".

Also, from his Wikipedia page:

"In 1944, he wrote What is Life?, which contains a discussion of Negentropy and the concept of a complex molecule with the genetic code for living organisms. According to James D. Watson 's memoir, DNA, The Secret of Life, Schrödinger's book gave Watson the inspiration to research the gene, which led to the discovery of the DNA double helix structure. Similarly, Francis Crick , in his autobiographical book What Mad Pursuit, described how he was influenced by Schrödinger's speculations about how genetic information might be stored in molecules."

Epigenetics, the effect on gene expression that is not a direct consequence of the genetic code

Epigenetics (Pharyngula)

Epigenetics (Wikipedia)

(from Tackling A Hard-to-treat Childhood Cancer By Targeting Epigenetic Changes )

Giving chromosomes their structure and shape, strands of DNA, shown in gray, are coiled around histones, depicted as spheres. In MLL-rearranged ALL, a form of acute lymphoblastic leukemia affecting infants, an enzyme call DOT1L modifies the histones by methylating them in an abnormal way (as indicated in orange), leading to inappropriate activation of cancer-promoting genes. Drugs inhibiting this enzyme could prevent a variety of cancerous changes in cells. (Credit: Eric Smith, Dana-Farber Cancer Institute)

Evolving L-Systems to Capture Protein Structure Native Conformations, a book chapter of Genetic Programming by Gabi Escuela, Gabriela Ochoa and Natalio Krasnogor

"A protein is a linear chain of amino acids that folds into a unique functional structure, called its native state. In this state, proteins show repeated substructures like alpha helices and beta sheets. This suggests that native structures may be captured by the formalism known as Lindenmayer systems (L-systems). In this paper an evolutionary approach is used as the inference procedure for folded structures on simple lattice models. The algorithm searches the space of L-systems which are then executed to obtain the phenotype, thus our approach is close to Grammatical Evolution. The problem is to find a set of rewriting rules that represents a target native structure on the lattice model. The proposed approach has produced promising results for short sequences. Thus the foundations are set for a novel encoding based on L-systems for evolutionary approaches to both the Protein Structure Prediction and Inverse Folding Problems."

Language oriented bioinformatics, a list of references and a short summary.

Also see Information theory: a short introduction to its application in genetics, particularly redundancy.

 

[To Do: Engineering and design]

Assembling Materials with DNA as the Guide

Faisal A. Aldaye, Alison L. Palmer,  Hanadi F. Sleiman

Science 26 September 2008:
Vol. 321. no. 5897, pp. 1795 - 1799

In this approach, DNA tiles are typically made using strands with different sequences to prevent the formation of undesired structures. In practice, however, this requires synthesizing a large number of components and mixing these in exact stoichiometric ratios for successful assembly. By incorporating identical sequences (sequence symmetry) in DNA strands, Mao found that a stable four-way junction can be constructed from three strands instead of nine and that it assembles into the desired square grid array with an increased long-range order (2). Yan used sequence symmetry to tackle the problem of constructing finite arrays, rather than extended 2D assemblies, from a small number of DNA tiles (2). Thus, judicious incorporation of sequence symmetry in DNA strands merely used as architectural elements, such as struts and junctions, can simplify tile-based assembly. Winfree proposed the concept of "algorithmic DNA self-assembly" to increase complexity in DNA assembly. This was achieved by designing a set of DNA building blocks that represent "Wang tiles." Conceptually, Wang tiles contain a single color on each of their four sides and assemble so that the adjacent sides of each square are of the same color. This requirement necessarily means that each tile can fit in a specific manner within the assembly. Winfree adapted this methodology to construct rectangular-shaped DNA tiles, with four addressable sticky ends at each side as Wang tiles, and demonstrated the feasibility of assembling these according to a set of algorithmic rules initiated by a nucleating strand. Impressively complex fractal patterns can be generated using this approach, from a minimal set of DNA tiles (3).

 

Using fractal structures for antenna design.

L-System Tool for Generating Fractal Antenna Structures with Ability to Export into EM Simulators

Directory of Open Access Journals (DOAJ ), 2006

Pavel HAZDRA, Miloš MAZÁNEK
Department of Electromagnetic Field, Czech Technical University, Technická 2, 166 27 Praha, Czech Republic

An L-System (Lindenmayer system) is a scheme primarily developed in the area of the computer science for simulating the development of biological structures. It has also been found very useful for generating the geometry of various fractal antennas. A Matlab environment has been used for both implementing an in-plane L-systems algorithm and for creating appropriate files for widely used EM simulators like the IE3D and the CST Microwave Studio. Finally, the performance of the developed script is demonstrated on two fractal microstrip patch antennas.

Constructal theory

 
An interrogation of the transitions in algorithms called
L-systems, and the generation of a design language which these new forms produce

(Thesis Abstract of Geraldine Sarmiento
Interactive Telecommunications Program
New York University, Spring 2006.)

A beautiful exposition with nice quotes and general development.

"The fascination for the underlying structure of forms and patterns in the natural and artificial world has been with me since childhood. Self-similar and fractal-like forms inspired my imagination in the perception and confusion of scale. I would imagine worlds within worlds in all scales. Why are there similarities in the forms of nature in various scales? Why does repetition and variation of form create harmony in poetry? in wallpaper? in music? in architecture? Why do we seek patterns in everything? These are just some of the questions I’ve asked myself in my curiosity for the wonderful mysteries and the great variety of forms in all things. Through the focus on transitions in growth and form, I hope to discover the process by which complexity and beauty emerge through the use of L-systems."

[To Do: Tilings, as a separate topic under Simple Recursive Systems. ]

[To Do: Simple aperiodic square tilings. Motif replacement. Weaves. Fractal tilings and fractal prototiles.]

[To Do: 1 and 2-D periodic patterns -- the frieze and wallpaper groups.]

2008-08-21 Ted Bell writes:

"I've made a chart showing how four types of transformation can be applied to 4 basic shapes generating 16 different possibilities. This set of 16 is degenerate in a couple of ways that leads back to the 7 friezes.

The four basic shapes are assymmetrical vertical symmetry only horizontal symmetry only chiral symmetry about the center four transformations are:

glide (or simple translation)

glide reflect (like a barrel roll, twisting like a screw along the axis of movement)

rolling glide (like a forward roll)

spinning roll (moving along the axis but doing a 180 turn)

These are of course very similar to conways descriptions of the 7 frieze movements, but I believe they reveal something that is obscured in the set of 7, namely how the larger set is degenerate.

I believe that I can do the same thing with the wall paper groups, with the addition of a couple of basic shapes (triangle, hex), and multiplying the transformations in both directions. It's a larger table, but large portions of it are degenerate. However some of the degeneracies are interesting, in that they aren't simple duplications, but rather large complexes which have the same symmetry properties as the smaller basic shapes."

2008-08-24 Ted Bell writes:

This isn't the frieze chart, but it is a set of tilings generated by applying one of four types of transforms along on direction and another four along a second.

It's only the set generated by one assymmetrical unit. There are two versions, in the second version there is a one unit glide/offset.