Alan Turing and Computability

Yesterday (June 23), would have been the 100th birthday of Alan Turing, the mathematician who was one of the founders of modern computer science – indeed he is often considered to be the “father of computer science.”

In the 1920s and 1930s, much attention in the mathematics was on the subject of “computable numbers” and finding automatic systems for proving mathematical statements.   Based on a series of problems stated by David Hilbert, the mathematician Kurt Gödel ultimately proved that this not possible.  Essentially, there is no formal mathematical system that can decide the truth or falsehood of all mathematical statements.   This is quite profound and simple to state, but Gödel’s mathematics is cryptic and at some times impenetrable.   By contrast, Alan Turing’s formulation of the mathematics as a simple device is quite accessible and laid the groundwork for the positive use of Gödel’s results.  Sure, we cannot solve all mathematical problems computationally, but we can do quite a lot with the right tools.  The Turing Machine is one of the simpler of such tools.


A Turing Machine consists of a tape, or an infinite sequence of cells, each of which contains a symbol that can be read or written.  There is a head, which (much like the head on a tape recorder) moves along the tape and is always positioned at one cell.  The state register contains one or more states of the machine.  Finally, the transition table contains a series of instructions of the form qiaj→qi1aj1dk where q is a state, a is a symbol, and d is a number of cells to move the head left or right along the tape (including not moving it at all).  So, if the machine is at a given state qi and the head is over a symbol aj, switch to state qi1, write the symbol aj1 at the head, and move the head dk positions to the left or right.

The description of the Turing Machine is very mechanical, which makes it a bit easier to understand.  But it is nonetheless a formal mathematical model.  It was used to demonstrate that the “halting problem”, the ability of such a machine to determine if any set of states and transitions will stop or repeat forever, is not solvable.  This remains today, one of the great unsolvable problems in computer science.

About the same time as Turing published his results, American mathematician Alonzo Church published an equivalent result using lambda calculus, a system I personally find more intuitive and elegant because of its basis in functions and algebraic-like expressions (it will be the subject of a future article).  But Turing’s work has been more prominent both in mainstream computer science and in the culture at large, with computer designs and languages being described as “Turing complete”.  And then there is the “Turing Test” for evaluating artificial intelligence systems.  So far, no system has ever passed the test.

During this centennial, especially coming as it does during Pride Weekend in much of the United States, there has been much written about Turing’s homosexuality and his being convicted for homosexual activity that was then illegal in the UK and stripped of his security clearance.  This is a very sad statement on the time in which he lived, that someone who was both one of the most influential mathematicians in a growing field of computation and a hero of World War II for is code-breaking exploits was treated in such a mean and undignified way.  There was also much written about the mysterious circumstances of his death – long considered a suicide, a recent BBC article on the centennial suggests otherwise.  You can read for yourself here.  As for us at CatSynth, we prefer to focus on his achievements.

Google honored Turing yesterday with one of their trademark “Google Doodles” in which they implemented a functioning Turing Machine.


Ackermann’s Function and “Really Big Numbers”

Today we return to to the topic of mathematics with a look at Ackermann’s Function. Anyone who has studied computer science has probably encountered this function (though I’m sure many have gone on to forget it). It is most commonly defined as follows:

This is actually a variant of Wilhelm Ackermann’s original function, often called the Ackermann–Péter function. It is quite a simple function to define and to trace, and it is very easy to implement in just about any programming language, including Python:

def ackermann(m, n):
  if m == 0:
    return n + 1
  elif n == 0:
    return ackermann(m - 1, 1)
    return ackermann(m - 1, ackermann(m, n - 1))

However, its complexity (in terms of run-time and memory) grows quite quickly. As such, it is often used as an exercise in teaching students more complex forms of recursion, and also as a test case in compiler development for optimizing recursion. It also has some interesting mathematical properties for particular values of m:

