#computable numbers

[man-reading]

How A Gay Love Story Led To The Invention Of The Computer

How an adolescent gay love story changed the shape of the digital future:

The idea that led to the invention of the computer, an idea that Alan Turing put forward in his 1936 paper ‘Computable Numbers’, did not start with a mathematical puzzle. It started with a love story, and a gay love story at that.

Alan Turing became friends with Christopher Morcom in1928. Morcom was, in many ways, Turing’s first real peer. He was, like Turing, a mathematician and a scientist. “When they were together,” David Leavitt writes, “the boys were more likely to talk about relativity and the value of π – which Turing, in his spare time, had calculated to thirty-six decimal points – than about poetry. Despite their seemingly dry subject matter, these conversations hummed, at least for Turing, with poetic intensity.” It was an unrequited love, by all accounts, but it was no less significant for that.

Christopher Morcom changed Alan Turing. The distracted and somewhat lonely boy was no longer alone; now he had someone to look up to, and someone he wanted to impress. As a scientist, Morcom was careful. Turing, who was raw enthusiasm, unbound, was careless. Morcom taught him to be methodical, which is something his schooling had failed to do. There was a focus and a drive that had not been there before, and his schoolmasters, who had previously been dismayed at his work, were astonished by the change. As Turing later wrote, Morcom “had a great power in practical work of finding out just what was the best way of doing anything.”

In the early hours of February 7, 1930, Turing had a premonition of Morcom’s death. The abbey clock struck a quarter to three, and he looked out of the window and saw the setting moon, which he suddenly knew was a “goodbye to Morcom”. That same night Christopher Morcom was taken ill with tuberculosis, and on February 13 he died.

Turing was devastated. Yet on 16 Feb he wrote to his mother, “I feel sure that I shall meet Morcom again somewhere and that there will be some work for us to do together.” Turing’s writing about Morcom in the years following his death betrays all the hallmarks of adolescent love. “It never seems to have occurred to me to make other friends besides Morcom, he made everyone else seem so ordinary,” he wrote in a letter to Morcom’s mother. The loss fixed Morcom, and the very idea of love, in a romantic ideal; as Leavitt notes, there was no chance for this love to sour, and for reality to set in. “Perhaps as a result, he spent much of the rest of his short life seeking to replicate this great and unfulfilled love.” What is certain is that the death of his friend had a decisive effect on Turing’s creative mind, and he developed a mystical attitude toward Morcom, as well as toward death and the idea of the spirit.

In an essay titled ‘Nature of Spirit’, written in 1932 and sent to Christopher Morcom’s mother, Alan Turing started to explore the mystical ideas that had been working their way around his head in the years following Morcom’s death. “It used to be supposed in Science,” he began, “that if everything was known about the universe at any particular moment then we can predict what it will be all through the future.” The theory of relativity, and the unpredictability of atoms and electrons, had changed that. Yet what power does the will, the spirit, have over that unpredictability, he then asked, and what is the role of the body in this? “Personally I think that spirit is really eternally connected with matter but certainly not always by the same kind of body,” he concluded. “The body provides something for the spirit to look after and use.” The spirit, and the vessel that held the spirit, were to Turing’s mind separate and separable. This thinking had a profound impact on how he conceived the idea of the “universal machine”.

In ‘Computable Numbers’, the idea of a universal machine that Turing put forward separated the machine itself, i.e. the body, from the software that allowed the machine to function, i.e. the mind. It was from this revolutionary idea that the modern digital computer was born. His thinking about the nature of spirit in the wake of Morcom’s death, moreover, linked back to what he had been taught by the influential book Natural Wonders Every Child Should Know, by Edwin Tenney Brewster, which had been given to him when he was 10.

“For, of course, the body is a machine. It is a vastly complex machine, many, many times more complicated than any machine ever made with hands; but still after all a machine. It has been likened to a steam engine. But that was before we knew as much about the way it works as we do now. It really is a gas engine, like the engine of automobile, a motor boat, or a flying machine.”

After the loss for Morcom, Turing started to puzzle out the nature of mind and spirit, and its relationship with the physical machine, the body. It was this creative leap that drove his career. Questions of free will and determinism, and the extent to which the mind controls the body, are at the core of ‘Computable Numbers’.

The most complex and difficult ideas of Alan Turing, from the universal machine to artificial intelligence, which he explored when he asked “can machines think?” in his 1950 paper ‘Computing Machinery and Intelligence’, link back to this love story and its consequences. Alan Turing believed that the spirit could live on, and he proved that yes, it could. In the end, Morcom’s spirit lived on not in his body but in a wholly different form, in the work of Alan Turing.

