Season 9 Episode 3

In this episode, Sergey demonstrates mathematics at the foundations of computer science, applied to a particular style of computing machine.

OOMC Season 9 Episode 3

Watch on YouTube

Further Reading

Halting Problem

We mentioned the Halting Problem briefly; this is the idea that you cannot have a computer program capable of always deciding whether or not programs eventually stop (or print a particular character, in Turing’s formulation).

I’d like to link you to a particular (rather elegant) idea for way to prove this, due to Christopher Strachey, which you can find here.

Christopher Strachey was a British computer scientist and the first director of the Programming Research Group in Oxford (then part of the Computing Laboratory, which is now the Department of Computer Science). He’s responsible for the following excellent quote;

“It has long been my personal view that the separation of practical and theoretical work is artificial and injurious. Much of the practical work done in computing, both in software and in hardware design, is unsound and clumsy because the people who do it have not any clear understanding of the fundamental design principles of their work. Most of the abstract mathematical and theoretical work is sterile because it has no point of contact with real computing. One of the central aims of the Programming Research Group as a teaching and research group has been to set up an atmosphere in which this separation cannot happen.”

 

Temporal Logic

The logic of time! Here’s an article from the Stanford Encyclopedia of Philosophy. (Warning: this webpage has over 15,000 words).

The idea of things happening eventually always or always eventually reminded me a bit of the behaviour of an operation called the logistic map. Here’s how you can try it at home; get a calculator and do the following:

  • Type a number between 0 and 1 and press equals
  • Type \( 2 \times \text{Ans} \times (1- \text{Ans}) \)
  • Press equals
  • Keep pressing equals

Describe the behaviour that you observe.

Now start again and repeat the experiment, but this time, use \(3.2 \times \text{Ans} \times (1- \text{Ans}) \) instead. Describe the behaviour that you observe.

Try other starting numbers, and try other values of \(k\) in the repeated calculation \(k \times \text{Ans} \times (1- \text{Ans}) \)  

Only once you think that you’ve seen everything there is to see, have a look at this page about the Logistic Map. (Warning: this webpage has over 15,000 words).

 

If/then

There was a question in chat about how the if/then symbol ⇒ works.

We might have a statement like "P ⇒ Q" which we read as "if P then Q", and where P and Q are themselves statements. Let’s say that P is "it’s Thursday" and Q is "I’ll watch OOMC today". The statements P and Q might or might not be true. We say that the statement "if P then Q" is true if either Q is true, or P is false. Here’s a truth table;

P

Q

if P then Q

T

T

T

T

F

F

F

T

T

F

F

T

Note that it’s OK for P to be false and Q to be true; I might watch OOMC on other days (via the recordings, over 90 of which are available to stream at any time at www.maths.ox.ac.uk/r/club). In fact, if P is false then anything goes (if it’s not Thursday then the statement "if it’s Thursday then I’ll watch OOMC today" doesn’t mean that I will or that I won’t watch OOMC today).

There’s an interactive NRICH activity about these implication symbols here.

Note that the double headed arrow ⇔ means “if and only if”, which is a different concept from “if”.

 

Cellular Automata

No introduction to the behaviour of computer systems would be complete without some links to information about cellular automata, and where better to link you to than Wolfram MathWorld? The elementary cellular automata are particularly approachable. These can be simulated on squared paper with a pencil; you might like to explore the behaviour of rule 30 for yourself.

The theme here is to take a system with simple rules and ask questions about the behaviour of that system over time. Both cellular automata and the calculator activity above demonstrate that even simple systems can have amazingly complex behaviour.

 

If you want to get in touch with us about any of the mathematics in the video or the further reading, feel free to email us on oomc [at] maths.ox.ac.uk.

Last updated on 31 Jan 2025, 3:15pm. Please contact us with feedback and comments about this page.