The numbers in the case of A(4,n) are quite large. Indeed, one could describe Ackermann’s function as “computing really really large numbers really really slowly.” Although the numbers grow quickly, the function is really just doing subtraction and recursion. We can take advantage of the properties described above, however, to make some shortcuts that yield a much more efficient function.

def ackermann(m, n):
  while m >= 4:
    if n == 0:
      n = 1
      n = ackermann(m, n - 1)
    m -= 1
  if m == 3:
    return 2 ** ( n + 3) - 3
  elif m == 2:
    return 2 * n + 3
  elif m == 1:
    return n + 2
  else: # m == 0
    return n + 1

With this version computing A(m,n) for m≤3 becomes trivial. And this makes computations for m≥4 possible. Or at least A(4,2), which we can actually run in python to reveal the 19,000 digit answer.

You can see the full value on this page. Computing A(4,3) is infeasible. Even with the optimizations, most computers will run out of memory trying to compute this value. But one can still reason about these rather large numbers. Let us move from the more common function we have been using to Ackermann’s original version:

This version has three arguments instead of two, and on the surface it may seem a bit more complicated. However, different values of the third argument p yield very familiar operations.

Again, this function is a rather inefficient way to compute addition, multiplication and exponentiation, but it is an interesting way to reason about them and extrapolate to other more exotic operations. For example, if we take p to be 3, we get the following operation.

Just as m x n is adding m to itself n times, and exponentiation mn is multiplying m by itself n times, this new operation (sometimes called tetration) is the next level: exponentiating m by itself n times.

Such an operation grows so fast as to be uncomparable to exponential growth. It grows even too fast to compare to the gamma function which have explored on CatSynth in the past. This series of ever higher-order operations is often noted with an arrow, called Knuth’s up-arrow notation after legendary computer scientist Donald Knuth.

Using this notation, we can define as sequence of numbers, called Akermann Numbers, where each is an ever higher-order operation of the element applied to itself.

  • 1↑1 = 11 = 1,
  • 2↑↑2 = 2↑2 = 22 = 4,
  • 3↑↑↑3 = 3↑↑3↑↑3 = 3↑↑(3↑3↑3) = 

Even just the 4th number is this sequence is so large that we can’t even easily notate it with exponents. So forget about the 5th number in sequence. But a question that interests me is what about interpolating with real numbers. What is the 1 1/2th Ackermann number? That question, if it even has an answer, will have to wait for another time.

Weekend Cat Blogging and Photo Hunt: Heart

Our combined Weekend Cat Blogging and Saturday Photo Hunt features the theme Heart. We have a few images that blend the theme with our interests in music, mathematics and of course, cats.

Here Luna poses with a heart-shaped kalimba (thumb piano).

Luna peers at the iPad, which displays a plot of a cardioid. We used a mathematical function that produces the heart-shaped figure when plotted with polar coordinates. The formula for the cardioid is: r = 1 – sin(θ), where r is the radius from the center of the plot and θ is the angle sweeping around the center. The best way to visualize polar coordinates is using one of those old circular radar screens where the plotter sweeps in a circular motion.

The photo also features one of Luna’s favorite toys, a heart-shaped plush toy with the word “kitty” inscribed on it. We have had it for years now (indeed, it was featured in a WCB/Photo Hunt back in 2008).

Weekend Cat Blogging #349 (Valentines Day edition) is hosted by Meowza.

The Saturday Photohunt theme is Heart.

The Carnival of the Cats will be up this Sunday at Meowzings of an Opinionated Pussycat.

And the Friday Ark is at the modulator.

11:11 on 11/11/11

At 11:11 on this day 11/11/11, I snapped screenshots of both the iPad and iPhone featuring Luna.

Of course, the symmetry and homogeneity of the date and time is quite attractive, and unique (at least within a given century). The number 111111 is also interesting when you decompose it into primes:

111111 = 11 * 13 * 3 * 37 * 7

I find the prime factorization quite poetic.

