:: wikimiki.org ::

Fractal

Fractal

A fractal is a geometric object which is rough or irregular on all scales of length, and so which appears to be 'broken up' in a radical way. Some of the best examples can be divided into parts, each of which is similar to the original object. Fractals are said to possess infinite detail, and some of them have a self-similar structure that occurs at different levels of magnification. In many cases, a fractal can be generated by a repeating pattern, in a typically recursive or iterative process. The term fractal was coined in 1975 by Benoît Mandelbrot, from the Latin fractus or "broken". Before Mandelbrot coined his term, the common name for such structures (the Koch snowflake, for example) was monster curve. Fractals of many kinds were originally studied as mathematical objects. Fractal geometry is the branch of mathematics which studies the properties and behaviour of fractals. It describes many situations which cannot be explained easily by classical geometry, and has often been applied in science, technology, and computer-generated art. The conceptual roots of fractals can be traced to attempts to measure the size of objects for which traditional definitions based on Euclidean geometry or calculus fail.

History

calculus. Each time new triangles are added (an iteration), the perimeter grows. It diverges to infinity with the number of iterations. The length of the Koch snowflake's boundary is infinite, while its area remains finite.]]

Contributions from classical analysis

Objects that are now called fractals were discovered and explored long before the word was coined. In 1872, Karl Weierstrass found an example of a function with the non-intuitive property that it is everywhere continuous but nowhere differentiable — the graph of this function would now be called a fractal. In 1904, Helge von Koch, dissatisfied with Weierstrass's very abstract and analytic definition, gave a more geometric definition of a similar function, which is now called the Koch snowflake. The idea of self-similar curves was taken further by Paul Pierre Lévy who, in his 1938 paper Plane or Space Curves and Surfaces Consisting of Parts Similar to the Whole, described a new fractal curve, the Lévy C curve. Georg Cantor gave examples of subsets of the real line with unusual properties — these Cantor sets are also now recognised as fractals. Iterated functions in the complex plane had been investigated in the late 19th and early 20th centuries by Henri Poincaré, Felix Klein, Pierre Fatou, and Gaston Julia. However, without the aid of modern computer graphics, they lacked the means to visualize the beauty of the objects that they had discovered.

Aspects of set description

In an attempt to understand objects such as Cantor sets, mathematicians such as Constantin Carathéodory and Felix Hausdorff generalised the intuitive concept of dimension to include non-integer values. This was part of the general movement in the first part of the twentieth century to create a descriptive set theory; that is, a continuation of the direction of Cantor's research that was able in some way to classify sets of points in Euclidean space. The definition of Hausdorff dimension is geometric in nature, although it is based technically on tools from mathematical analysis. This direction was taken up by Besicovitch, amongst others; it is different in character from the logical investigations that made up much of the descriptive set theory of the 1920s and 1930s. Both of these fields were pursued for some time afterwards, but mainly by specialists.

Mandelbrot's contributions

In the 1960s, Benoît Mandelbrot started investigating self-similarity in papers such as How Long Is the Coast of Britain? Statistical Self-Similarity and Fractional Dimension. This built on earlier work by Lewis Fry Richardson. Taking a highly visual approach, Mandelbrot recognised connections between these previously unrelated strands of mathematics. In 1975, Mandelbrot coined the word fractal to describe self-similar objects which had no clear dimension. He derived the word fractal from the Latin fractus, meaning broken or irregular, and not from the word fractional, as is commonly believed. However, fractional itself is derived ultimately from fractus as well. Once computer visualization was applied to fractal geometry, it presented a powerful visual argument for fractal geometry connecting far larger domains of mathematics and science than had previously been considered, particularly in the realm of non-linear dynamics, chaos theory (though a few use the term xaos instead to differentiate between ordered non-linear behaviour and the common meaning of the word), and complexity. One example is plotting Newton's method as a fractal, showing how the boundaries between different solutions are fractal, and that the solutions themselves are strange attractors. Fractal geometry was also used for data compression and for modelling complex organic and geological systems, for example the growth of trees or the development of river basins. Harrison [http://math.berkeley.edu/~harrison/research/publications/] extended Newtonian calculus to fractal domains, including the theorems of Gauss, Green, and Stokes.

Definitions

The most characteristic property of fractals is that they are generally irregular (not smooth) in shape, and thus are not objects definable by traditional geometry. That means that fractals tend to have significant detail, visible at any arbitrary scale; when there is self-similarity, this can occur because magnification simply shows similar pictures. Such sets are usually defined instead by recursion. For example, a normal Euclidean shape, such as a circle, looks flatter and flatter as it is magnified. At infinite magnification it would be impossible to tell the difference between the circle and a straight line. Fractals are not like this. The conventional idea of curvature, which represents the reciprocal of the radius of an approximating circle, cannot usefully apply because it scales away. Instead, with a fractal, increasing the magnification reveals more detail that was previously invisible. The defining characteristics of fractals, while intuitively appealing, are remarkably hard to condense into a mathematically precise definition. Mandelbrot defined fractal as "a set for which the Hausdorff-Besicovitch dimension strictly exceeds the topological dimension". For an entirely self-similar fractal, the Hausdorff dimension is equal to the Minkowski-Bouligand dimension. Problems with defining fractals include: :
- There is no precise meaning of "too irregular". :
- There is no single definition of "dimension". :
- There are many ways that an object can be self-similar. :
- Not every fractal is defined recursively.

Categories of fractals

The whole Mandelbrot set

Mandelbrot zoomed 6x

Mandelbrot Zoomed 100x

Mandelbrot Zoomed 2000x Even 2000 times magnification of the Mandelbrot set uncovers fine detail resembling the full set.

Fractals can be grouped into three broad categories. These categories are determined from how the fractal is defined or generated: :
- Iterated function systems — These have a fixed geometric replacement rule. Cantor set, Sierpinski carpet, Sierpinski gasket, Peano curve, Koch snowflake, Harter-Heighway dragon curve, T-Square, Menger sponge, are some examples of such fractals. :
- Escape-time fractals — Fractals defined by a recurrence relation at each point in a space (such as the complex plane). Examples of this type are the Mandelbrot set and the Lyapunov fractal. :
- Random fractals, generated by stochastic rather than deterministic processes, for example, fractal landscapes and Lévy flights. Fractals can also be classified according to their self-similarity. There are three types of self-similarity found in fractals: :
- Exact self-similarity — This is the strongest type of self-similarity; the fractal appears identical at different scales. Fractals defined by iterated function systems often display exact self-similarity. :
- Quasi-self-similarity — This is a loose form of self-similarity; the fractal appears approximately (but not exactly) identical at different scales. Quasi-self-similar fractals contain small copies of the entire fractal in distorted and degenerate forms. Fractals defined by recurrence relations are usually quasi-self-similar but not exactly self-similar. :
- Statistical self-similarity — This is the weakest type of self-similarity; the fractal has numerical or statistical measures which are preserved across scales. Most reasonable definitions of "fractal" trivially imply some form of statistical self-similarity. (Fractal dimension itself is a numerical measure which is preserved across scales.) Random fractals are examples of fractals which are statistically self-similar, but neither exactly nor quasi-self-similar. It should be noted that not all self-similar objects are fractals — e.g., the real line (a straight Euclidean line) is exactly self-similar, but the argument that Euclidean objects are fractals is a distinct minority position. Mandelbrot argued that a definition of "fractal" should include not only "true" fractals, but also traditional Euclidean objects, because irrational numbers on the number line represent complex, non-repeating properties. Because a fractal possesses infinite granularity, no natural object can be a fractal. However, natural objects can display fractal-like properties across a limited range of scales.

Examples

