New Blog Excitement

My girlfriend has a new blog called The Language of Bad Physics. Although I don't understand everything that she talks about, if you like physics and like nonsense getting eviscerated, you will probably enjoy her blog.

Scientist Appreciation: Persi Diaconis the Mathemagician

Dr. Persi Diaconis is a fascinating man, and part of that fascination comes from the fact that he can claim title to one of the simultaneously coolest and silliest job names ever: mathemagician. I saw Diaconis give a talk on mathematics and magic at the Fields Institute a couple of years ago, and it is one of my favourite all time talks. Diaconis is engaging, charismatic, and relates a sense of absolute enjoyment of both mathematics and performance trickery. Having worked as both a professional magician and as a professor in departments of both statistics and mathematics, Diaconis exudes the combined sense of wonder and power that can be found in the study of mathematics.

Aside from the one talk I visited, I don't have a lot to present about Persi Diaconis that is not available on either Wikipedia or his website. I had intended to share one of his tricks that I saw him demonstrate, but I think it would be better to try and show it. That, however, requires a little more organization than I currently have (including a tripod for my camera and a volunteer to be in the video with me), so you will have to wait for me to get everything together. In the meantime, if you get the chance to see a talk by Dr. Persi Diaconis, I highly recommend it.

The History of Computability

As part of my forays into the subjects of philosophy and empiricism, one of the things I advocated for is the idea that scientists should be more aware of the philosophical underpinnings of their respective fields. I have been meaning to do a series on the philosophical underpinnings of my own chosen field (namely, how intelligence works) for quite some time now, but in order to do that I need to lay some groundwork. One of the most important pairs of concepts for the theoretical pursuit of understanding how intelligence works is also the fundamental pair of concepts underlying computer science: computability and complexity. As I had mentioned in my Scientist Appreciation of Alan Turing, computer science is a relatively young discipline with much of its fundamental work done by Alan Turing and Alonzo Church (who I never did get around to doing a Scientist Appreciation about). These days people take the idea of a programmable electronic device for granted, but it was remarkably recent that a formal architecture to describe and discuss such devices was actually rigorously developed.

Before I get too far ahead of myself, however (and electronic computers are quite far ahead), I will begin at the turn of the 20th century. A remarkably brilliant man named David Hilbert compiled a list of 23 unsolved mathematical problems in 1900. This list in many ways served as a sketched outline to guide theoretical research for the coming century, with a number of the problems remaining unsolved even today. Although many of Hilbert’s problems are fascinating in their own right (I’m sure all of them probably are, but I don’t actually understand a few of them), the one which is relevant to the discussion at hand is his tenth problem. Hilbert's tenth problem is ordinarily written as something along the lines of

Find an algorithm to determine if a given Diophantine equation with integer coefficients has an integer solution.