We can also factor the date and time together (11:11:11 on 11/11/11):

111111111111 = 11 * 13 * 3 * 37 * 7 * 101 * 9901

Note quite as poetic as the previous example, but still interesting. In particular, 9901 is interesting as the greatest prime factor for any repeating series of 12 numbers. Other related properties can be seen at the site Prime Curios.

Weekend Cat Blogging and Photo Hunt: Digital

The theme of this week’s Photo Hunt is digital. Rather than simply use a digital photo – which could be any photo ever taken of Luna – I chose a couple of images that demonstrate the unique opportunities of the medium. A digital photo is really just a stream of numbers, not unlike digital audio, and can be processed in countless ways using digital signal processing or applying other mathematical functions.

For a piece I originally did in 2007, I took one of Luna’s adoption photos from Santa Cruz County Animal Services and applied an algorithm that overlaid these colored bands, as shown above.  The color bands were generated using a set of hastily chosen trigonometric and hyperbolic functions applied to the timeline of the animation sequence.  These photos are stills from the full animation.

I did these using image and video extensions to Open Sound World – one nice feature of that work was that I could use the same functions for both audio and video, and “see” what a particular audio-processing algorithm looked like when applied to an image.   And I would probably use the Processing environment for future visual work, perhaps in conjunction with OSW.

Weekend Cat Blogging #309 and Carnival of the Cats are both being hosted by Billy SweetFeets this weekend. Perhaps Luna’s animation could be part of one of the dance videos they often feature.

Photo Hunt #264 is hosted by tnchick. This week’s theme is digital.

And the Friday Ark is at the modulator.

A special note this week. Our friend Judi at Judi’s Mind over Matter (home of Jules and Vincent) has information on how to help animals affected the storms and tornadoes in the southeast US. They live in Alabama, not far from the place that was hit hardest by the tornadoes. We’re glad they’re safe, and able to provide this information for those who would like to help.


Sometimes when things get a bit overwhelming it’s good to turn to numbers and highways. As mentioned in earlier posts, I maintain a rather cursory yoga routine for both health/exercise and grounding. The number 108 comes up fairly often in cycles of repetition and I have been curious about its significance. Long before it was featured on Lost, 108 prominently figured in Hinduism as the number of beads on a mala and in other contexts, and through Hinduism finds its way into Buddhism. 108 has several interesting purely mathematical properties. My favorite is its being the hyperfactorial of 3. The hyperfactorial is the product of consecutive integers, each raised to itself as an exponent:

11 x 22 x 33 = 108

Among the more random properties is being the sum of 9 consecutive integers:

8 + 9 + 10 + 11 + 12 + 13 + 14 + 15 + 16 = 108

9 is of course a divisor of 108, as in 9 x 12 = 108. And both 9 and 12 appear in the above series.

More significantly, 108 degrees is the angle of a vertex a regular pentagon, and 108 degrees can also be used to derive the golden ratio.

The relationship to the golden ratio would seem to be an interesting one, until one remembers that the representation of angles as degrees is itself arbitrarily based on the number 360. The 3π/5 radian representation is more significant in this regard.

And what about fun with highways numbered 108? Here in California, state highway 108 runs from the Central Valley town of Modesto northward and eastward across the Sierra via the Sonora Pass (north of Yosemite) to meet US 395 on the eastern side of the Sierra.

[Photo by jodastephen on flickr.  (License CC BY-ND 2.0)]

While I have not driven CA 108, I am sure I have crossed its path on CA 120 on the way to Yosemite. From the picture above, it looks like it would be a nice drive, particularly in the summer. The eastern side of the Sierra has that stark, desolate quality, in comparison to the heavily wooded slopes on the western side. They are both quite beautiful, but the eastern side tends to speak to me more.

In New York, Route 108 is a short highway on Long Island. In fact, it is very short, a little under two miles total.  It’s southern terminus is the picture below.