irrational number Some common examples of fractals include the Mandelbrot set, Lyapunov fractal, Cantor set, Sierpinski gasket and carpet, Menger sponge, dragon curve, Peano curve, limit sets of Kleinian groups, and the Koch curve. Fractals can be deterministic or stochastic (i.e. non-deterministic). Chaotic dynamical systems are often (if not always) associated with fractals. The Mandelbrot set contains whole discs, so has dimension 2. This is not surprising. What is truly surprising is that the boundary of the Mandelbrot set also has a Hausdorff dimension of 2. A relatively simple class of examples is the Cantor sets, in which short and then shorter (open) intervals are struck out of the unit interval [0, 1], leaving a set that might (or might not) actually be self-similar under enlargement, and might (or might not) have dimension d that has 0 < d < 1. A simple recipe, such as excluding the digit 7 from decimal expansions, is self-similar under 10-fold enlargement, and also has dimension log 9/log 10 (this value is the same, no matter what logarithmic base is chosen), showing the connection of the two concepts.

Fractals in nature

Approximate fractals are easily found in nature. These objects display complex structure over an extended, but finite, scale range. These naturally occurring fractals (like clouds, [http://www.its.caltech.edu/~atomic/snowcrystals/ snowflakes], mountains, river networks, and systems of blood vessels) have both lower and upper cut-offs, but they are separated by several orders of magnitude. Despite being ubiquitous, fractals were not much studied until well into the twentieth century, and general definitions came later. Trees and ferns are fractal in nature and can be modeled on a computer using a recursive algorithm. This recursive nature is clear in these examples — a branch from a tree or a frond from a fern is a miniature replica of the whole: not identical, but similar in nature. Image:Glue1_800x600.jpg|Pulling two glue-covered acrylic sheets apart forms a natural fractal. Image:Square1.jpg|High voltage breakdown within a 4″ block of acrylic creates a fractal Lichtenberg figure. Image:Microwaved-DVD.jpg|Fractal branching occurs on a microwave-irradiated DVD Image:Fractal Broccoli.jpg|Romanesco broccoli showing very fine natural fractals

Applications

Random fractals have the greatest practical use because they can be used to describe many highly irregular real-world objects. Examples include clouds, mountains, turbulence, coastlines, and trees. Fractal techniques have also been employed in fractal image compression, as well as a variety of scientific disciplines. There are various applications [http://library.thinkquest.org/26242/full/ap/ap.html] of fractals in the fields of:
- Classification of histopathology slides in medicine
- Generation of new music
- Generation of various art forms
- Signal and image compression
- Seismology
- Cosmology
- Computer and video game design, especially computer graphics for organic environments

Fractal generation

Fractals are usually rendered with computers. Various software exists for rendering fractals, and even generating new ones.
- Fractint (multiplatform)
- Sterling Fractal — Advanced fractal-generating program for Microsoft Windows operating systems by Stephen Ferguson
- XaoS — A fast interactive real-time fractal zoomer and morpher ([http://xaos.sourceforge.net/ homepage]).

External links

- [http://hypertextbook.com/chaos/ The Chaos Hypertextbook]. An introductory primer on chaos and fractals.
- [http://www.fractalus.com/info/layman.htm Fractals, in Layman's Terms]
- [http://www.cut-the-knot.org/Curriculum/index.shtml#f Fractals, fractal dimension, chaos, plane filling curves] at cut-the-knot
- [http://math.rice.edu/~lanius/fractals/self.html Fractal properties]
- [http://www.faqs.org/faqs/fractal-faq/ Information on fractals from FAQS.org]
- [http://www.jracademy.com/~jtucek/math/dimen.html Fractal dimensions]
- [http://math.berkeley.edu/~harrison/research/publications/ Fractal calculus]
- [http://www.math.vt.edu/people/hoggard/FracGeomReport/node1.html Fractal Dimension]
- [http://astronomy.swin.edu.au/~pbourke/fractals/grandcanyon/ Natural fractals in Grand Canyon]
- [http://www.geom.uiuc.edu/~math5337/ds/ One Dimensional Dynamical Systems]. From UIUC a brief introduction ; Multiplatform generator programs
- [http://xaos.sourceforge.net/ Xaos] — Realtime generator — Windows, Mac, Linux, etc
- [http://flam3.com/ FLAM3] — Advanced iterated function system designer and renderer for all platforms.
- [http://fract.ygingras.net Fract] — A Web-based fractal zoomer ; Linux generator programs
- [http://gnofract4d.sourceforge.net/ Gnofract4d] — Interactive editor which can use many fractint formulas
- [http://freshmeat.net/articles/view/827/ Review of fractal software packages which run under X11 on Linux] ; Windows generator programs
- [http://www.fractovia.org/fractal_generators/index.shtml Fractovia's listing of fractal generators] is a fairly complete listing of free fractal generators.
- [http://www.wackerart.de/fractal.html Online Fractal Generator] Java-Plugin required.
- [http://www.ultrafractal.com/ Ultra Fractal] — popular software for Microsoft Windows
- [http://www.chaospro.de ChaosPro] — for Microsoft Windows
- [http://www.aswsoftware.com/products/msplotter/msplotter.shtml MSPlotter] a great free Windows-based fractal generator, using fractals to create bitmap images and AVI video clips.
- [http://www.eclectasy.com/Fractal-Explorer/ Fractal Explorer] — free Windows-based generator ; Mac generator programs
- [http://www.daugerresearch.com/fractaldemos/altivecfractalcarbon.html Altivec Fractal Carbon] Mac-based benchmarking utility, using fractals to determine performance. ; MorphOS generator programs
- [http://www.elena-fractals.it/ Zone Explorer] with support for custom formulas ; Fractal Art Galleries
- [http://blog.yukonho.com/article.php?id=71 Gallery of beautiful, nature-like fractals]
- [http://www.fractovia.org/ Fractovia] — authoritative source of fractal generators, as well as a listing of tutorials regarding fractals in general, and specific programs.
- [http://www.phidelity.com/ph2/fractals/ Fractal Artwork, Spot files for Fractal Explorer]
- [http://www.fractal-landscapes.com Fractal landscapes]
- [http://fred.mitchellware.com/fractals Mitchell-Green gravity set]
- [http://www.faemalia.net/Fractals Several fractal art galleries with parameter files and programs for re-creating the images]
- [http://www.ericbigas.com/fractals Fractal Zoom movies]
- [http://webfractales.free.fr/en/ Galleries and softwares] Category:Digital Revolution Category:Digital art ko:프랙탈 ja:フラクタル th:แฟร็กทัล

Geometry

Geometry (Greek γεωμετρία; geo = earth, metria = measure) arose as the field of knowledge dealing with spatial relationships. It was one of the two fields of pre-modern mathematics, the other being the study of numbers. In modern times, geometric concepts have been generalized to a high level of abstraction and complexity, and have been subjected to the methods of calculus and abstract algebra, so that many modern branches of the field are barely recognizable as the descendants of early geometry. (See areas of mathematics and algebraic geometry.)

The earliest geometry

The earliest recorded beginnings of geometry may be traced to Ancient Egypt (see geometry in Egypt) and Ancient Babylon (see Babylonian mathematics) around 3000 B.C. Early geometry was a collection of empirically discovered principles concerning lengths, angles, areas, and volumes, which were developed to meet some practical need in surveying, construction, astronomy, and various crafts. Among these were some surprisingly sophisticated principles, and a modern mathematician might be hard put to derive some of them without the use of calculus. For example, both the Egyptians and the Babylonians were aware of versions of the Pythagorean theorem about 1500 years before Pythagoras; the Egyptians had a correct formula for the volume of a frustum of a square pyramid; the Babylonians had a trigonometry table. Chinese culture at this same time period was equally advanced, so it is likely that they had an equally advanced mathematics, but no artifacts have survived from which we could learn about it. This may be partly due to their early use of paper, rather than clay tablets or stone, to record their achievements.

The Greek period (c. 600 B.C. – 600 A.D.)

The Greek Period must be considered in detail, since geometry, for most of its history, was what the Greeks made it. For the Ancient Greeks, geometry was the crown jewel of their sciences, reaching a completeness and perfection of methodology that no other branch of their knowledge had attained. They expanded the range of geometry to many new kinds of figures, curves, surfaces, and solids; they changed its methodology from trial-and-error to logical deduction; they recognized that geometry studies “eternal forms”, or abstractions, of which physical objects are only approximations; and they developed the idea of an “axiomatic theory”, which, for more than 2000 years, was regarded to be the ideal paradigm for all scientific theories.

Thales and Pythagoras

Thales (635-543 B.C.) of Ionia (now southwestern Turkey), was the first to whom deduction in mathematics is attributed. There are five geometric propositions for which he wrote deductive proofs, though his proofs have not survived. Pythagoras (582-496 B.C.) of Ionia, and later, Italy, then colonized by Greeks, may have been a student of Thales, and probably traveled to Babylon and Egypt. The theorem that bears his name was not his discovery, but he was the first to give a deductive proof of it. He gathered a group of students around him to study mathematics, music, and philosophy, and together they discovered most of what high school students learn today in their geometry courses. In addition, they made the profound discovery of incommensurable lengths and irrational numbers.

Plato

Plato (427-347 B.C.), the philosopher most esteemed by the Greeks, had inscribed above the entrance to his famous school, “Let none enter here who are ignorant of geometry.” Though he was not a mathematician himself, his views on mathematics had great influence. Mathematicians thus accepted his belief that geometry should use no tools but a compass and straight edge – never measuring instruments such as a marked ruler or a protractor, because these were a workman’s tools, not worthy of a scholar. This dictum led to a deep study of the possible ruler and compass constructions, and three classic ruler-and-compass problems: how to use these tools to trisect an angle, to construct a cube twice the volume of a given cube, and to construct a square equal in area to a given circle. The proofs of the impossibility of these constructions, finally achieved in the 19th century, led to important principles regarding the deep structure of the real number system. Aristotle (384-322 B.C.), Plato’s greatest pupil, wrote a treatise on methods of reasoning used in deductive proofs (see Logic) which was not substantially improved upon until the 19th century.

Euclid

Euclid (365?-275? B.C.), probably a student of one of Plato’s students, wrote a treatise in 13 books (chapters), titled The Elements of Geometry, in which he presented geometry in the ideal axiomatic form. The treatise is not a compendium of all that the Greeks knew at the time about geometry; Euclid himself wrote eight more advanced books on geometry. We know from other references that Euclid’s was not the first elementary geometry textbook, but it was so much superior that the others fell into disuse and were lost. He was brought to the university at Alexandria by Ptolemy I, King of Egypt. The Elements began with definitions of terms, fundamental geometric principles (called axioms or postulates), and general quantitative principles (called common notions) from which all the rest of geometry could be logically deduced. Following are his five axioms, somewhat paraphrased to make the English easier to read. # Any two points can be joined by a straight line. # Any finite straight line can be extended in a straight line. # A circle can be drawn with any center and any radius. # All right angles are equal to each other. # If two straight lines in a plane are crossed by another straight line (called the transversal), and the interior angles between the two lines and the transversal lying on one side of the transversal add up to less than two right angles, then on that side of the transversal, the two lines extended will intersect (also called the parallel postulate). It was soon observed, and no doubt Euclid himself knew, that his fifth axiom could be replaced by the shorter statement “Given a line and a point not on the line, there is only one line through the given point and in the same plane with the given line that does not intersect the given line.” This is called Playfair’s Axiom, after the British teacher who proposed to make the replacement in all the school textbooks. The axioms, according to Plato, should be simple and self-evident principles, so clearly true that they need no proof. Euclid’s first four axioms meet this criterion, but the fifth, even if replaced by Playfair’s Axiom, is not simple, and most would say not self-evident like the first four. The fifth resembled more the theorems that Euclid proved from the axioms. Furthermore, Euclid developed a substantial part of his theory of triangles without using the Fifth Axiom. The speculation arose, probably during Euclid’s lifetime, that the Fifth Axiom can and should be proved as a theorem from the first four, and thus is unnecessary as an axiom. Thus began many centuries of attempts to prove the Fifth Axiom, and the question was not settled until the 19th century.

Archimedes

Archimedes (287-212 B.C.), of Syracuse, Sicily, when it was a Greek city-state, was the greatest of the Greek mathematicians, and often named as one of the three greatest of all time (along with Isaac Newton and Carl Friedrich Gauss). Had he not been a mathematician, he would still be remembered as a great physicist, engineer, and inventor. In his mathematics, he developed methods very similar to the coordinate systems of analytic geometry, and the limiting process of integral calculus. The only element lacking for the creation of these fields was an efficient algebraic notation in which to express his concepts.

After Archimedes

After Archimedes, Greek mathematics began to decline. There were a few minor stars yet to come, but the golden age of geometry was over. Proclus (410-485), author of Commentary on the First Book of Euclid, was one of the last important players in Greek geometry. He was a competent geometer, but more importantly, he was a superb commentator on the works that preceded him. Much of that work did not survive to modern times, and is known to us only through his commentary. The Roman Republic and Empire that succeeded and absorbed the Greek city-states produced excellent engineers, but no mathematicians of note.

The Middle Ages, Renaissance, and Reformation

The great library of Alexandria was burned. There is a growing consensus among historians that the Library of Alexandria likely suffered from several destructive events, but that the destruction of Alexandria's pagan temples in the late 4th century was probably the most severe and final one. The evidence for that destruction is the most definitive and secure. Caesar's invasion may well have led to the loss of some 40,000-70,000 scrolls in a warehouse adjacent to the port (as Luciano Canfora argues, they were likely copies produced by the Library intended for export), but it is unlikely to have affected the Library or Museum, given that there is ample evidence that both existed later. Civil wars, decreasing investments in maintenance and acquisition of new scrolls and generally declining interest in non-religious pursuits likely contributed to a reduction in the body of material available in the Library, especially in the fourth century. The Serapeum was certainly destroyed by Theophilus in 391, and the Museum and Library may have fallen victim to the same campaign. The Islamic ascendency in the Middle East, north Africa, and Spain began about 640 A.D. Original Arab mathematics during this period was primarily algebraic rather than geometric, though there were important commentaries on geometry. Omar Khayyám, for example, was a geometer as well as a poet. Scholarship in Europe declined until even the great works of antiquity were lost to them, and survived only in the Islamic centers of learning. When Europe started to emerge from the intellectual darkness of the Middle Ages, the writers of Ancient Greece and Rome were rediscovered in Islamic libraries and translated from Arabic into Latin. Euclid’s Elements of Geometry was recovered, and the rigorous deductive methods of geometry were relearned. Development of geometry in the style of Euclid resumed, resulting in an abundance of new theorems and concepts, many of them very profound and elegant.

The 17th and early 18th centuries

In the early 17th century, there were two important developments in geometry. The first and most important was the creation of analytic geometry, or geometry with coordinates and equations, by Rene Descartes (1596-1650) and Pierre de Fermat (1601-1665). This was a necessary precursor to the development of calculus and a precise quantitative science of physics. The second geometric development of this period was the systematic study of projective geometry by Girard Desargues (1591-1661). Projective geometry is the study of geometry without measurement, just the study of how points align with each other. There had been some early work in this area by Greek geometers, notably Pappus (c. 340). The greatest flowering of the field occurred with Jean-Victor Poncelet (1788-1867). In the late 17th century, calculus was developed independently and almost simultaneously by Isaac Newton (1642-1727) and Gottfried Wilhelm von Leibniz (1646-1716). This was the beginning of a new field of mathematics now called analysis. Though not itself a branch of geometry, it is applicable to geometry, and it solved two families of problems that had long been almost intractable: finding tangent lines to odd curves, and finding areas enclosed by those curves. The methods of calculus reduced these problems mostly to straightforward matters of computation.

The late 18th and 19th centuries

Non-Euclidean geometry

The old problem of proving Euclid’s Fifth Postulate, the "Parallel Postulate", from his first four postulates had never been forgotten. Beginning not long after Euclid, many attempted demonstrations were given, but all were later found to be faulty, through allowing into the reasoning some principle which itself had not been proved from the first four postulates. By 1700 a great deal had been discovered about what can be proved from the first four, and what the pitfalls were in attempting to prove the fifth. Saccheri, Lambert, and Legendre each did excellent work on the problem in the 18th century, but still fell short of success. In the early 19th century, Gauss, Johann Bolyai, and Lobatchewsky, each independently, took a different approach. Beginning to suspect that it was impossible to prove the Parallel Postulate, they set out to develop a self-consistent geometry in which that postulate was false. In this they were successful, thus creating the first non-Euclidean geometry. By 1854, Bernhard Riemann, a student of Gauss, had applied methods of calculus in a ground-breaking study of the intrinsic (self-contained) geometry of all smooth surfaces, and thereby found a different non-Euclidean geometry. This work of Riemann later became fundamental for Einstein's theory of relativity. It remained to prove mathematically that the non-Euclidean geometry was just as self-consistent as Euclidean geometry, and this was first accomplished by Beltrami in 1868. With this, non-Euclidean geometry was established on an equal mathematical footing with Euclidean geometry. While it was now known that different geometric theories were mathematically possible, the question remained, "Which one of these theories is correct for our physical space?" The mathematical work revealed that this question must be answered by physical experimentation, not mathematical reasoning, and uncovered the reason why the experimentation must involve immense (interstellar, not earth-bound) distances. With the development of relativity theory in physics, this question became vastly more complicated.

Introduction of mathematical rigor

All the work related to the Parallel Postulate revealed that it was quite difficult for a geometer to separate his logical reasoning from his intuitive understanding of physical space, and, moreover, revealed the critical importance of doing so. Careful examination had uncovered some logical inadequacies in Euclid's reasoning, and some unstated geometric principles to which Euclid sometimes appealed. This critique paralleled the crisis occurring in calculus and analysis regarding the meaning of infinite processes such as convergence and continuity. In geometry, there was a clear need for a new set of axioms, which would be complete, and which in no way relied on pictures we draw or on our intuition of space. Such axioms were given by David Hilbert in 1894 in his dissertation Grundlagen der Geometrie (Foundations of Geometry). Some other complete sets of axioms had been given a few years earlier, but did not match Hilbert's in economy, elegance, and similarity to Euclid's axioms.

Analysis situs, or topology

In the mid-18th century, it became apparent that certain progressions of mathematical reasoning recurred when similar ideas were studied on the number line, in two dimensions, and in three dimensions. Thus the general concept of a metric space was created so that the reasoning could be done in more generality, and then applied to special cases. This method of studying calculus- and analysis-related concepts came to be known as analysis situs, and later as topology. The important topics in this field were properties of more general figures, such as connectedness and boundaries, rather than properties like straightness, and precise equality of length and angle measurements, which had been the focus of Euclidean and non-Euclidean geometry. Topology soon became a separate field of major importance, rather than a sub-field of geometry or analysis.

The 20th century

External links

- [http://www.cut-the-knot.org/WhatIs/WhatIsGeometry.shtml What Is Geometry?] at cut-the-knot
- [http://www.elvenkids.com/tools/geometria/Geometria.php Geometria] An online tool to compute lines, surfaces and volumes of the main plane and solid figures, through direct and indirect formulas.
- [http://www.geogebra.at/ Geogebra] A free dynamic geometry tool, useful for exploring geometry.
- [http://agutie.homestead.com Geometry Step by Step from the Land of the Incas] by Antonio Gutierrez.
- [http://www.cut-the-knot.org/geometry.shtml Geometry] at cut-the-knot
- [http://www.islamicarchitecture.org/art/islamic-geometry-and-floral-patterns.html Islamic Geometry]
- Stanford Encyclopedia of Philosophy:
- [http://plato.stanford.edu/entries/geometry-finitism/ Finitism in Geometry]
- [http://plato.stanford.edu/entries/geometry-19th/ Geometry in the 19th Century]
- [http://www.egwald.com/geometry/index.php Online Interactive Geometric Objects] by Elmer G. Wiens Category:Geometry ko:기하학 ja:幾何学 simple:Geometry zh-min-nan:Kí-hô-ha̍k

Recursion

In mathematics and computer science, recursion specifies (or constructs) a class of objects (or an object from a certain class) by defining a few very simple base cases (often just one), and then defining rules to break down complex cases into simpler cases. Recursion is sometimes mistaken for circular reasoning. However, the crucial difference is that its base cases are defined in terms that are not part of the system. Since all the cases break down into base cases, and the base cases are in different terms, the analysis stops. That is, it is not circular. circular reasoning For example, the following is a recursive definition of person's ancestors:
- One's parents are one's ancestors (base case);
- The parents of any ancestor are also ancestors of the person under consideration (recursion step). For instance, your ancestors are:
- your parents, and
- your parents' parents (= grandparents), and
- your grandparents' parents, and
- everyone else you get by successively adding ancestors It is convenient to think that a recursive definition defines objects in terms of "previously defined" objects of the class to define. Definitions such as these are often found in mathematics. For example, the formal definition of natural numbers is: 0 is a natural number, and each natural number has a successor, which is also a natural number. To visualize recursion, it can be helpful to consider recursively-defined geometric figures, such as the Koch curve, the Sierpinski triangle, or the Cantor set. Also, examples of recursion abound in natural language, often appearing as, or transforming into jokes. These jokes can help one develop an intuition for recursion. For example, responding to the question, "What do you mean what do I mean?" with "What do you mean 'What do you mean what do I mean?'?", can clearly go on forever, although it is unclear how many iterations can be meaningful... Although artist- and poet-types often make jokes of this kind, studying recursion in mathematics and programming languages can help to understand the meaning and philosophy of language in this sense, and a careful observation of language in this sense can help to understand recursion.

Recursion in mathematics

Functional Recursion

Mathematical recursion involves a function calling on itself over and over until reaching an end state. Each iteration increases the depth of the call. Once the end state is achieved, the function then backs all the way out, step by step. The key points of this kind of recursion are two fold: #You have to have a function that calls itself with a smaller subset of the values with which it began. #The function must be aware that an end state exists which terminates the recursive process.

Recursive Proofs

The standard way to define new systems of mathematics or logic is to define objects (such as "true" and "false", or "all natural numbers"), then define operations on these. These are the base cases. After this, all valid computations in the system are defined with rules for assembling these. In this way, if the base cases and rules are all proven to be calculable, then any formula in the mathematical system will also be calculable. This sounds unexciting, but this type of proof is the normal way to prove that a calculation is impossible. This can often save a lot of time. For example, this type of proof was used to prove that the area of a circle is not a simple ratio of its diameter, and that no angle can be trisected with a compass and ruler -- both puzzles that fascinated the ancients.

Recursion in computing

Recursion in computer programming defines a function in terms of itself. One example application of recursion is in parsers for programming languages. The great advantage of recursion is that an infinite set of possible sentences, designs or other data can be defined, parsed or produced by a finite computer program. One basic form of recursive computer program is to define one or a few base cases, and then define rules to break down other cases into the base case. This is analytic, and is the most common design for parsers for computer languages. Another, similar form is generative recursion. This is synthetic. In this scheme, the computer uses rules to assemble cases, and starts by selecting a base case. This scheme is often used when a computer must design something automatically, such as code, a machine part or some other data. The commonly used example (using the Euphoria programming language, in this case) is the function used to calculate the factorial of an integer: function Factorial ( integer X ) if X < 0 then return "Invalid argument" end if if X = 0 then return 1 end if return Factorial(X-1)
- X end function Although the recursive factorial function is calculating the same value as the iterative function below, depending on language implementation, recursive function may consume additional memory for each call. I.e. factorial(20) may use ten times more memory than factorial(10). The Scheme language is especially efficient at recursion, but naive recursive implementations in earlier versions of C were very notoriously wasteful. Nowadays, only the most performance-hungry software, such as video games, missile guidance systems and graphics card drivers, should worry about whether recursion will be slower than iterative for or while loops. Recursive functions are often regarded as more elegant than alternative implementations and they are usually shorter and simpler. For example, above function coded in the same language without recursion would be as follows: function Factorial ( integer X ) integer temp_result if X < 0 then return "Invalid argument" end if temp_result = 1 for i = 1 to X do temp_result
- = i end for return temp_result end function In this particular example the iterative implementation is slightly faster in practice than the recursive one. (Note that an even faster implementation for the Factorial function is that of using a lookup table.) There are other types of problems that seem to have an inherently recursive solution, i.e. they need to keep track of prior state. One example is tree traversal, which is possible to implement iteratively with the help of a stack, but the need for the stack arguably defeats the purpose of the iterative solution. One other possible reason for choosing an iterative algorithm is that in today's programming languages thread stacks are often much smaller than memory available in the heap.

Recursion in language

Linguist Noam Chomsky produced evidence that unlimited extension of a language such as English is possible only by the recursive device of embedding sentences in sentences. Thus, a talky little girl may say, "Dorothy, who met the wicked Witch of the West in Munchkin Land where her wicked Witch sister was killed, liquidated her with a pail of water." Clearly, two simple sentences — "Dorothy met the Wicked Witch of the West in Munchkin Land" and "Her sister was killed in Munchkin Land" — can be embedded in a third sentence, "Dorothy liquidated her with a pail of water," to obtain a very talky sentence. Niels K. Jerne, the 1984 Nobel Prize laureate in Medicine and Physiology, used Chomsky's transformational-generative grammar model to explain the human immune system, equating "components of a generative grammar ... with various features of protein structures." The title of Jerne's Stockholm Nobel lecture was The Generative Grammar of the Immune System. Here is another, perhaps simpler way to understand recursive processes: #Are we done yet? If so, return the results. Without such a termination condition a recursion would go on forever. #If not, simplify the problem, solve those simpler problem(s), and assemble the results into a solution for the original problem. Then return that solution. A more humorous illustration goes: "In order to understand recursion, one must first understand recursion." Or perhaps more accurate is the following due to Andrew Plotkin: "If you already know what recursion is, just remember the answer. Otherwise, find someone who is standing closer to Douglas Hofstadter than you are; then ask him or her what recursion is." Examples of mathematical objects often defined recursively are functions, sets, and especially fractals.

Recurrence relations or algorithms

Recurrence relations are equations to define one or more sequences recursively. Some specific kinds of recurrence relation can be "solved" to obtain a non-recursive definition.

Recursively defined sets

Example: the natural numbers

The canonical example of a recursively defined set is given by the natural numbers: :0 is in N :if n is in N, then n + 1 is in N :The set of natural numbers is the smallest set satisfying the previous two properties. Here's an alternative recursive definition of N: :0, 1 are in N; :if n and n + 1 are in N, then n + 2 is in N; :N is the smallest set satisfying the previous two properties.

Example: The set of true reachable propositions

Another interesting example is the set of all true "reachable" propositions in an axiomatic system.
- if a proposition is an axiom, it is a true reachable proposition.
- if a proposition can be obtained from true reachable propositions by means of inference rules, it is a true reachable proposition.
- The set of true reachable propositions is the smallest set of reachable propositions satisfying these conditions. This set is called 'true reachable propositions' because: in non-constructive approaches to the foundations of mathematics, the set of true propositions is larger than the set recursively constructed from the axioms and rules of inference. See also Gödel's incompleteness theorems. (Note that determining whether a certain object is in a recursively defined set is not an algorithmic task.)

Recursively defined functions

Functions whose domains can be recursively defined can be given recursive definitions patterned after the recursive definition of their domain. The canonical example of a recursively defined function is the following definition of the factorial function

f(n)

f (0) = 1

f (n) = n  -  f (n-1)

for any natural number

n > 0

Given this definition, also called a recurrence relation, we work out

f(3)

as follows:

f (3) = 3  -  f (3 - 1)

= 3  -  f (2)

= 3  -  2  -  f (2 - 1)

= 3  -  2  -  f (1)

= 3  -  2  -  1  -  f (1 - 1)

= 3  -  2  -  1  -  f (0)

= 3  -  2  -  1  -  1

= 6

Recursive algorithms

A common method of simplification is to divide a problem into subproblems of the same type. As a computer programming technique, this is called divide and conquer and is key to the design of many important algorithms, as well as being a fundamental part of dynamic programming. Virtually all programming languages in use today allow the direct specification of recursive functions and procedures. When such a function is called, the computer (for most languages on most stack-based architectures) or the language implementation keeps track of the various instances of the function (on many architectures, by using a stack, although other methods may be used). Conversely, every recursive function can be transformed into an iterative function by using a stack. Any function that can be evaluated by a computer can be expressed in terms of recursive functions, without use of iteration, and conversely. To make a very literal example out of this: If an unknown word is seen in a book, the reader can make a note of the current page number and put the note on a stack (which is empty so far). The reader can then look the new word up and, while reading on the subject, may find yet another unknown word. The page number of this word is also written down and put on top of the stack. At some point an article is read that does not require any explanation. The reader then returns to the previous page number and continues reading from there. This is repeated, sequentially removing the topmost note from the stack. Finally, the reader returns to the original book. This is a recursive approach. Some languages designed for logic programming and functional programming provide recursion as the only means of repetition directly available to the programmer. Such languages generally make tail recursion as efficient as iteration, letting programmers express other repetition structures (such as Scheme's map and for) in terms of recursion. Recursion is deeply embedded in the theory of computation, with the theoretical equivalence of recursive functions and Turing machines at the foundation of ideas about the universality of the modern computer. John McCarthy's 91 function is another example of a recursively defined function. The Quicksort and Mergesort algorithms are also commonly done using recursion, which allows them to run in an average of O(n log n) time. Many operations involving tree data structures also use recursion, as it is often quite difficult to iteratively traverse a tree of unknown length. In addition, some numerical methods for finding approximate solutions to mathematical equations use recursion. In Newton's method, for example, an approximate root of a function is provided as initial input to the method. The calculated result (output) is then used as input to the method, with the process repeated until a sufficiently accurate value is obtained.

The recursion theorem

In set theory, this is a theorem guaranteeing that recursively defined functions exist. Given a set

X

, an element

a

X

and a function

f: X \rightarrow X

, the theorem states that there is a unique function

F: N \rightarrow X

(where

N

denotes the set of natural numbers) such that :

F(0) = a

F(n + 1) = f(F(n))

for any natural number

n

Proof of uniqueness

Take two functions

f

and

g

of domain

N

and codomain

A

such that: :

f(0) = a

g(0) = a

f(n + 1) = F(f(n))

g(n + 1) = F(g(n))

where

a

is an element of

A

. We want to prove that

f = g

. Two functions are equal if they: :i. have equal domains/codomains; :ii. have the same graphic. :i. Done! :ii. Mathematical induction: for all

n

N

f(n) = g(n)

? (We shall call this condition, say,

Eq(n))

: ::1.

Eq(0)

iff

f(0) = g(0)

iff

a = a

. Done! ::2.Let

n

be an element of

N

. Assuming that

Eq(n)

holds, we want to show that

Eq(n + 1)

holds as well, which is easy because:

f(n + 1) = F(f(n)) = F(g(n)) = g(n + 1)

. Done! you should consider N union as a domain of F.

Proof of existence

[See Hungerford, "Algebra", first chapter on set theory] ---- Some common recurrence relations are:
- Factorial --

n! = n (n - 1)! = n (n - 1)\cdots 1

- Fibonacci numbers --

f(n) = f(n - 1) + f(n - 2)

- Catalan numbers --

C_0=1

C_ = (4n+2)C_n/(n+2)

- Computing compound interest
- The tower of Hanoi
- Ackermann function
- Population growth rate

Recursion in plain English

Recursion is the process a procedure goes through when one of the steps of the procedure involves rerunning the entire same procedure. A procedure that goes through recursion is said to be recursive. Something is also said to be recursive when it is the result of a recursive procedure. To understand recursion, one must recognize the distinction between a procedure and the running of a procedure. A procedure is a set of steps that are to be taken based on a set of rules. The running of a procedure involves actually following the rules and performing the steps. An analogy might be that a procedure is like a menu in that it is the possible steps, while running a procedure is actually choosing the courses for the meal from the menu. A procedure is recursive if one of the steps that makes up the procedure calls for a new running of the procedure. Therefore a recursive four course meal would be a meal in which one of the choices of appetizer, salad, entrée, or dessert was an entire meal unto itself. So a recursive meal might be potato skins, baby greens salad, chicken parmesan, and for dessert, a four course meal, consisting of crab cakes, Caesar salad, for an entrée, a four course meal, and chocolate cake for dessert, so on until each of the meals within the meals is completed. A recursive procedure must complete every one of its steps. Even if a new running is called in one of its steps, each running must run through the remaining steps. What this means is that even if the salad is an entire four course meal unto itself, you still have to eat your entrée and dessert.

Recursive humour

A common geeky joke (for example [http://catb.org/~esr/jargon/html/R/recursion.html]) is the following "definition" of recursion. :Recursion ::See "Recursion". This is a parody on references in dictionaries, which in some careless cases may lead to circular definitions; in fact the above is the shortest possible one. Every joke has an element of wisdom, and also an element of misunderstanding. This one is also the second-shortest possible example of an erroneous recursive definition of an object, the error being the absence of the termination condition (or lack of the initial state, if to look at it from an opposite point of view). Newcomers to recursion are often bewildered by its apparent circularity, until they learn to appreciate that a termination condition is key. Other examples are recursive acronyms, such as GNU, PHP or TTP (Dilbert; "The TTP Project").

References

-
-
-
-
-
- - offers a treatment of corecursion.
-
-

External links

- [http://www.mantasoft.co.uk/_stuff/recursive.gif Recursive Animation], Animated GIF
- [http://www.mantasoft.co.uk/anim/show.php?url=Recursive.swf Recursive Animation], Requires Flash
- [http://www.mantasoft.co.uk/anim/show.php?url=Recursive_2.swf Recursive Animation], Requires Flash
- "[http://www.freenetpages.co.uk/hp/alan.gauld/tutrecur.htm Recursion]"- tutorial by Alan Gauld
- [http://citeseer.ist.psu.edu/cis?q=recursion Citations from CiteSeer]
- [http://escherdroste.math.leidenuniv.nl/index.php?menu=symmetry&sub=droste Droste effect], recursive image Category:Algorithms Category:Computer science Category:Mathematical logic Category:Theory of computation ja:再帰呼び出し

1975

1975 (MCMLXXV) was a common year starting on Wednesday (the link is to a full 1975 calendar).

Events

January

- January 1 - Watergate scandal: John N. Mitchell, H. R. Haldeman, John D. Ehrlichman are found guilty of the Watergate cover-up
- January 2 - The Federal Rules of Evidence are approved by Congress
- January 5 - The Tasman Bridge in Tasmania, Australia, is struck by the bulk ore carrier Lake Illawarra, killing twelve people.
- January 7 - OPEC agrees to raise crude oil prices by 10%.
- January 8 - Ella Grasso becomes Governor of Connecticut, becoming the first woman to serve as a Governor in the United States who did not succeed her husband
- January 10 - Japanese soldier Teruo Nakamura surrenders on the Indonesian Island of Morota
- January 14 - 17 year old heiress Lesley Whittle is kidnapped from her home in Shropshire, England by the Black Panther.
- January 20 - Michael Ovitz founds Creative Artists Agency
- January 29 - Weather Underground bombs US State Department main office in Washington D.C.
- January - Altair 8800 is released, sparking the era of the microcomputer

February

- February 4 - The first successfully predicted earthquake occurred in Haicheng, Liaoning, China.
- February 9 - The Soyuz 17 Soviet spacecraft returns to Earth.
- February 11 - Margaret Thatcher defeats Edward Heath for the leadership of the UK Conservative Party in the United Kingdom.
- February 21 - Watergate scandal: Former United States Attorney General John N. Mitchell and former White House aides H. R. Haldeman and John Ehrlichman are sentenced to between 30 months and 8 years in prison
- February 23 - In response to the energy crisis, daylight saving time commences nearly two months early in the United States.
- February 26 - a fleeing IRA terrorist shoots dead off-duty London police officer Stephen Tibble, 22, as he gives chase
- February 27 - Movement 2 June kidnaps West German politician Peter Lorenz. He is released on March 4 after most of the kidnappers' demands are met
- February 28 - A major tube train crash at Moorgate station, London kills 43 people.
- February 28 - In Lomé, the capital of Togo, the European Economic Community and 46 African, Caribbean and Pacific countries sign a financial and economic treaty, known as the first Lomé Convention.

March

- March 1 - Color television transmissions begin in Australia
- March 4 - Charlie Chaplin is knighted by Queen Elizabeth II of the United Kingdom
- March 6 - Algiers Accord - Iran and Iraq announce a settlement over their border dispute.
- March 6 - A bomb explodes in the Paris offices of the Springer Press. The "6 March Group" (connected to the Red Army Faction) demands amnesty for the "Baader-Meinhof Group"
- March 7 - The body of teenage heiress Lesley Whittle, kidnapped seven weeks earlier by the Black Panther is discovered in Staffordshire, England
- March 8 - United Nations begin sponsoring the International Women's Day.
- March 9 - Construction of the Trans-Alaska Pipeline System begins
- March 10 - Vietnam War: North Vietnamese troops attack Ban Me Thout, South Vietnam, on their way to capturing Saigon.
- March 15 - In Brazil, the Estado da Guanabara (State of Guanabara) merges with the state of Rio de Janeiro, under the name of Rio de Janeiro. The state's capital moves from the city of Niterói to the city of Rio de Janeiro.
- March 25 - King Faisal of Saudi Arabia is shot and killed by a nephew with a history of mental illness - the killer is beheaded on June 18.
- March 28 - A fire in the maternity wing at Kucic Hospital in Rijeka, Yugoslavia, kills 25 babies

April-May

- April 3 - Bobby Fischer refuses to play in a chess match against Anatoly Karpov, giving Karpov the title.
- April 4 - Vietnam War: The first military Operation Babylift flight, C5A 80218, crashes 27 minutes after takeoff killing 138 on board; 176 survive the crash.
- April 13 - An attack by Phalangists on a Palestinian bus in Ain El Remmeneh, Lebanon sparks over 15 years of civil war.
- April 17 - Pol Pot proclaims the "Democratic Republic of Kampuchea" in Cambodia and becomes its Prime Minister (1975–1979).
- April 24 - Six Red Army Faction terrorists take over West German embassy in Stockholm, take 11 hostages and demand the release of the group's jailed members. Shortly after they are captured by Swedish police.
- April 25 - Vietnam War: As North Vietnamese forces close in on the South Vietnamese capital Saigon, the Australian Embassy is closed and evacuated, almost ten years to the day since the first Australian troop commitment to South Vietnam.
- April 30 - Vietnam War: The Vietnam War ends as Communist forces take Saigon and South Vietnam surrenders unconditionally.
- May 5 - The Busch Gardens Williamsburg theme park opens in Virginia.
- May 12 - Mayaguez incident: Khmer Rouge forces in Cambodia seize the American merchant ship SS Mayaguez in international waters.
- May 15 - Mayaguez incident: The American merchant ship Mayaguez, seized by Cambodian forces, is rescued by U.S. Navy and Marines. 38 Americans are killed.
- May 16 - India annexes Sikkim.
- May 16 - Junko Tabei becomes the first woman to reach the summit of Mount Everest.
- May 28 - 15 West African countries sign the Treaty of Lagos, creating the Economic Community of West African States.
- May 30 - 1972 Olympic runner Steve Prefontaine dies in a car accident.

June-July

- June 5 - The Suez Canal opens for the first time since the Six-Day War
- June 5 - The United Kingdom votes yes in a referendum on staying in the European Community
- June 9 - Order of Australia (OA) awarded for 1st time
- June 19 - Lord Lucan found guilty in absentia of the murder of the nanny Sandra Rivett
- June 25 - Mozambique gains independence from Portugal
- June 26 - Two FBI agents and one member of AIM die in a shootout in Pine Ridge Indian Reservation in South Dakota
- July 1 - Postmaster-General's Department is disaggregated into the Australian Telecommunications Commission (trading as Telecom Australia) and the Australian Postal Commission (trading as Australia Post).
- July 4 - Sydney newspaper publisher Juanita Nielsen disappears, and is presumed to have been murdered.
- July 5 - Cape Verde gains independence after 500 years of Portuguese rule
- July 6 - The Comoros declare their independence from France
- July 9 - The National Assembly of Senegal passes a law that will pave way for a (albeit highly restricted) multi-party system.
- July 12 - São Tomé and Príncipe declare independence from Portugal
- July 17 - Apollo-Soyuz Test Project: An American Apollo and a Soviet Soyuz spacecraft dock with each other in orbit marking the first such link-up between spacecraft from the two nations
- July 31 - In Detroit, Michigan, Teamsters Union president Jimmy Hoffa is reported missing.

August

- August 8 - The Banqiao Dam, in China's Henan Province, fails after a freak typhoon. Over 200,000 people perish.
- August 8 - Samuel Bronfman, son of the president of Seagrams, is kidnapped in Purchase, New York
- August 11 - British Leyland comes under British government control
- August 11 - Mário Lemos Pires, Governor of Portuguese Timor, abandons the capital Dili following UDT coup and outbreak of civil war between UDT and Fretilin.
- August 15 - Birmingham Six wrongfully sentenced to life imprisonment
- August 15 - Mujibur Rahman, president of Bangladesh, is killed during a coup
- August 20 - Viking program: NASA launches the Viking 1 planetary probe toward Mars
- August 24 - Officers responsible for the military coup in Greece in 1967 are sentenced to death in Athens. The sentences are later commuted to life imprisonment

September

- September 5 - In Sacramento, California, Lynette "Squeaky" Fromme, a follower of incarcerated cult leader Charles Manson, attempts to assassinate US President Gerald Ford, but is thwarted by a Secret Service agent.
- September 14 - Rembrandt's painting "The Night Watch" is slashed a dozen times at a gallery in Amsterdam.
- September 15 - The French department of Corse, comprising the entire island of Corsica, is divided into two departments: Haute-Corse and Corse-du-Sud.
- September 20 - End of term for Tuanku Al-Mutassimu Billahi Muhibbudin Sultan Abdul Halim Al-Muadzam Shah ibni Almarhum Sultan Badlishah as the 5th Yang di-Pertuan Agong of Malaysia.
- September 21 - Sultan Yahya Petra ibni Almarhum Sultan Ibrahim Petra, Sultan of Kelantan becomes the 6th Yang di-Pertuan Agong of Malaysia.
- September 22 - President Gerald Ford survives a second assassination attempt, this time by Sara Jane Moore
- September 30 - Hughes Helicopters (later McDonnell-Douglas, now Boeing IDS) AH-64 Apache made its first flight.

October

- October 9 - A bomb explosion outside Green Park tube station near Piccadilly in London kills 1 and injures 20.
- October 16 - Five Australian-based journalists are killed at Balibo by Indonesian forces during an incursion into Portuguese Timor.
- October 27 - – 18-year-old Robert Poulin begins shooting in St. Pius X High School in Ottawa, Canada and then shoots himself, killing 1 and wounding 5.
- October 29 - Peter Sutcliffe (the "Yorkshire Ripper") commits his first murder, Wilma McCann.
- October 30 - Prince Juan Carlos becomes acting Head of State of Spain after dictator Francisco Franco concedes that he is too ill to govern.

November

Francisco Franco
- November 3 - An independent audit of Mattel, of the United States largest toy manufacturers, reveals that company officials fabricated press releases and financial information to "maintain the appearance of continued corporate growth."
- November 3 - First oil pipeline opens from Cruder Bay to Grangemouth
- November 6 - Green March begins: 300,000 unarmed Moroccans converge on the southern city of Tarfaya and wait for a signal from King Hassan II of Morocco to cross into Western Sahara
- November 10 - United Nations Resolution 3379: With a vote of 72 to 35 (with 32 abstentions), the United Nations General Assembly approves a resolution equating Zionism with racism. The resolution provokes an outcry among Jews around the world.
- November 10 - The 729-foot-long freighter (then, the largest ship on the Great Lakes) SS Edmund Fitzgerald sinks during a storm 17 miles from the entrance to Whitefish Bay on Lake Superior, killing all 29 crew on board
- November 11 - Angola becomes independent from Portugal (a deadly civil war soon erupts)
- November 11 - Australian constitutional crisis of 1975: Australian Governor-General Sir John Kerr dismisses the government of Gough Whitlam and commissions Malcolm Fraser as Prime Minister
- November 11 - First annual Vogalonga rowing "race" in Venice, Italy
- November 14 - Spain abandons Western Sahara
- November 22 - Juan Carlos is declared King of Spain following the death of dictator Francisco Franco.
- November 25 - Suriname gains independence from the Kingdom of the Netherlands
- November 25 - Irish Republican Army outlawed in Britain
- November 25 - Surinam gains independence from the Netherlands
- November 27 - Ross McWhirter, the co-founder of the Guinness Book of Records, is shot dead by the PIRA for offering reward money to informers
- November 28 - Portuguese Timor declares its independence from Portugal as East Timor
- November 29 - The name "Micro-soft" (for microcomputer software) is used by Bill Gates in a letter to Paul Allen for the first time (Microsoft became a registered trademark on November 26, 1976).

December

- December 7 - East Timor invaded by Indonesia.
- December 21 - Left-wing terrorists, including Carlos (the Jackal), kidnap delegates of an OPEC conference in Vienna. They kill three hostages, extort $5 million ransom and escape into the Middle East.
- December 29 - A bomb explodes at LaGuardia Airport killing 11.

Unknown dates

- In New Zealand, Maori leader Whina Cooper leads a march of 5000 people in support of Maori claims to their land
- The Third Cod War between UK and Iceland lasted between November 1975 - June 1976
- Government of Colombia announces finding of Ciudad Perdida
- Spanish army quits Spanish (Western) Sahara. Saharaui Republic (RASD) is created. Morocco invades ex-Spanish Western Sahara.
- First use of the term fractal
- Victoria (Australia) abolishes capital punishment
- South Australia becomes first Australian state to decriminalize homosexual acts between consenting adults
- Self-proclaimed time traveller John Titor arrives to acquire an IBM 5100 for use in 2036
- MIND opens
- In May, rock singer Peter Gabriel announces that he is leaving British progressive rock band Genesis after their successful The Lamb Lies Down On Broadway tour.
- Jehovah's Witnesses claimed that Armageddon would happen in 1975 and many of them sold their houses and businesses to prepare for the new world of paradise on earth which they believe will exist when Jesus comes back.
- BACCHUS Network, American college alcohol peer-education network established.
- The Rock and Roll band KISS releases their Alive! album, catapulting them into record success. The album goes 4x platinum. Kiss was having trouble with record sale until then, as they sounded much different live then they did on record. They solved this problem by creating live albums.

Births

January-April

- January 2 - Doug Robb, American singer (Hoobastank)
- January 3 - Danica McKellar, American actress
- January 5 - Bradley Cooper, American actor
- January 13 - Shazia Mirza, British comedienne
- January 20 - Mark Allan Robinson, Canadian recall leader
- January 22 - Balthazar Getty, American actor
- January 25 - Tim Montgomery, American athlete
- January 29 - Sara Gilbert, American actress
- February 2 - Todd Bertuzzi, Canadian hockey player
- February 2 - Ieroklis Stoltidis, Greek footballer
- February 4 - Natalie Imbruglia, Australian musician
- February 5 - Adam Carson, American drummer (AFI)
- February 17 - Wish Bone, American rapper
- February 20 - Brian Littrell, American musician (Backstreet Boys)
- February 22 - Drew Barrymore, American actress
- March 5 - Jolene Blalock, American actress
- March 5 - Niki Taylor, American model
- March 9 - Roy Makaay, Dutch football player
- March 15 - Eva Longoria, American actress
- March 15 - Veselin Topalov, Bulgarian chess player
- March 17 - Justin Hawkins, British singer (The Darkness)
- March 27 - Stacy Ferguson, American singer (Black Eyed Peas)
- April 4 - Scott Rolen, baseball player
- April 4 - Delphine Arnault, billionaire French businesswoman LVMH
- April 7 - Ronde Barber, American football player
- April 7 - Tiki Barber, American football player
- April 9 - Robbie Fowler, British footballer
- April 14 - Amy Dumas, American professional wrestler
- April 22 - Greg Moore, Canadian race car driver (d. 1999)

May-August

- May 1 - Marc-Vivien Foé, Cameroonian footballer (d. 2003)
- May 2 - David Beckham, English footballer
- May 3 - Kimora Lee Simmons, American fashion designer
- May 3 - Maksim Mrvica, Croatian pianist
- May 8 - Enrique Iglesias, Spanish-born singer
- May 10 - Hélio Castroneves, Brazilian race car driver
- May 12 - Jonah Lomu, New Zealand rugby player
- May 14 - Hunter Burgan, American bassist (AFI)
- May 15 - Ray Lewis, American football player
- May 19 - London Fletcher, American football player
- May 25 - Lauryn Hill, American singer
- May 27 - Jamie Oliver, British chef and television personality
- June 4 - Angelina Jolie, American actress
- June 17 - Chloe Jones, American actress
- June 9 - Andrew Symonds, Australian cricketer
- June 18 - Martin St. Louis, Canadian hockey player
- June 25 - Vladimir Kramnik, Russian chess player
- June 27 - Tobey Maguire, American actor
- July 6 - 50 Cent, American rapper
- July 11 - Lil' Kim, American rapper
- July 17 - Konnie Huq, English television presenter
- July 18 - Torii Hunter, baseball player
- July 18 - Daron Malakian, American guitarist and singer (System of a Down)
- July 22 - Erol Spencer Hofmans, Dutch political scientist
- July 24 - Torrie Wilson, American professional wrestler and model
- July 27 - Shea Hillenbrand, baseball player
- July 27 - Alex Rodriguez, baseball player
- July 30 - Graham Nicholls, British artist
- August 7 - Charlize Theron, South African actress
- August 15 - Kara Wolters, American basketball player
- August 24 - Hayato Sakurai, Japanese martial artist

September-December

- September 17 - Jimmie Johnson, American race car driver
- September 17 - Constantine Maroulis, American singer
- September 20 - Rikki Lee Travolta, Italian-American actor
- September 23 - Chris Hawkins, British radio personality
- September 25 - Matt Hasselbeck, American football player
- October 2 - Michel Trudeau, son of Canadian Prime Minister Pierre Trudeau and Margaret Trudeau, ( d.1998)
- October 5 - Kate Winslet, British actress
- October 23 - Odalys Garcia, Cuban-born actress
- November 10 - Markko Märtin, Estonian race car driver
- November 17 - Diane Neal, American actress
- November 18 - David Ortiz, Dominican Major League Baseball player
- November 19 - Sushmita Sen, Indian beauty queen and actress
- November 20 - Dierks Bentley, American singer and musician
- November 20 - Timea Vagvoelgyi, Hungarian erotic star
- November 20 - Davey Havok, American singer (AFI)
- November 24 - Lee Wan Wah, Malaysian badminton player
- December 5 - Ronnie O'Sullivan, British snooker player
- December 13 - Tom Delonge, American guitarist and singer (blink-182)
- December 14 - Justin Furstenfeld, American guitarist and singer (Blue October)
- December 17 - Milla Jovovich, Ukrainian actress and model
- December 18 - Masaki Sumitani, Japanese television performer
- December 18 - Trish Stratus, Canadian professional wrestler and fitness model
- December 23 - Sky Lopez, American actress
- December 27 - Heather O'Rourke, American actress (d. 1988)
- December 30 - Tiger Woods, American golfer

Deaths

Unknown date

- Will Mastin, American vaudevillian

January-March

- January 8 - Richard Tucker, American tenor (b. 1913)
- January 19 - Thomas Hart Benton, American artist (b. 1889)
- January 24 - Larry Fine, American actor and comedian (b. 1902)
- January 27 - Bill Walsh, American film producer and writer (b. 1913)
- February 4 - Louis Jordan, American musician (b. 1908)
- February 8 - Robert Robinson, British chemist, Nobel Prize laureate (b. 1886)
- February 10 - Nikos Kavvadias, Greek poet and writer (stroke) (b. 1910)
- February 13 - André Beaufre, French general (b. 1902)
- February 14 - Julian Huxley, British biologist (b.

Fractal

History

Contributions from classical analysis

Aspects of set description

Mandelbrot's contributions

Definitions

Categories of fractals

Examples

Fractals in nature

Applications

Fractal generation

See also

Further reading

External links

Geometry

The earliest geometry

The Greek period (c. 600 B.C. – 600 A.D.)

Thales and Pythagoras

Plato

Euclid

Archimedes

After Archimedes

The Middle Ages, Renaissance, and Reformation

The 17th and early 18th centuries

The late 18th and 19th centuries

Non-Euclidean geometry

Introduction of mathematical rigor

Analysis situs, or topology

The 20th century

See also

External links

Recursion

Recursion in mathematics

Functional Recursion

Recursive Proofs

Recursion in computing

Recursion in language

Recurrence relations or algorithms

Recursively defined sets

Example: the natural numbers

Example: The set of true reachable propositions

Recursively defined functions

Recursive algorithms

The recursion theorem

Proof of uniqueness

Proof of existence

Recursion in plain English

Recursive humour

See also

References

External links

1975

Events

January

February

March

April-May

June-July

August

September

October

November

December

Unknown dates

Births

January-April

May-August

September-December

Deaths

Unknown date

January-March