Searle’s wall, computation and representation

Reading a bit more of Brain Cantwell Smith’s “On the Origin of Objects”  and he refers (p.30-31) to Searle‘s wall that, according to Searle, can be interpreted as implementing a word processor.  This all hinges on predicates introduced by Goodman such as ‘grue’, meaning “green is examined before time t or blue if examined after”:

grue(x) = if ( now() < t ) green(x)
          else blue(x)

The problem is that an emerald apparently changes state from grue to not grue at time t, without any work being done.  Searle’s wall is just an extrapolation of this so that you can interpret the state of the wall at a time to be something arbitrarily complex, but without it ever changing at all.

This issue of the fundamental nature of computation has long seemed to me the ‘black hole’ at the heart of our discipline (I’ve alluded to this before in “What is Computing?“).  Arguably we don’t understand information much either, but at least we can measure it – we have a unit, the bit; but with computation we cannot even measure except without reference to specific implementation architecture whether Turing machine or Intel Core.  Common sense (or at least programmer’s common sense) tells us that any given computational device has only so much computational ‘power’ and that any problem has a minimum amount of computational effort needed to solve it, but we find it hard to quantify precisely.  However,  by Searle’s argument we can do arbitrary amounts of computation with a brick wall.

For me, a defining moment came about 10 years ago, I recall I was in Loughbrough for an examiner’s meeting and clearly looking through MSc scripts had lost it’s thrill as I was daydreaming about computation (as one does).  I was thinking about the relationship between computation and representation and in particular the fast (I think fastest) way to do multiplication of very large numbers, the Schönhage–Strassen algorithm.

If you’ve not come across this, the algorithm hinges on the fact that multiplication is a form of convolution (sum of a[i] * b[n-i]) and a Fourier transform converts convolution into pointwise multiplication  (simply a[i] * b[i]). The algorithm looks something like:

1. represent numbers, a and b, in base B (for suitable B)
2. perform FFT in a and b to give af and bf
3. perform pointwise multiplication on af and bf to give cf
4. perform inverse FFT on cf to give cfi
5. tidy up cfi a but doing carries etc. to give c
6. c is the answer (a*b) in base B

In this the heart of the computation is the pointwise multiplication at step 3, this is what ‘makes it’ multiplication.  However, this is a particularly extreme case where the change of representation (steps 2 and 4) makes the computation easier. What had been a quadratic O(N2) convolution is now a linear O(N) number of pointwise multiplications (strictly O(n) where n = N/log(B) ). This change of representation is in fact so extreme, that now the ‘real work’ of the algorithm in step 3 takes significantly less time (O(n) multiplications) compared to the change in representation at steps 2 and 4 (FFT is O( n log(n) ) multiplications).

Forgetting the mathematics this means the majority of the computational time in doing this multiplication is taken up by the change of representation.

In fact, if the data had been presented for multiplication already in FFT form and result expected in FFT representation, then the computational ‘cost’ of multiplication would have been linear … or to be even more extreme if instead of ‘representing’ two numbers as a and b we instead ‘represent’ them as a*b and a/b, then multiplication is free.  In general, computation lies as much in the complexity of putting something into a representation as it is in the manipulation of it once it is represented.  Computation is change of representation.

In a letter to CACM in 1966 Knuth said1:

When a scientist conducts an experiment in which he is measuring the value of some quantity, we have four things present, each of which is often called “information”: (a) The true value of the quantity being measured; (b) the approximation to this true value that is actually obtained by the measuring device; (c) the representation of the value (b) in some formal language; and (d) the concepts learned by the scientist from his study of the measurements. It would seem that the word “data” would be most appropriately applied to (c), and the word “information” when used in a technical sense should be further qualified by stating what kind of information is meant.

In these terms problems are about information, whereas algorithms are operating on data … but the ‘cost’ of computation has to also include the cost of turning information into data and back again.

Back to Searle’s wall and the Goodman’s emerald.  The emerald ‘changes’ state from grue to not grue with no cost or work, but in order to ask the question “is this emerald grue?” the answer will involve computation (if (now()<t) …).  Similarly if we have rules like this, but so complicated that Searle’s wall ‘implements’ a word processor, that is fine, but in order to work out what is on the word processor ‘screen’ based on the observation of the (unchanging) wall, the computation involved in making that observation would be equivalent to running the word processor.

At a theoretical computation level this reminds us that when we look at the computation in a Turing machine, vs. an Intel processor or lambda calculus, we need to consider the costs of change of representations between them.  And at a practical level, we all know that 90% of the complexity of any program is in the I/O.

  1. Donald Knuth, “Algorithm and Program; Information and Data”, Letters to the editor. Commun. ACM 9, 9, Sep. 1966, 653-654. DOI= http://doi.acm.org/10.1145/365813.858374 [back]

What is Computing? The centrality of systemics

Recently I was in a meeting where the issue of ‘core’ computer science came up. One person listed a few areas, but then this was challenged by another member of the group who said (to be fair, partly in jest), that core computer science should certainly include computer architecture, but not the ‘human stuff’.