[tablekat]

A "Ring" over the Computable Numbers

In my last post I explained how computable numbers could be represented as a computable infinite list of rational numbers, and I gave pi as an example.

Now, I'm going to define a few more operations, enough to define a ring over the computable numbers. Or rather I'm going to define ring operations on computable numbers. Unfortunately, it's not possible to define equality on computable numbers (because verifying equality would take an infinite amount of steps). Because of this, saying things like "a + (-a) = 0" or "(a ⋅ b) ⋅ c = a ⋅ (b ⋅ c)" is meaningless, because you can never be sure anything really equals anything in computable numbers. (If you'd like more illustration, imagine 2 sequences a = [1,1,1,1,1,...] and b = [1,1,1,1,...]. How do you know a = b? Even after checking n elements, what if there's a 2 somewhere after? You can never be sure unless you check all infinity elements of both of them)

First, let's think of computable numbers as computable infinite lists of rational numbers:

import Data.Ratio type Computable = [Rational]

Then, it's fairly straightforward to define addition, and show it works with an example: 

add :: Computable -> Computable -> Computable add x y = zipWith (+) x y  -- a = [3, 3.1, 3.14, 3.141, 3.1415, ...] → π   -- b = [1,1,1,1,1,...] → 1  -- a + b = [4, 4.1, 4.14, 4.141, 4.1415, ...] → π + 1

To get additive inverses, we can define negation:

negate :: Computable -> Computable negate x = map negate x  -- b = [2, 2, 2, ...] → 2  -- negate b = [negate 2, negate 2, negate 2, ...] = [-2, -2, -2, ...]  -- and [-2, -2, -2, ...] → -2  -- and to check, -2 = negate 2

Multiplication can be defined in the same way as addition (but because we're only considering ring operations, we don't need multiplicative inverses)

mult :: Computable -> Computable -> Computable mult x y = zipWith (*) x y

While we're at it, we can define the rest of the operations from the Haskell Num type class

fromInteger :: Integer -> Computable fromInteger a = repeat (fromInteger a)  -- fromInteger 3 = [3, 3, 3, 3, ...]

If that definition is a little boring, we can define something a bit more interesting. First note that "map (1/) [1..]" is the same as the sequence \\( \{1, \frac{1}{2}, \frac{1}{3}, ... \frac{1}{n}, ...\} \\), which converges to 0. Then, we can map the integer \\(x\\) to \\(\{x + 1, x + \frac{1}{2}, x + \frac{1}{3}, ... x + \frac{1}{n}, ...\} \\) which still converges to x!

funFromInteger :: Integer -> Computable funFromInteger x = map (+ fromInteger x) $ map (1/) [1..]

Continuing definitions from Num, 

abs :: Computable -> Computable abs x = map abs x signum :: Computable -> Computable signum x = map signum x

I'd like to mention that at first I was a bit worried about how to define signum on computable numbers. First, if we note that a rational sequence converges to a positive number, then signum applied to each rational number in that sequence will converge to positive 1. For example, note that

let a = [-3, -2, -1, 0, 1, 2, 2, 2, 2, ...] → 2 signum a = [-1, -1, -1, 0, 1, 1, 1, 1, 1...] → 1 (signum 2) = 1

The trouble comes when we try to take signum of a sequence that converges to 0. Consider the rational sequence \\( a_n = \frac{(-1)^n}{n} \\). This sequence, of course, converges to 0. However, signum of this sequence will always jump back and forth between -1 and 1, but never converge! However, this isn't a problem if the sequence doesn't converge to zero. This is actually important, because if we knew signum of every sequence that converges to 0 is 0, then it means we could test equality in the computable numbers, which we already know isn't true! In other words, we can't know if "a = b", but that also means we can't know if "a - b = 0", and the latter happens if and only if "signum(a - b) = 0".

For most of the definitions above, if you just copy and paste into Haskell, it'll complain that "abs", "negate", etc. are already defined in the Prelude. We can get around this by just making a Num typeclass instance for lists of numbers:

instance (Num a) => Num [a] where     xs + ys = zipWith (+) xs ys     xs * ys = zipWith (*) xs ys     negate xs = map negate xs     fromInteger a = repeat (fromInteger a)     abs xs = map abs xs     signum xs = map signum xs

Then, if you want to play around with the numbers in GHCi, use take to just see the first few elements of each infinite list

*Main Data.Ratio> take 5 $ funFromInteger 3 [4 % 1,7 % 2,10 % 3,13 % 4,16 % 5] *Main Data.Ratio> map fromRational it :: [Float] [4.0,3.5,3.3333333,3.25,3.2]