# The bad guys die at the end

I was wondering whether anyone has any recommendations for books about getting/doing a PhD. I am now reading The Unwritten Rules of PhD Research and it is very good, so I’d happily recommend it – it is one of those books that helps you see the underlying order in what appears to be the chaos going on around you.

For my domain of study Writing for Computer Science: The Art of effective Communication is also essential reading.

# How can I lose that final stone?

The graph on this page shows the moving fortnightly average of my weight (in pounds – human weight will be one of the last things to go metric in Britain) since the middle of February.

I think the graph shows I am still losing weight from my gym-five-times-a-week approach, but it has become much harder than before (in fact the rate of decrease in February was still a fair bit lower than in 2012).

So, how can I fix this? Serious, evidence-backed replies only please!

I am not particularly interested in hearing about diets either.

The February weight loss started when I changed my routine in the gym – essentially doing a much higher number of repetitions on the machines (with a lower weight) – I usually do 45 – 60 minutes of cardio followed by 15 – 30 of strength.

I have kept that (newer) regime but, as you can see, it has been of limited effectiveness.

# What is this “complexity” of which you speak?

My review of an excellent companion volume to “Godel, Escher, Bach”

# A cynical thought

I am now reading up on supercomputer operating systems – part of the literature review for the qualifying dissertation of my PhD and so, naturally enough, took a peak at the new TOP500 list of supercomputers – topped by by the Chinese National University of Defense Technology’s TianHe-2 (I have just been reading of its predecessor, the TianHe-1A).

But do we really believe a list that doesn’t seem to contain any computers operated by anyone’s communications intelligence agencies?

After all, Station X’s key breakthroughs on Engima came via parallel computations!

# The proof that frightened Pythagoras

I have been meaning to do this for a while …

Pythagoras was said to be shocked by the proof that $\sqrt 2$ is an irrational number (i.e., that it cannot be represented as a ratio of two whole numbers). The proof (by contradiction) is a simple one.

If $\sqrt 2$ is rational then $\sqrt 2 = \frac{a}{b}$ and $2 = \frac{a^2}{b^2}$ where $a$ and $b$ are the smallest nominator and denominator possible, i.e, in the lowest terms.

Hence $a^2 = 2b^2$ and so $a$ must be even (as two odd numbers multiplied always give an odd number – let $l = 2x$ and $m = 2y$ be even numbers then $(l + 1)(m + 1) = lm + l + m + 1$). Hence $a = 2k$.

But we also have $4k^2 = a^2$ and thus $4k^2 = 2b^2$ and $b^2 = 2k^2$ and so $b$ is even.

So we have $a$ and $b$ sharing a common factor of 2, so they cannot be the nominator and denominator of the fraction in the lowest terms.

But if $a$ and $b$ are both even then they share a common factor of 2 and $\frac{a}{b} = \frac{2k}{2p} = \frac{k}{p}$: implying that $a = k$ and $a = 2k$, an obvious contradiction: hence $\sqrt 2$ cannot be a rational.

Update: I have made the final step of this shorter and clearer.

Further update: I have been told (see comments below) I would have been better sticking with a clearer version of the original ending ie., we state that $\frac{a}{b}$ are the lowest terms. Then, plainly as they have a factor in common (2) they cannot be the lowest terms and so we have a contradiction. Would be great if someone could explain why we cannot use the $a = 2k = k$ contradiction.

And another update: Should have stuck with the original explanation – which I have now restored in a hopefully clearer way. The comments below are really interesting and from serious mathematicians, so please have a look!

# How to be a successful PhD student

Well, there is a bit of presumption going on here. I am not a successful PhD student as ultimately that is a binary thing: a successful PhD student is one who gets the doctorate. I have not even begun an experiment yet.

But I do feel like I am making progress like never before because of the soft-backed notebooks in my life.

To explain further I will use an analogy. When you are expecting your first child everyone says “it will change your life”. It is said so frequently it becomes boring and you think, every time you are told it – “as if I didn’t know”.