I felt a little like a teenager complete with T-shirt and iPod dropped into Jurassic Park arguments that I thought had been put to bed in the 1980s suddenly resurfacing – how do you explain this white thing that makes sounds from its earphones to a caveman wearing skins?

However, I also felt a certain sympathy as I often wonder about computer science as a whole; indeed it has its own arguments in the 1960s and ’70s as to whether it was a ‘discipline’ as opposed to just an application domain for maths or electronics, or just a tool for business. Maybe one of the clinchers was the theoretical foundations of computing in the work of Church and Turing … but strangely enough at Lancaster the closest to this, the course on algorithmic complexity, is taught by a HCI person!

One of my worries in computing is that these theoretical foundations are still weak, there is black hole in the theoretical centre of computer science1. However, these theoretical issues were certainly not what was bothering my colleague. To answer his challenge and my own worries about the discipline we really need to know – what is computing?

Continue reading

  1. This demands a discussion of its own, but the basic problem is that while Church and Turing gave us understanding of disembodied computation, we still do not have clear understanding of generic computation when embodied in devices in general only particular architectures. [back]

matterealities and the physical embodiment of code

Last Tuesday morning I had the pleasure of entertaining a group of attendees to the Matterealities workshop @ lancaster. Hans and I had organised a series of demos in the dept. during the morning (physiological gaming, Firefly (intelligent fairylights), VoodooIO, something to do with keyboards) … but as computer scientists are nocturnal the demos did not start until 10am, and so I got to talk with them for around an hour beforehand :-/

The people there included someone who studied people coding about DNA, someone interested in text, anthropologosts, artists and an ex-AI man. We talked about embodied computation1, the human body as part of computation, the physical nature of code, the role of the social and physical environment in computation … and briefly over lunch I even strayed onto the modeling of regret … but actually a little off topic.

Alan driving

physicality – Played a little with sticks and stones while talking about properties of physical objects: locality of effect, simplicity of state, proportionality and continuity of effect2.

physical interaction – Also talked about the DEPtH project and previous work with Masitah on natural interaction. Based on the piccie I may have acted out driving when talking about natural inverse actions

ubiquity of computation – I asked the question I often do “How many computers do you have in your house” … one person admitted to over 10 … and she meant real computers3. However, as soon as you count the computer in the TV and HiFi, the washing machine and microwave, central heating and sewing machine the count gets bigger and bigger. Then there is the number you carry with you: mobile phone, camera, USB memory stick, car keys (security codes), chips on credit cards.

FireFly on a Christmas treeHowever at the Firefly demo later in the morning they got to see what may be the greatest concentration of computers in the UK … and all on a Christmas Tree. Behind each tiny light (over 1000 of them) is a tiny computer, each as powerful as the first PC I owned allowing them to act together as a single three dimensional display.

embodiment of computation – Real computation always happens in the physical world: electrons zipping across circuit boards and transistors routing signals in silicon. For computation to happen the code (the instruction of what needs to happen) and the data (what it needs to happen with and to) need to be physically together.

The Turing Machine, Alan Turing’s thought experiment, is a lovely example of this. Traditionally the tape in the Turing machine is thought of as being dragged across a read-write head on the little machine itself.

However … if you were really to build one … the tape would get harder and harder to move as you used longer and longer tapes. In fact it makes much more sense to think of the little machine as moving over the tape … the Turing machine is really a touring machine (ouch!). Whichever way it goes, the machine that knows what to do and the tape that it must do it to are brought physically together4.

This is also of crucial importance in real computers and one of the major limits on fast computers is the length of the copper tracks on circuit boards – the data must come to the processor, and the longer the track the longer it takes … 10 cm of PCB is a long distance for an electron in a hurry.
Alanbrain as a computer – We talked about the way each age reinvents humanity in terms of its own technology: Pygmalion in stone, clockwork figures, pneumatic theories of the nervous system, steam robots, electricity in Shelley’s Frankenstein and now seeing all life through the lens of computation.

This withstanding … I did sort of mention the weird fact (or is it a factoid) that the human brain has similar memory capacity to the web5 … this is always a good point to start discussion 😉

While on the topic I did just sort of mention the socio-organisational Church-Turing hyphothesis … but that is another story

more … I recall counting the number of pairs of people and the number of seat orderings to see quadratic (n squared) and exponential effects, the importance of interpretation, why computers are more than and less than numbers, the Java Virtual Machine, and more, more, more, … it was very full hour

AlanLcoblo - artefactsAlan

  1. I just found notes I’d made for web page in embodied computation 5 years ago … so have put the notes online[back]
  2. see preface to Physicality 2006 proceedings[back]
  3. I just found an online survey on How many computers in your house[back]
  4. Yep I know that Universal Turing machine has the code on the tape, but there the ‘instructions’ to be executed are basically temporarily encoded into the UTM’s state while it zips off to the data part of the tape.[back]
  5. A. Dix (2005). the brain and the web – a quick backup in case of accidents. Interfaces, 65, pp. 6-7. Winter 2005.
    http://www.hcibook.com/alan/papers/brain-and-web-2005/[back]