However, this is not actually how Hilbert posed the problem, as the word algorithm had yet to enter useage (Webster's New World Dictionary, for example, did not include the word 'algorithm' prior to 1957). The actual original statement of the problem was something along the lines of:

Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers.

Before a number of my readers balk at the term 'Diophantine equation', it simply means an indeterminate polynomial equation (for example, x + y = 5 is an Diophantine equation, since there is no single assignment of values that satisfies the equation. Rather, the solution is the line x = 5 - y).

As I mentioned, at the time that Hilbert originally posed this problem the term algorithm was not in use. An algorithm is essentially a process or sequence of instructions, but with a number of specific properties (namely, that it has a finite sequence of instructions and is well defined (at no point does it reach a state in execution in which it is not clear what it is to do next)). Informally, algorithms have been around for centuries. One of the most famous (and one that is likely familiar to any computer science student) is Euclid's algorithm for determining the greatest common divisor of two numbers. However, prior to Hilbert's problems, very few people had ever attempted to analyse the notion of abstract processes. Mathematicians and scientists developed and utilized specific mathematical methods for specific problems, but, for the most part, each one was developed and investigated within the context of its application alone. What changed all of this was that people began to question whether or not there actually existed the process that Hilbert's tenth problem was asking for. The fact that some problems could be unsolvable was a fairly ground-breaking notion, and provided the impetus to explore the general notion of solvable methods.

Although the actual proof that no such algorithm exists which can solve Hilbert's tenth problem did not come about until 1970 with the publication of Yuri Matiyasevich's doctoral dissertation, the inkling that it might be unsolvable began much earlier, particularly from the field of logic with Kurt Gödel's famous incompleteness theorems. Motivated by the growing question of solvability and mathematical truth, in 1928 Hilbert proposed another, more general algorithmic challenge called the Entscheidungsproblem (decision problem). The Entscheidungsproblem takes a formal language and a mathematical statement in that language as input and outputs whether or not it is true. The problem piqued the interest of both Church and Turing, motivating the two of them to independently formalize the concept of calculability in the mid 1930s. Both Church and Turing independently showed that the Entscheidungsproblem could not be solved. The models of computation that Church and Turing each used (λ-calculus and Turing machines, respectively) were subsequently shown to be equivalent, and thus the field of computability was formed.

I will discuss the actual material of computability in the next post on this topic, but I thought an historical overview might help illustrate the motivations behind the field as well as provide a somewhat less painful introduction for those not familiar with the terms. I am not sure I was entirely successful with the latter aim, but feel free to leave any comments or send me questions via email for parts that are not clear.

Timothy Williamson and the Philosophy of Philosophy

A couple weeks ago, I went to a lecture at the Paulinerkirche given by Professor Timothy Williamson, a philosopher from Oxford, entitled Armchair Knowledge and the Philosophy of Philosophy. The talk was for a general audience, so I am sure Professor Williamson simplified his arguments and glossed over some of the supporting ideas that have helped spur his own, but I still felt somewhat dissatisfied with overall presentation and thrust of his argument.

Professor Williamson started with a description of the general practice of philosophy as an exercise of cogitation one performs from the comfort of an armchair. He then gave a humorous anecdote about an Irish chemist being surprised that English universities regularly also had philosophy departments (the chemist had assumed that Dublin's Trinity College philosophy department continued to exist as a matter of tradition rather than for any sort of pragmatic utility). Thus, Williamson set up the central conflict on which his talk centered as the question of whether or not the criticism of philosophy as antiquated and made obsolete by experimental science was apt, and what that meant for the motivations and practice of philosophy (the philosophy or philosophy, if you will).

The central thrust of Williamson's argument started with the idea that no one is a pure empiricist, as basing all of one's beliefs on direct empirical evidence is impossible. In this, Williamson is certainly correct. Earning one's education is in many ways an exercise in academic trust, although, as was astutely pointed out in the How To Think About Science series, one of the inherent strengths of science rests not so much with its skeptical roots as with its ability to determine who and what to trust. One of the problems I continually run into in subjects outside of the realm of science (and even within some discourse that claims it is scientific - namely certain branches of psychology) is that the established basis for some discourse is not clearly defined or, in some cases, is clearly defined but erroneous (either in light of later discoveries, in which case it may be excusable, or simply because it was assumed true without empirical evidence, in which case it is less excusable). For example, as those who remember my reviews of a selection of historical treatises on political theory may recall, I was thoroughly disappointed with both Plato and Aristotle. I thought Hobbes did a much better job by specifically and carefully defining his terms and assumptions (some might claim that this was a little overly pedantic on his part, making his text more difficult to digest than one which skips over such dry discourse as careful definitions, but it is important nonetheless). Of course, I think Hobbes' analysis still ends up flawed, but it is much easier to follow his reasoning and in that way determine where I disagree thanks to his methodological approach. I seem to be getting away from myself, however. Getting back to Williamson's talk, I grant that calling for a purely empirical framework for knowledge and belief is not feasible. We do choose to trust knowledge disseminated by other sources, but I think the important point here rests on our determination of the trustworthiness of sources. Basing trust on human charisma, while often the most common method, is unfortunately a highly flawed method as it easily leaves one open to being taken advantage of. The system created around unbiased and rigorous verification of knowledge rooted entirely within the natural world that is modern science is the best that I think we can currently hope for in the department of trust.

Continuing from the fact that everyone accepts knowledge not personally empirically derived, Williamson also brings up the fact that even empirical scientists further process empirical results with a set of mental reasoning tools which Williamson classified as akin to imagination. We are mentally capable of trying out ideas and following avenues of thought which have not explicitly been borne out in the real world. At this point, Williamson went on a slightly odd detour by ruminating on the origins of the human capacity for reasoning given our evolutionary past. He justified its survival advantage by giving an example of a person running from a tiger - the person would be able to gage the appropriate response by running through possible future scenarios in their mind (such as hiding behind a rock, climbing a tree, and so on). Of course, it was a simplistic example, so I won't spend too long quibbling with it, but I do want to point out that any person who stopped to think so carefully while being chased by a tiger was going to be caught and eaten. Our capacity for rational thought serves more to modulate what sorts of behaviours we practice to increase our future survival capacity rather than serving us in speedy split-second survival decisions. Ignoring that nuance for the sake of the argument, however (and it does not particularly change the logic to go from reasoning about what sorts of behaviours are best to practice for future enactment and what sorts of behaviours one should execute in the current moment), it is true that we continually process empirical information (often in ways we are not even immediately aware of - see my series on top-down processing in vision).

Essentially, those two points are what led Williamson to his justification for philosophy. Philosophy is therefore, according to my understanding of Williamson, simply engaging our capacity of hypothetical rational thought as a valid exercise in knowledge derivation. I would contend, however, that Williamson's version of philosophy is continuous with and enveloped by the combined fields of mathematics and science, and the areas of philosophy that remain outside of those fields still have no valid justification as sources of worldly knowledge. As I see it, there are two possible ways in which one can engage the rational faculties that Williamson established to exist. One can ruminate on the purely abstract, such as the field of logic. Philosophy of that sort, however, becomes indistinguishable from the field of mathematics. It can be a valuable avenue of thought, but it does not tell us directly about the world. When philosophy moves beyond the abstract and begins to make statements about reality, then I think it should be held to the same empirical accountability as any theoretical science. Philosophers may not be the ones gathering the empirical data, but that does not excuse them from being aware of the implications of that data. Far too often people entirely ignorant of neurophysiology and even behavioural psychology embark on developing vast treatises of the philosophy of the mind. Of course, philosophers often focus on different questions and aspects of a field, and in that I think they make their most valuable contributions (for example, fields like the philosophy of physics or the philosophy of mathematics, which often draw upon the larger philosophical field of epistemology, are exceedingly important for any scientific field and, in the same way that I think philosophers should make an effort to be aware of at least general trends of empirical results, so too should more scientists be aware of the philosophical underpinnings of their fields). Fundamentally, though, all knowledge of our world is rooted in empirical data, and thus I think the philosophy of philosophy leads us to the same place as the philosophy of science and mathematics.

"Bob Loblaw"

As I have been mentioned a few times over the last couple of days, I gave a talk yesterday morning. I mentioned it so often because I was fairly nervous about it, and I was fairly nervous about it not because it was a talk of any great importance, but because I don't have a lot of experience giving technical talks to highly academic people. The talk was titled Phase Response as a Function of Graph Structure, and was essentially an overview of what I have spent my last month doing. The first half of the talk was a mathematical and intuitive development of the concept of phase response, and then the second half was how that related to dynamical networks (primarily of identical weakly coupled oscillators). Robert left a comment to my post about being nervous, pointing out no one was likely to remember my talk in ten years. As this was an intra-departmental talk to an audience of about ten people, I would be surprised if memories lasted even half that long. What was nice, though, was that I received several compliments on the talk, including from the head of the research group. What was less nice was the Ph.D. student I've been working with and I discovered a handful of minor mistakes on the slides the morning of the talk during my last practice run-through, and my audience managed to spot all but one of them (at least it means they were paying attention). I guess that is what happens when you give a talk to an audience primarily composed of mathematicians and physicists... they actually pay attention to the equations you have on your slides!

I will now try to give a brief overview of what the subject Phase Response as a Function of Graph Structure actually means. If you take an arbitrary dynamical system (which is essentially a fancy word for saying a system that evolves through time) that has a stable periodic limit cycle (which means the system has a state that repeats after a period of time T, and small perturbations to that system will disappear over time and it will settle back to the periodic motion), then you can define something called the phase of the system as how far along in the period the system is. Phase is usually parameterized to be between either 0 and 1 or 0 and 2π by convention. I find the 0 and 1 parameterization more intuitive (it essentially translates to what percentage of the period has already passed, with 0.5 being 50% of the way through from whatever point is defined as the period beginning). The idea of phase can then be generalized to the basin of attraction around the limit cycle (which is essentially the region of your dynamical system's feature space which eventually settles onto your limit cycle), such that a point on the limit cycle and point within the basin of attraction are considered to have the same phase if they evolve through time to the same point on the limit cycle. A rough picture of this idea is shown in Figure 1. This leads to the idea of an isochron (the dotted lines in Figure 1), which is the collection of points in your feature space that all share the same phase.

Figure 1: A point on the limit cycle and off that have the same phase. The mustard yellow curve represents the time evolution of a point off the limit cycle as the moves back to the cycle, while the green curve represents the evolution of a point that starts on the limit cycle. When the mustard yellow curve rejoins the limit cycle, it does so at the same point that the green curve reaches in an equivalent length of time. The two starting points are therefore said to have the same phase.

With phase now defined both on and off the limit cycle, one is able to develop the idea of phase response. If a perturbation (essentially, some sort of externally applied influence that drives the system away from its normal time evolution) is applied to a dynamical system with a stable limit cycle, the phase of the unperturbed system and the perturbed system are both defined (assuming the perturbation is small enough that your system remains within the basin of attraction of the limit cycle), and the change in phase resulting from the perturbation is the phase response of the system (see Figure 2).

Figure 2: The phase response (Δφ, where φ is the phase of the system) to a perturbation ε.

Until now, I have left the discussion fairly open-ended about the properties of the dynamical system under analysis. The idea of phase response is usually applied to the analysis of single oscillators. An example of such a system would be the Hodgkin-Huxley model of a neuron exposed to a constant ambient current such that it is tonically firing at a set period. The feature space of the system is then the voltage across the membrane, the applied current, and the ionic concentrations (both intracellularly and extracellularly) of several key ions (such as potassium and sodium). What we have been investigating is the phase response of networks of oscillators coupled together, at which point the coupling relationship between oscillators becomes part of your feature space. A perturbation applied to one element of the network might ellicit a different phase response than a perturbation applied to another element.

On the surface, one might wonder what the point of all of this is. The thing is, coupled dynamical systems are found in all sorts of areas. Networks of neurons are an obvious example, but gene expression is another area of biological research where there are large systems of interacting biochemical pathways. There are examples outside of biology as well, but I am having a hard time thinking of one off the top of my head since my group tends to focus on the biological tie-in of our research. Therefore, having a better understanding of the phase response of networks will lead to a better understanding of these exceedingly complex systems.

Note: Figure 2 was pulled from Christoph Kirst's diploma thesis, Dynamics of Pulse-Coupled Neuronal Oscillators with Partial Reset. Figure 1 was a (rather shoddy) edit of Figure 2 that I made over the weekend using GIMP.

Looks like there's some explaining to do...

There is a lot about the recent Iranian elections that looks rather suspect - the severe crackdown on foreign journalism and internal dissent, the ridiculous speed of announced results, and the massive landslide victory for the incumbent regardless of the region (including the home cities of his rivals). Now there is further evidence compiled by the Polish astrophysicist Dr. Boudewijn F. Roukema in which he displays highly suspicious and statistically anomalous deviations from Benford's Law. I don't have a lot of time at the moment to try and explain his results (nor do I think I am the best person to try), but I thought it was an interesting case of applied mathematics. Of course, getting a government to admit they recently perpetrated a massive fraud on their own people is a bit like convincing a billionaire that he ought to renounce worldly possessions and live off of the generosity of others. I don't have high hopes for the Iranian regime to come clean and open their records.

An Interesting Link

I've spent the last day and a half working hard on a presentation I have to give tomorrow, so there hasn't been much time for blogging. However, this evening I read an article written by a guest writer at one of the weekly blogs which I regularly read, and it piqued my interest. I thought I would therefore share it with all of my readers. The article is by Steven Strogatz over at The Wild Side. As I have mentioned before, I have a growing fascination with the mathematics of dynamical systems, which is Strogatz's area of study. When I have a little more time I would like to delve into the references he used. In the meantime, I hope others find it as interesting as I did.

The Buffon Needle Problem: The Solution to Puzzle Number Two

I will admit, I have been a little disappointed by the lack of attempts to solve puzzle number two. So far, no one has attempted to send in solutions, either incorrect or correct. Rather than waiting around, I assume in vain, for people to send me attempts, I decided it was about time I posted what I find to be an elegant and fascinating solution.

To briefly reiterate the problem, one is trying to come up with an empirical estimate of π based on repeatedly dropping a rod of length L onto a floor with parallel floorboards separated by distance D. I have generated a quick diagram of the situation in Paint (this computer does not have any actual image editors on it other than Gimp which I am still learning how to use, so please forgive the rudimentary ugliness of the diagram), which also introduces the value of x which is the distance from the centre of the rod to the nearest floorboard edge.
Clearly, x can range from 0 to D/2. As one assumes a uniform probability for the position of the rod, the probability density function of x is 1/(D/2) = 2/D. Things are a little less clear when outlining the properties of the random variable θ, as the most obvious choice (for me) would be it can range from 0 to π. This will, however, cause problems later due to the properties of the sine function (namely that sin(0) = sin(π) = 0), so it is best to define θ as the measure of the acute angle. It can thus range from 0 to π/2, and, also assuming uniform probability, the probability density function of θ is 1/(π/2) = 2/π. Since θ and x are independent, the overall probability density function for the needle can be found by multiplying the two independent density functions together, yielding 4/πD.

Since we are interested in the number of times the rod crosses the lines between the floorboards, we need to determine when that happens. With a little bit of geometry, it is fairly clear that whenever x < (L/2)sinθ the rod crosses the floorboards. Thus, to find the expected fraction of crosses, we need to integrate the probability density function 4/πD over the two random variables, first integrating from 0 to (L/2)sinθ with respect to x and then from 0 to π/2 with respect to θ (if anyone knows how to write integrals in html, I would appreciate it if you could tell me). First, integrating 4/πD with respect to x from 0 to (L/2)sinθ results in 2Lsinθ/πD. Integrating this result with respect to θ from 0 to π/2 yields 2Lsin(π/2)/πD = 2L/πD.

Thus, the expected ratio the number of times the rod crosses the division between floorboards divided by the number of times it is dropped is 2L/πD. As one repeatedly drops the rod and counts the number of crosses, the value will converge to this expected value. Since the length of the rod and the distance between the floorboards is easily measurable, it is a simple computation to achieve an estimate for π.

This is actually a physical example of a branch of computational techniques known as Monte Carlo estimation in which a series of random or pseudorandom samples are used to estimate a result. I find it extremely fascinating, and I think it has a measure of profundity that should not be lightly dismissed. The fact that one is able to simply count a binary event and use that ratio to find an estimate for a much more complicated value is absolutely amazing (of course, it should be immediately obvious that one will never be able to find the actual value of π with this method as the estimate will always be a ratio of number of crosses over number of trials and thus will always be a rational number). Probability and statistics is an amazing branch of mathematics, and it is something I wish I were better at.

Puzzle One Solution

It took me longer than I had planned to get around to posting this solution, but here it is. If you recall, puzzle number one was concerned with finding the starting pair of numbers from 0 to 9 which provided the most iterations before reaching zero of taking the new number pair from the digits of the product of the previous pair. While I invented this puzzle as an aid to falling asleep (in which case brute force mental computation was actually the desired outcome), I was curious to see if anyone would come up with an elegant solution based on numerical logic rather than simply trying every single combination. While Scott (whose blog I just discovered is not on my "Places of Interest" list... I could have sworn it was!) mentioned he did spend some time mentally contemplating the solution, both he and Wisefly ended up doing the same thing I did to confirm the answer - write a short computer program that simply tried every starting combination and looped through the iterations. Wisefly used Excel, Scott used python, and I used MatLab. If anyone is curious about the specific code used to find the solution, either leave a comment or send me an email and I can send you my .m file. Roughly, the pseudocode is as follows:

maxCount = 0, maxStart = 0
for i = 1 to 99
count = 1, x = floor(i/10), y = mod(i,10)
while(x*y > 0)
  count++, iter = x*y
  x = floor(iter/10), y = mod(iter,10)
end while
if(count > maxCount)
  maxCount = count, maxStart = i
end if
end for

Of course, for some reason I cannot get white space to stick around even within block-quotes, so my pseudocode comes out looking like crap. Please forgive its lack of spacing. Also, if you are not used to my pseudocode (which is entirely possible), floor yields the rounded down integer value of the value passed to it (for example, floor(5/3) = 1) and mod is the modulus (or remainder) of the first number by the second (for example, mod(10,4) = 2).

Anyway, running the program yields the correct answer of 77 (or x = 7, y = 7) as your starting value. 7*7 = 49, 4*9 = 36, 3*6 = 18, 1*8 = 08, 0*8 = 0. Thus, there are five iterations before the value becomes 0. As was pointed out to me, this was a relatively straightforward puzzle when one wrote a computer program to solve it (and even without the computer program it was feasible to solve by some relatively simple number crunching). Wisefly suggested modifying the puzzle such that instead of being in base 10 (ie. taking starting integers from 0 to 9), it would be interesting to see what the results were for a base n system, where n is anything greater than 2 (taking a base 2 system yields the trivially obvious solution of both x = 1 and y = 1, as the three other starting choices go to 0 immediately). This is relatively easy to do by just replacing the values of 10 in the above code by n and running the for loop from i = 1 to n*n-1. One can then look at the results of this and see if some sort of pattern emerges which would allow one to pick the appropriate best starting digits for a given base n without having to resort to brute force methods. I have completed the modifications to my own program and run it for values from 2 to 6 without spotting any sort of discernable pattern. I do plan on doing some actual work this afternoon, so I have tabled this for now but might explore it in the future. If anyone decides to explore this themselves and comes up with some interesting ideas, feel free to send me your results.

Note: I made the mistake this time of not keeping an accessible list of those who solved the puzzle and sent me solutions. While I think it was just Wisefly and Scott, if my memory has failed me and I forgot someone, please send me an email or leave a disgruntled comment, and I will make the appropriate changes to this post.

Edit: Thanks to Paul's helpful comment, my pseudocode looks a little more readable now.

A Brief Introduction to Computational Neuroscience Paradigms

Within computational neuroscience there seem to be two main theoretical paradigms. In the first, the brain is viewed as an elaborate and nested control system. This branch of investigation tends to use many of the same mathematical models as those used in the engineering discipline of control, albeit with an eye on the biological feasibility and possible neuronal configurations necessary for attaining such a control system. In the second, the brain is viewed as a dynamical system on the edge of chaos, and thus utilizes the mathematical tools found in dynamical system analysis. I have to admit that the latter of these two paradigms I am rather fuzzy on, despite having taken (and done rather well in) a course on Chaos, Fractals, and Dynamics. I am not sure if my inability to fathom what a 'dynamical system on the verge of chaos' means is due to a lack of intellectual capacity on my part or a lack of substance underlying the fancy terms being thrown around on the part of those championing the dynamical system interpretation. My guess is that the two paradigms are not as entirely exclusive as some claim them to be, but I think I will have to gain a better understanding of the application of dynamics to physiology before I can be sure. In the meantime, the control systems approach speaks quite clearly to the (former) engineer in me, and I find the control theory approach rather appealing. It is simple, elegant, and powerful.

Before I continue in this vein, however, I should mention a brief caveat. There is a third branch of thought which I have not included in this description known as machine learning. While it could also be argued to be a paradigm of computational neuroscience (or at least my interpretation of what computational neuroscience ought to be), I have not included it in this discussion because, to me, it is much more a branch of traditional approaches to artificial intelligence. Machine learning tends to focus more on function modeling through stochastic methods. While this provides many powerful tools (some of which are even utilized within the control systems approach), there is a lack of emphasis on physiological feasibility which might provide for a general theory of intelligence. Of course, I think many of the mathematical tricks used in machine learning (like principle components analysis (PCA)) will likely have neuronal correlates found in which our brains somehow provide a system to achieve similar results, machine learning does not tend to be devoted to uncovering methods of cognition as its primary goal.

Now that I have rambled about machine learning, I shall return to control theory. A control system is essentially any system designed to control a variable through time. The actual form the control system takes can be quite varied, including electronic control systems, mechanical ones, and, as I surmise our brains might be, electrochemical. They usually utilize some form of feedback (most often negative), since an open control system (as those without feedback are called) are not really much good at controlling anything. However, I will go into more detail about control theory in another post. This post was simply meant to introduce the idea of the different paradigms, as well as the fact that I am currently more focused on control theory.

Scientist Appreciation: Alan Turing

I had my Computational Complexity and Computability course tonight, and on the way home while slogging through the snow I wondered how I could work a post around the rather fascinating course material. Then I realised it gave me a perfect excuse to resurrect one of my favourite series on this blog which sadly fell the wayside: Scientist Appreciation! So, since he is so central to the subject of computability, this installment of Scientist Appreciation is devoted to Alan Turing.

Alan Turing had an unfortunately short life, but prior to his untimely death at the age of 41 he completed works and earned prestige which would make most academics inwardly weep with envy. His work helped form the theoretical foundation of computer science while he also goes down in engineering history as helping to construct one of the first true computers. Additionally, he gained popular fame as a code breaker during World War II working to counter the infamous Enigma machine as well as having his name become widely known in the realm of both artificial intelligence and science fiction through his proposition of the Turing Test for intelligence. While he is probably more popularly famous for his cryptography and the Turing Test, the rest of this post will focus on his theoretical framing of the notion of computability.

The true power (as well as the beauty and frustration) of mathematics is its elegant rigour and formal set of rules. If you truly want to know the properties of something, find a way to frame it mathematically and probe the results. Thus, when people were trying to understand the concept of an algorithm and determine just what sort of problems were computable, Turing created the eponymous concept of the Turing Machine (TM for short). In its regular formulation, a TM can be envisioned as an assembly line with a computational head positioned above a sheet of some sort (paper, perhaps) which can be both read and written to by the head. This sheet extends to infinity to the right, but has an ending to the left (from which the input is written). In each computational step, the head reads in an input from one position on the sheet, changes its internal state, has the option of writing over the current sheet's position, and then moves either to the left or the right (if it tries to move left in the initial position it stays where it is). This might sound like an awkward and plodding kind of computational machine to have, but there are some really fascinating things which can be shown about them. I don't know if there is any interest, so I won't go into detail now, but if any of my readers want me to give examples of some interesting problems with TMs let me know in the comments (or send me an email, if you have my email address). The thing is, I think I might just enjoy this because it is the kind of mathematics that comes the most naturally to me (as naturally as I think any university level math can come to a non-genius). Even if no one cares, I might not be able to restrain myself after I talk about Church in the next Scientist Appreciation and tie his work in with Turing's.

Anyway, my laptop is really acting up tonight, so I'm going to end this post here and hope my computer doesn't die (it also means I haven't proof-read this, so I hope it isn't too abysmal. Of course, I could always save as a draft and publish tomorrow, but what would be the fun in that?). In conclusion, Alan Turing made an amazing account of himself for his short life, and his early death was a tragedy for mathematics and computer science.

A Century of Posts

This is my one hundredth published post, so I thought I would commemorate the occasion by talking about why one hundred is such a special number. The specialness of 100 is primarily rooted in our 10-based numerical system. Basically, 100 is nice because it is a large, uncomplicated number but not unmanageably large. It is also 10 x 10, making it a perfect square. However, we are so used to thinking in base-10 that we forget how much it colours our thinking of numbers. I suppose, to be entirely responsible, I should start with a description of what a base-n system of numbers is.

Any number which we can write as a decimal can be written as an additive sequence. I briefly covered this in my post on the Cantor Set, but I will repeat myself here to refresh your memories (also, please note that I will now use * for multiplication rather than x, simply because it is what I more used to writing on the computer). For example, the number 15.34 = 1*10¹ + 5*10⁰ + 3*10^-1 + 4*10^-2. The base of your system is whatever number is being raised to the exponent in the expanded representation of the number. There are some other base systems that receive widespread use, the most famous and popular being the binary system (base-2). When looking at the Cantor Set, we used the ternary system (base-3), and in many computer science problems it is useful to use base-8 or base-16 (base-16 gets somewhat awkward to use since we need additional symbols beyond 0-9 to represent values up to 15. The letters A-F substitute in an unpleasant mixture of letters and numbers, which is why, despite my fondness for the number 16, I resent base-16 (also called hexadecimal)). Those, of course, are not the only possible systems, since one could potentially choose any base.

If we did not use base-10, then, 100 would cease to be such an exciting number. While it would still have the property of being a perfect square, it would no longer be any more special than 36 or 49 (though I think I would still like it more than 49 since it is even, and I have an irrational dislike of odd numbers). There would be other ramifications, however. 5 would no longer be as special as it is, since it would no longer be half of the base. If we used a base-6 system, 3 would take on many of the nice properties of 5, becoming even more popular than it already is, and 5 would be relegated to the awkward position of 7 or 11 as an ungainly prime number. The reason the properties of numbers change based on the system one is working with is because of the tricks you learn to do mental math. If you are not working in a base-10 system, then multiplying by 10 no longer simply shifts things one position over and adds a zero. Instead, whatever the base of your system now does that. The entire numerical field in one's head must twist and contort to fit the new system.

The funny thing is, I have a really hard time picturing any of these ramifications, because my mind automatically works hard at translating things back into decimal. It is one of the reasons I find the binary system nicer to work with than the ternary system, since it is easier to mentally translate binary to decimal and thereby visualize what I am working with. Numbers have their properties in my head based on the decimal system, much like words have their meanings rooted very strongly in English. I might know some German words, but they are more like code words in which I have memorized their English translation rather than additional words with subtle connotations in their own right. Likewise, German grammar is an artificial system of rules that I must impose upon the sentences which I compose in my head in English. My Russian is much better, in that there are things I can successfully 'think in Russian' about, and I suppose that might happen if I were to exclusively operate in another numerical base for a while. I can even see that starting to happen with the ternary system and the Cantor Set, because I am perfectly happy to do the majority of my Cantor Set thinking in ternary. It just makes relating that to other areas of mathematics somewhat burdensome, because then I am stuck trying to mentally translate the entirely unwieldy ternary system to decimal.

Anyway, this isn't exactly the post I had envisioned to commemorate my 100th blog post, but I hope my meandering ramblings about numbers were at least vaguely interesting. The main point I was trying to make was that the appreciation for 100 that exists is mainly based on our convention of using a base-10 system rather than anything else, yet the fact that the decimal properties of numbers are a convention goes largely unacknowledged.

The Mathie Difference

I told my girlfriend the following joke the other day:

"An infinite number of mathematicians walks into a bar. The first one orders a beer. The second one orders half a beer. The third one orders a quarter of a beer. It continues that way until the bartender interrupts to say, "You are all a bunch of idiots," and pours two beers."

While she greatly enjoyed it, her response was, "You know, when I tell that joke I am going to specify at the beginning that it is a countably infinite number of mathematicians, just to avoid any initial confusion."

The thought never even occurred to me. I guess my brain still hasn't fully registered that there is a difference between countable and uncountable infinity. Sigh.

Understanding Through Mathematical Concepts

My great aunt is a wonderful lady. A worldly intellectual in her own right, she can speak knowledgeably about Thucydides (which she read in the original Greek, not that wimpy translation stuff I read) and other literature of which I could not hope to compile an exhaustive list, as well as hold her own in a discussion of history and politics, especially if it involves Korea (where she was born and raised through much of her childhood before returning home to Canada). I am also a big fan of my great uncle, but since it was my aunt that made the comment I am going to discuss, I will have to wait for another day to sing his praises. I bring up my esteem for my aunt to put in context a comment she made one night when my girlfriend and I were at my aunt and uncle's for dinner, in which she stated something to the effect that she didn't understand how mathematics could hold any draw as a subject since it was such a dry and abstract thing. I think it was somewhat unfortunate for her that she made such a comment at a table with her husband (a retired aeronautical engineer), my girlfriend (who studies physics and mathematics), a Russian fellow who sails with my uncle and his wife (both who studied mathematics and computer science before moving to Canada), and me (a former aerospace student and now student of computational neuroscience), so she may have been a little unfairly outnumbered by those who had ties to mathematics. A great cry went up around the table and everyone tried to explain all at once that mathematics was, in fact, a wonderful thing. I don't think my aunt (a former graduate of the humanities) was trying to be confrontational at all, but I think she really was baffled (and, unfortunately, I don't think any of our answers really cleared anything up at the time, since the best we came up with was simply that it helps you to see the world differently without really giving any examples). I also don't think my aunt is alone. For many people, mathematics remains a dry and stuffy subject, handy for balancing the books and maybe work in research and design (but even then, there are a fair share of engineers who forsook mathematics upon achieving their degree and getting a job), but beyond that they don't have a concept of it.

While I am no mathematician, I still enjoy mathematics and dabble in it in my studies. I will therefore endeavour to give an example of how mathematical concepts can help explain aspects of the world using a personal insight about another subject that also commonly baffles people: speciation in evolutionary biology. Among critics of evolution, one of the commonly fallacious argument given is, "if evolution is true, why doesn't a dog give birth to a cat?" (or some other ridiculous combination). While that is probably the most ridiculous formulation of the argument, the basic idea that trips people up is understanding how one species can evolve into another. This lack of understanding often leads to the lamentable "middle of the road" half-cocked compromise in which a person accepts "microevolution" while claiming that he still doesn't believe in "macroevolution". To give some insight into how speciation works, at least from a conceptual standpoint, I turn to probability and calculus.

Take a circle with a spinning dial mounted in the middle. If you mark a spot on the circle (say the spot corresponding with '12' on a clock face) as the 0 mark, then you can spin the dial and it will land with some anticlockwise angle from 0 to 360 degrees. Since there are an infinite number of points on the circle, however, if you take your measurement to an arbitrary level of exactness (landing at 10.0000000000001 is different from landing at 10 exactly), the probability of landing at any distinct spot is essentially 0. The only way to obtain a non-zero probability is to talk about a range of possible angles. The probability is then simply the length of that range divided by 360 (thus, having the dial land within the first 90 degrees has a probability of 90/360 = 1/4). Thus, the circle can be divided into regions, each one representing a range of possible angles and thus having a non-zero probability. However, at the borders we see that which region we are in becomes a harsh cut-off over a seemingly negligeable difference. For example, if we divide our circle into four regions of equal size (each representing 90 degree increments), 89.99999999... would fall into region 1 while 90.0000000...001 would fall into region 2, despite an arbitrarily small difference between the two of them. Take the idea of that circle and now morph it in your head to represent an evolutionary lineage. The population of organisms at each moment in time represents one single location on the circle. A region represents a species, and thus a species is said to evolve into another if its region precedes the other. But remember that the demarcation line of our regions was essentially an arbitrary cutoff, a boundary imposed to provide meaning to the system. There is no drastic change in the dial's position when we go from region 1 to region 2, but rather the change can be as infinitesimally small as we want. Likewise, the change from species A to species B is not some drastic, single moment of monumental change such as a dog giving birth to a cat, but is rather a collection of tiny bumps in the dial position as it gradually creeps along the circle going from region 1 to region 2. However, when one compares the dial position from somewhere near the middle of each region, it looks to be very far apart.

This is no lofty or profoundly insightful thing I have come up with. I also recognize that I may have taken some liberties with the specific terms and workings of both mathematics and evolutionary biology, so for anyone who is actually in those fields and upset with me, I apologize (and you have full permission to admonish me in the comments). However, it is something that I have discovered a surprising number of people never really put together on their own. The concept of infinitesimal steps from calculus is a profound thing, and with it many other concepts in the world can be illuminated more fully. That, to me, is how mathematics is not dry or dull. Its concepts are wide reaching, elegant, and profound. If a person understands mathematics, there is a huge variety of subjects that suddenly become easily grasped.

The Middle-Thirds Cantor Set

I am not a mathematician. Sometimes I greatly wish I were, but that is not really the point here. Mathematics can still be really fun to think about even for non-mathies like me. Most people find such a statement a little ludicrous, but I am going to attempt to elucidate its merit with an example: the middle-thirds Cantor set.

The Cantor set is created in the following manner:

Take a number line from 0 to 1:

0___________________________1

Remove the middle third:

0_________1/3 ... 2/3_________1

Then do the same thing for the remaining sections:

0___1/9 ... 2/9___1/3 ... 2/3___7/9 ... 8/9___1

And continue in that manner, removing the middle of all sections after each step. After doing this an infinite number of times, all the points that remain will form the Cantor set. What is fascinating about this set is that there is an uncountably infinite number of points remaining in the Cantor set, but at the same time the amount removed, when totaled all together, equals 1.

To get the total amount removed, one simply needs to notice the following:

In the first step, 1/3 is removed. In the next, 2/9. In the third, 4/27. In fact, it is not hard to see that in the ith step, the amount removed is 2^i-1/3ⁱ. The total amount removed is thus the summation over i from 1 to infinity of 2^i-1/3ⁱ, which can be rewritten as the summation over i from 0 to infinity of (1/3)(2ⁱ/3ⁱ), which is equal to (1/3)(1/(1-2/3)) = 1. Thus, the entire line is removed, but at the same time an uncountably infinite number of points remain (which I will endeavour to show next).

To show that an uncountably infinite number of points remain, let me first switch from using a decimal system of numbering to a ternary system. Ternary numbers basically use base 3 instead of base 10. For example, if one takes the number 0.467 (written in normal decimal notation), it could equivalently be written as (4/10) + (6/10²) + (7/10³). Similarly, a number written in ternary notation as 0.102 would be equivalent to (1/3) + (0/3²) + (2/3³). When writing numbers from 0 to 1 on the number line with ternary notation, only numerals 0, 1, and 2 are used after the decimal point. Visualizing this geometrically, we can see that for a number 0.x₁x₂..., if x₁ is 0, the number must fall somewhere in the first third of the number line (if it is 1 it falls in the middle third, and if it is 2 it falls in the final third). Similarly, if x₂ is 0 it falls in the first third of the subsection denoted by x₁, if it is 1 it falls in the middle third, and if it is 2 it falls in the upper third. To give an example, take 0.02...:

0_________|_________|_________1

The first digit is 0, which means it must fall in the first third of our number line:

0___|___|___1/3

The second digit is 2, meaning it must fall within the upper third of this section of the number line:

2/9_|_|_1/3

If I had written more digits to the number, we would be able to further hone in on the region of the number line upon which it exists. However, hopefully the example is enough to demonstrate that, if one recalls that we remove the middle third of all sections of our number line, that any number that contains a 1 at any point will be removed. Thus, the Cantor set is made up of all numbers that can be written as 0.x₁x₂... where all x's are 0 or 2. Since one can have an infinite number of decimal points, there must necessarily be an infinite number of elements in the Cantor set. However, that does not mean there are an uncountably infinite number of elements. That last bit requires one more quick proof:

Assume that there is a countable number of members of the Cantor set and we write them down in the following manner (note, the order I am writing them in is completely arbitrary, since the only necessary thing is that they can all be written together to form a large matrix):

0.0202022...
0.2202002...
0.2002000...
0.0200222...
.
.
.
and so on

Then, form a number in the following manner: take the first element of the first number in our matrix and reverse it (0 becomes 2, 2 becomes 0). That becomes the first element of our new number. The second element is likewise the reverse of the second element of the second number, and so on for every number in our set. We thus have formed a new number that is without 1s (so will be in our set), but which necessarily is a novel value because it has at least one digit that is different from every other number, which thereby contradicts the initial assumption that we could enumerate every member of the Cantor set.

Anyway, I just thought that the Cantor set was very interesting. The seemingly contradictory idea that you could remove chunks of a segment of the number line totaling in length to the entire segment, but still leave behind an uncountably infinite number of points is fun to knock about in ones head. I really should stop procrastinating, though, and get back to my work...

Chaos

I just read one of the most enjoyable opening lines of a preface I think I have ever read in a textbook:

"Popular treatments of chaos, fractals, and dynamical systems let the public know there is a party but provide no map to the festivities. Advanced texts assume their readers are already part of the club."

It just struck me as clever. I have only the vaguest notion of the mathematics of dynamical systems, but I will endeavour to change that over the next little while. Luckily, I have this wonderful sounding textbook (available online here), so everyone can join me at the mathematical party.