But when you have your first child you realise very quickly  just why everyone said that same thing to you – because it will change your life. They didn’t tell you enough of how deep and fundamental that change is.

So when you start your PhD everyone says “takes notes as you go along” and you think “of course”. But you don’t do it properly. You mix your notes up with everything else in this or that notebook and then months later you come back and think “what does that paper say again – these notes are a mess”.

And then you realise that you must have the notebook with you every time you read a paper and that notebook is your most important possession. And then you start to get it right…

# Incompleteness in the natural world

A post inspired by Godel, Escher, Bach, Complexity: A Guided Tour, an article in this week’s New Scientist about the clash between general relativity and quantum mechanics and personal humiliation.

The everyday incompleteness: This is the personal humiliation bit. For the first time ever I went on a “Parkrun” today – the 5km Finsbury Park run, but I dropped out after 2.5km 2km – at the top of a hill and about 250 metres from my front door – I simply thought this is meant to be a leisure activity and I am not enjoying it one little bit. I can offer some excuses – it was really the first time ever I had run outdoors and so it was a bit silly to try a semi-competitive environment for that, I had not warmed up properly and so the first 500 metres were about simply getting breathing and limbs in co-ordination – mais qui s’excuse, s’accuse.

But the sense of incompleteness I want to write about here is not that everyday incompleteness, but a more fundamental one – our inability to fully describe the universe, or rather, a necessary fuzziness in our description.

Let’s begin with three great mathematical or scientific discoveries:

The diagonalisation method and the “incompleteness” of the real numbers: In 1891 Georg Cantor published one of the most beautiful, important and accessible arguments in number theory – through his diagonalisation argument, that proved that the infinity of the real numbers was qualitatively different from and greater than the infinity of the counting numbers.

The infinity of the counting numbers is just what it sounds like – start at one and keep going and you go on infinitely. This is the smallest infinity – called aleph null ($\aleph_0$).

Real numbers include the irrationals – those which cannot be expressed as fractions of counting numbers (Pythagoras shocked himself by discovering that $\sqrt 2$ was such a number). So the reals are all the numbers along a counting line – every single infinitesimal point along that line.

Few would disagree that there are, say, an infinite number of points between 0 and 1 on such a line. But Cantor showed that the number was uncountably infinite – i.e., we cannot just start counting from the first point and keep going. Here’s a brief proof…

Imagine we start to list all the points between 0 and 1 (in binary) – and we number each point, so…

1 is 0.00000000…..
2 is 0.100000000…..
3 is 0.010000000……
4 is 0.0010000000….
n is 0.{n – 2 0s}1{000……}

You can see this can go on for an infinitely countable number of times….

and so on. Now we decide to ‘flip’ the o or 1 at the index number, so we get:

1 is 0.1000000….
2 is 0.1100000….
3 is 0.0110000….
4 is 0.00110000….

And so on. But although we have already used up all the counting numbers we are now generating new numbers which we have not been able to count – this means we have more than $\aleph_0$ numbers in the reals, surely? But you argue, let’s just interleave these new numbers into our list like so….

1 is 0.0000000….
2 is 0.1000000…..
3 is 0.0100000….
4 is 0.1100000….
5 is 0.0010000….
6 is 0.0110000….

And so on. This is just another countably infinite set you argue. But, Cantor responds, do the ‘diagonalisation’ trick again and you get…

1 is 0.100000…..
2 is 0.110000….
3 is 0.0110000….
4 is 0.1101000…
5 is 0.00101000…
6 is 0.0110010….

And again we have new numbers, busting the countability of the set. And the point is this: no matter how many times you add the new numbers produced by diagonalisation into your counting list, diagonalisation will produce numbers you have not yet accounted for. From set theory you can show that while the counting numbers are of order (analogous to size) $\aleph_0$, the reals are of order $2^{\aleph_0}$, a far far bigger number – literally an uncountably bigger number.