[Photo by dougtone on flickr.  (License CC BY-SA 2.0)]

Route 108 southbound crosses into Nassau County, but soon curves away back into Suffolk. Soon after, the two-lane road continues into Trail View State Park, where the route becomes desolate, passing two local ponds.

It is interesting how the word “desolate” can come up for both highways, with very different connotations.

Pi Day, 2011 (with Music)

Every year, we at CatSynth join numerous other mathematics enthusiasts, geeks and otherwise eccentric characters in celebrating Pi Day on March 14.

March 14 is notated in the U.S. and some other countries as “3-14”, which evokes the opening digits of π (pi). Although the date representation is a very arbitrary connection to the number, we also recognize that the representation of π in decimal digits is arbitrary, an accident of human beings having ten fingers. So this year we are exploring the representations in binary and other related bases.

To represent an integer in binary, one of course presents it as a sum of powers of two, e.g., 11 = 8 + 2 + 1 or 1011 in binary. But one can also represent fractional numbers in binary. Digits to the right of the decimal point represents powers of one-half. So the binary number 0.11 is 1/2 + 1/4, or 3/4. Fractions like 1/3 can be represented with repeating digits as 0.010101…, much like in base ten. And this concept can be extended to irrational numbers like π.

The author of this website has calculated 32768 digits of pi in binary. We reprint the first 258 below:

00100100 00111111 01101010 10001000 10000101 10100011 00001000 11010011 
00010011 00011001 10001010 00101110 00000011 01110000 01110011 01000100 
10100100 00001001 00111000 00100010 00101001 10011111 00110001 11010000  
00001000 00101110 11111010 10011000 11101100 01001110 01101100 10001001 

The initial “11” represents the 3 in π, and the remaining digits begin the non-integral portion. Like in the decimal representation, the binary representation continues forever with no particular pattern. While not as iconic or memorable as the decimal representation 3.14159…, there is something about the binary representation that makes it seem more universal, i.e., based on fundamental mathematical truths rather than a quirk of human anatomy. For me, the binary representation also lends itself to musical ideas. And for the occasion, I have created a couple of short synthesized pieces representing the 32768 binary digits of pi. In the first example, each binary digit represents a sample. The “1” represents full amplitude and the zero represents no amplitude (silence). The result, which at 44.1kHz sample rate is less than one second long, can be heard below.

The random configuration of digits sounds like noise, and more specifically like white noise, suggesting something approaching uniform randomness at least to human hearing. I also made an example slowed down to a level whether the individual samples became musical events. I find this one quite interesting.

With some additional refinement (and may some more digits to extend the length), it could certainly stand alone as a composition.

One interesting counterpoint to the notion that digits of pi form white noise is a conjecture related to its representation in hexadecimal (base 16), which as a power of two is “closer” to binary and seemingly less arbitrary than decimal. From Wolfram MathWorld, we find the following “remarkable recursive formula conjectured to give the nth hexadecimal digit of π – 3 is given by where is the floor function:

The formula is attributed to (Borwein and Bailey 2003, Ch. 4; Bailey et al. 2007, pp. 22-23). If true, it would add some sense of order to the digits, and thus additional musical possibilities.

Properties of 2011

The number “2011” abounds with fun numerical and “visual-numerical” properties. Early into the new year, we experienced the time “1:11:11 on 1/1/11”. And this week, we had the even more auspicious “1:11:11 on 1/11/11”, at least with the date-writing convention we use in the United States. This week all the dates have been palindromes using the two-digit year convention, e.g., today is “1 14 11”, and if one uses the full four-digit year, this past Monday was “1 10 2011”, also a palindrome.

While text-based properties are fun, they are somewhat arbitrary and less interesting than mathematical properties of numbers. First, 2011 is a prime number, the first prime year since 2003. And from @mathematicsprof on twitter, we have this interesting coincidence:

“2011 is also the sum of 11 CONSECUTIVE prime numbers:

In other words, this is not just a series of prime numbers, but all the prime numbers between 157 and 211. I like that the last prime in the series happens to be 211!

The Republic of Math blog follows the consecutive-prime inquiry further, with the observation that 2011 can also be written as the sum of three consecutive primes “661 673 and 677”.

From The Power of Proofs, we have the property that 2011 is the sum of three squares:

2011 = 392 + 172 + 72

However, any number not congruent to 7 modulo 8 will have such a property. I.e., if you divide 2011 by 8, you have 3 left over. So really 7 out of 8 integers can be expressed this way. Finding the series of squares can take some time, though.

Please feel free to share any other mathematical or fun coincidental properties in the comments below.

RIP, Benoit Mandelbrot

Today we return to mathematics, and sadly note the passing of Benoît Mandelbrot. His work was very influential not only within mathematics and science, but also art and music.

Benoit Mandelbrot. (Photograph by Rama via Wikimedia Commons.)

He is credited with coining the term “fractal” (literally, “fractional dimension”) and is often dubbed the “father of fractal geometry” – and he is of course memorialized by the Mandelbrot set (which is technically not a fractal). I had written an article that touched on the Mandlebrot set and fractals for this site back back in 2008.

This quote from his official site at Yale sums up the wide-ranging applications of his work to science and the humanities:

Seeks a measure of order in physical, mathematical or social phenomena that are characterized by abundant data but extreme sample variability. The surprising esthetic value of many of his discoveries and their unexpected usefulness in teaching have made him an eloquent spokesman for the “unity of knowing and feeling.”

I did have the opportunity to take a course at Yale for which he was a regular lecturer (the course was taught by his former colleague at IBM Research, Richard Voss). The course was aimed at an introductory audience, and I think many of the students did not appreciate the opportunity it presented – but that left me with more time to directly ask him deeper questions in both lectures and seminars. At the end of the term, he signed my personal copy of The Fractal Geometry of Nature, which still has a place of honor on my bookshelf.

[click to enlarge]

In reading some of the online articles this morning, I also was reminded that he and his family were part the great exodus of Jewish intellectuals from Poland and other parts of Eastern Europe in the years before World War II. It’s a story that comes up time and time again among thinkers, writers and teachers who have influenced me of the years.

Theano’s Day

We at CatSynth are participating in Theano’s Day, an event to celebrate women in Philosophy. It is named in honor of Theano, the wife of the Greek philosopher and mathematician Pythagoras but also a scholar in her own right. In addition to promoting the work of Pythagoras, she put together her own work on mathematics, art, and beauty, all topics that are a regular part of this site. She is often credited with developing the Golden Mean, one of the most well-known ideas in aesthetic theory in which art, whether spacial (painting, sculpture, architecture) or temporal (music, drama) include structural elements based on the golden ratio φ, which is the ratio a / b such that a / b = (a + b) / a.

The number appears in the Fibonacci series as well, and in the well-known spiral that is used to describe proportions in nature and in architecture:

Theano is also credited with writings about child rearing and gender (although I am having difficulty finding a reference to this). Gender identity seems to permeate the work of many female philosophers over the centuries, indeed it seems to be an inescapable topic. The seventeenth century scholar and artist Anna Maria van Schurman published Whether the Study of Letters Is Fitting for a Christian Woman? in which she argued in favor of women’s education. In the modern era, there is of course Simone de Beauvoir whose writing is considered foundational for contemporary feminism. But I am personally more interested in the treatment of gender as it relates to other philosophical and intellectual topics rather than social, political or biological. How does the concept of “the feminine” relate to existentialism in de Beauvoir’s novels, or to Schurman’s art or Theano’s mathematics? This is not a topic that can easily be covered in a single post, or on a single day, but relates deeply to some of the directions I am exploring in visual art (i.e., photography) and perhaps later on in music as well. So perhaps the best way to see this day is as a beginning…