Posted on Leave a comment

The Three Laws of Recursion

Recursion | Russian dolls

Like the robots of Asimov, all recursive algorithms must obey three important laws:

  • A recursive algorithm must have a base case.
  • A recursive algorithm must change its state and move toward the base case.
  • A recursive algorithm must call itself, recursively.

Recursion is the process of defining a problem (or the solution to a problem) in terms of (a simpler version of) itself. For example, we can define the operation “find your way home” as: If you are at home, stop moving. Take one step toward home.

Let’s begin our discussion of recursion by examining the first appearance of fractals in modern mathematics. In 1883, German mathematician George Cantor developed simple rules to generate an infinite set:

Cantor’s rule for an infinite set

There is a feedback loop at work here. Take a single line and break it into two. Then return to those two lines and apply the same rule, breaking each line into two, and now we’re left with four. Then return to those four lines and apply the rule. Now you’ve got eight. This process is known as recursion: the repeated application of a rule to successive results. Cantor was interested in what happens when you apply these rules an infinite number of times.

George Cantor

Dichotomy paradox – Zeno’s

“That which is in locomotion must arrive at the half-way stage before it arrives at the goal.”

— as recounted by Aristotle, Physics VI:9, 239b10

Suppose Atalanta wishes to walk to the end of a path. Before she can get there, she must get halfway there. Before she can get halfway there, she must get a quarter of the way there. Before traveling a quarter, she must travel one-eighth; before an eighth, one-sixteenth; and so on.

Zeno’s paradox was recursive by cutting the distance in half each time to the infinitesimal. This is also how the Tortoise beat the Hair by questioning time over distance.

Recursive Function Calls

The tortoise and the Hair – the paradox of time
int factorial(int n) 
{ if (n == 1) { return 1; }
else { return n * factorial(n-1); } }

A function that does call others is called a nonleaf function. … The factorial function can be rewritten recursively as factorial(n) = n × factorial(n – 1). The factorial of 1 is simply 1. The image shows an object trace of the factorial function written as a recursive function. Each call goes in the run time stack until the base case is reached, and the the stack is popped as the result is passed to each function on the stack.

Five Factorial (5!) in recursion

What Is a Fractal?

The term fractal (from the Latin fractus, meaning “broken”) was coined by the mathematician Benoit Mandelbrot in 1975. In his seminal work “The Fractal Geometry of Nature,” he defines a fractal as “a rough or fragmented geometric shape that can be split into parts, each of which is (at least approximately) a reduced-size copy of the whole.”

Recursion in Nature

Looking closely at a given section of the tree, we find that the shape of this branch resembles the tree itself. This is known as self-similarity; as Mandelbrot stated, each part is a “reduced-size copy of the whole.”

The Three Laws of Robotics

Isaac Asimov was an American writer and professor of biochemistry at Boston University. During his lifetime, Asimov was considered one of the “Big Three” science fiction writers, along with Robert A. Heinlein and Arthur C. Clarke. A prolific writer, he wrote or edited more than 500 books.

  • A robot may not injure a human being or, through inaction, allow a human being to come to harm
  • A robot must obey the orders given it by human beings except where such orders would conflict with the First Law
  • A robot must protect its own existence as long as such protection does not conflict with the First or Second Laws
Partial sources: https://natureofcode.com/book/chapter-8-fractals/, Wikipedia, Google 
Posted on 2 Comments

Continuum Hypothesis

Georg CantorGeorg Cantor’s conjecture, the Continuum Hypothesis

Without equations, this states that for any set of real numbers, S, one of three things happen:

  1. S is finite.
  2. S has a 1-1 correspondence to the integers.
  3. S has a 1-1 correspondence to the reals.

There is nothing in between the integers and reals. Kurt Goedel showed that this was consistent with set theory, and Paul Cohen showed that its negation was consistent. In other words, CH is an undecidable proposition of Zermelo-Frankel set theory (and of ZFC, ZF with the Axiom Of Choice). Ditto for the Generalized Continuum Hypothesis. — Eric Jablow

Continue reading Continuum Hypothesis

Posted on Leave a comment

Number as Archetype

Carl Jung
By Robin Robertson

Excerpts:

  • … Because human beings are capable of counting (“one, two, three…”), we imagine that is how numbers were arrived at.
  • … The story seems to demonstrate that a crow (or at least the crow in the story) has a sense of “one”, “two”, “three”, and “many”.
  • … In brief, one corresponds to a stage of non-differentiation; two—polarity or opposition; three—movement toward resolution, as expressed, e.g., in the Christian trinity.

Carl JUngThis paper has been adapted from the final chapter of Jungian Archetypes: Jung, Godel and the History of Archetypes, Nicolas-Hay, 1996, with the permission of Nicolas-Hay. Copyright Nicolas-Hay Publishers.

The sequence of natural numbers turns out to be unexpectedly more than a mere stringing together of identical units: it contains the whole of mathematics and everything yet to be discovered in this field. — Carl Jung[1]

It has turned out that (under the assumption that modern mathematics is consistent) the solution of certain arithmetical problems requires the use of assumptions essentially transcending arithmetic; i.e., the domain of the kind of elementary indisputable evidence that may be most fittingly compared with sense perception. — Kurt Godel[2]

Continue reading Number as Archetype