Gödel’s Incompleteness Theorems: These are not amenable to a blog post length demonstration, but amount to this – we can state mathematical statements we know to be true but we cannot design a complete proof system that incorporates them – or we can state mathematical truths but we cannot build a self-contained system that proves they are true. The analogy with diagonalisation is that we know how to write out any real number between 0 and 1, but we cannot design a system (such as a computer program) that will write them all out – we have to keep ‘breaking’ the system by diagonalising it to find the missing numbers our rules will not generate for us. Gödel’s demonstration of this in 1931 was profoundly shocking to mathematicians as it appeared to many of them to completely undermine the very purpose of maths.

Turing’s Halting Problem: Very closely related to both Gödel’s incompleteness theorems and Cantor’s diagonalisation proof is Alan Turing’s formulation of the ‘halting problem’. Turing proposed a basic model of a computer – what we now refer to as a Turing machine – as an infinite paper tape and a reader (of the tape) and writer (to the tape). The tape’s contents can be interpreted as instructions to move, to write to the tape or to change the machine’s internal state (and that state can determine how the instructions are interpreted).

Now such a machine can easily be made of go into an infinite loop e.g.,:

• The machine begins in the ‘start’ state and reads the tape.  If it reads a 0 or 1 it moves to the right and changes its state to ‘even’.
• If the machine is in the state ‘even’ it reads the tape. If it reads a 0 or 1 it moves to the left and changes its state to ‘start’

You can see that if the tape is marked with two 0s or two 1s or any combination of 0 or 1 in the first two places the machine will loop for ever.

The halting problem is this – can we design a Turing machine that will tell us if a given machine and its instructions will fall into an infinite loop? Turing proved  we cannot without having to discuss any particular methodology … here’s my attempt to recreate his proof:

We can model any other Turing machine though a set of instructions on the tape, so if we have machine $T$ we can have have it model machine $M$ with instructions $I$: i.e., $T(M, I)$

Let us say $T$ can tell whether $M$ will halt or loop forever with instructions $I$ – we don’t need to understand how it does it, just suppose that it does. So if $(M, I)$ will halt $T$ writes ‘yes’, otherwise it writes ‘no’.

Now let us design another machine $T^\prime$ that takes $T(M,I)$ its input but here $T^\prime$ loops forever if $T$ writes ‘yes’ and halts if $T$ writes ‘no’.

Then we have:

$M(I)$ halts or loops – $T(M, I)$ halts – $T^\prime$ loops forever.

But what if we feed $T^\prime$ the input of $T^\prime(T(M, I)$?

$M(I)$ halts or loops – $T(M, I)$ halts – $T^\prime(T(M,I))$ loops forever – $T^\prime(T^\prime(T(M,I)))$ – ??

Because if the second $T^\prime(T^\prime(T(M,I)))$ halted then that would imply that the first had halted – but it is meant to loop forever, and so on…

As with Gödel we have reached a contradiction and so we cannot go further and must conclude that we cannot build a Turing machine (computer) that can solve the halting problem.

Quantum mechanics: The classic, Copenhagen, formulation of quantum mechanics states that the uncertainty of the theory collapses when we observe the world, but the “quantum worlds” theory suggests that actually the various outcomes do take place and we are just experiencing one of them at any given time. The experimental backup for the many worlds theory comes from quantum ‘double-slit’ experiments which suggest particles leave traces of their multiple states in every ‘world’.

What intrigues me: What if our limiting theories – the halting problem, Gödel’s incompleteness theorem, the uncountable infinite, were actually the equivalents of the Copenhagen formulation and, in fact, maths was also a “many world” domain where the incompleteness of the theories was actually the deeper reality – in other words the Turing machine can both loop forever and halt? This is probably, almost certainly, a very naïve analogy between the different theories but, lying in the bath and contemplating my humiliation via incompleteness this morning, it struck me as worth exploring at least.

# Gödel, Escher, Bach

Finally finished Godel, Escher, Bach – click the link above to read my review.

# Apologies

I posted an article in which I identified a Wikipedia user – UK2013 – as vandalising a page. They didn’t. The page was vandalised, but I named the wrong user. Apologies for that. Rather than correct the article I have just deleted it. I won’t be publishing an updated version.