(original) (raw)

An example of Exploratory Programming

Russell's Paradox and the Barber

This is part of the introduction to Thinky Programming here: http://www.cs.bham.ac.uk/research/projects/poplog/examples

Russell's paradox (The set of all sets that do not contain themselves, must contain itself if it doesn't, and cannot contain itself if it does - so it does and it does not...) is connected with the Barber problem (finding the barber who shaves all and only the shavers who do not shave themselves).

The barber problem could easily be turned into a game to stimulate young kids to think: using any action that can be performed on someone else or on oneself. E.g. everyone gets a sticky label to stick on someone else or on themselves.

The class is divided into two groups each with the problem of working out how each member can decide to stick his/her label on someone else, or on him/her self. The winning group is the first group that manages to do that in such a way that one person in the group satisfies the barber condition (sticks a label on all and only those in the group who do not stick the label on themselves).

How long will it take kids of age X to discover that there can be no winning group, and work out why not? (X = 6, 7, 8, ....17?)

Then if they have access to a programming language (e.g. lisp, scheme, pop11, ...) that treats functions as first class objects (e.g. they can be passed as parameters) they can explore the consequences of trying to define a predicate that takes a procedure as input and returns true for all and only those procedures that return true when applied to themselves.

In Pop11 (see http://en.wikipedia.org/wiki/POP-11)

define barber(f);

    not(f(f))

enddefine;

Test it:

barber(isnumber) =>
** 

barber(isword) =>
** 

barber(isprocedure) =>
** 

barber(barber) =>
;;; MISHAP - rle: RECURSION LIMIT (pop_callstack_lim) EXCEEDED

(what difference does tail recursion optimisation make?).

Learners who have been through those exercises will have their minds stretched in ways that help to prepare them for study of the deep ideas of Turing and others, and modern variants.

They may, as a result, be better able to understand some of the deep problems of producing provably reliable systems, for example.

QUESTION: What happens if the 'not' is removed from the definition of procedure barber?

Can there be a barber who shaves all and only those barbers who do shave themselves?

What about a set that contains all and only those sets that contain themselves?

[References to be added]