DEPARTMENTAL SEMINAR (COMPUTER & COGNITIVE SCIENCES)
                           AUTUMN TERM 2000


TIME AND PLACE:    Thursdays 4pm (Unless otherwise stated)
                   Lecture Room 7, School of Computer Science

ORGANISER:         Marta Kwiatkowska
                   (M.Z.Kwiatkowska@cs.bham.ac.uk, ext 7264)
                   Sammie Snow
                   (S.Snow@cs.bham.ac.uk, ext 4774)


SPEAKERS and TITLES


-- Thu 12 Oct   Prof. Aaron Sloman, School of Computer Science,
                University of Birmingham:
		What are virtual machines? Are they real?
		
-- Thu 19 Oct   Caspar Bowden, Director, Foundation for Information Policy 
                Research, RIP Information Centre: 
                The RIP Saga - Interception, Encryption and Human Rights

-- Thu 26 Oct   Prof. Abbas Edalat, Department of Computing, Imperial College:
                Domain Theory and Differential Calculus
		
-- Thu  2 Nov   Dr Antoni Diller, School of Computer Science,
                University of Birmingham:
                The Belief-filter Problem

-- Thu  9 Nov	Dr David Duke, Department of Mathematical Sciences,
                University of Bath: 
                Reasoning about interaction and graphics	
		
-- Thu 16 Nov   Dr Annabelle McIver, Oxford University Computing Laboratory:
                Almost certain temporal properties and abstract probabilities

-- Thu 23 Nov   Prof. Samson Abramsky, Oxford University Computing Laboratory:
                Bounded types and finite state strategies: towards 
		model-checking for higher-order typed languages

-- Thu 30 Nov   Dr Peter Coxhead, School of Computer Science, University of 
                Birmingham:
	        No sentence is too difficult to understand: 
                syntax and semantics revisited

                ***Postponed until 15th March***
                Prof. Richard Brent, Oxford University Computing Laboratory:
                Prospects for Integer Factorisation Algorithms

-- Thu  7 Dec   ***Postponed until summer***
                Dr John Eakins, University of Northumbria at Newcastle:
                Content-based image retrieval - challenges and pitfalls

-- Thu 14 Dec   ***Postponed until further notice***
                Dr Bill Mitchell, Motorola UK Research Lab:
   (Hills 212)  Concurrent Testing of Requirement Specifications

		
ABSTRACTS

-----------------------------------------------------------------------------
-- Thu 12 Oct   Prof. Aaron Sloman, School of Computer Science,
                University of Birmingham:
		What are virtual machines? Are they real?
		
Philosophers have long discussed the relationship between mental
phenomena and physical phenomena. Theories about this include various
types of dualism (there are two kinds of stuff), various types of monism
(there's only one kind of stuff), pluralism/polyism (there are many
kinds of stuff), each of which has its own variants. E.g. according
to one sort of dualism, epiphenomenalism, causal traffic is one-way:
physical events can cause mental events and processes but not vice
versa, because the physical realm is "causally closed." There seem to be
only two options: the only ``true reality'' is the physical world and
either everything else is just an interpretation of it, or else its just
a collection of ``powerless shadows''. Both views are hard to square
with common sense.

Computer scientists and software engineers can now help philosophers
sort out this mess. We can make progress because there is a new type
of non-physical realm which we understand, because we have created it:
the realm of virtual machines in computers. However much of this
know-how is still at the stage of a "craft", i.e. it is
mostly intuitions and practical know-how of engineers and designers,
though theory is in hot pursuit.

Virtual machines have components which interact causally and change over
time. When they run they produce many sorts of physical effects, e.g.
changes on the screen and in the computer's memory, or movements of a
robot's limbs. How is that possible if the underlying physical circuitry
is causally closed?

Maybe our notions of causation become deeply confused when we
address questions about causal closure. My conjecture is that by
understanding more clearly what we mean by "X caused Y" in the context
of these "simple" computational virtual machines we may begin to get a
deeper understanding of all sorts of older, vastly more complex and
subtle, biological, social, mental, virtual machines and how their
reality, and their causal powers, do not contradict anything in physics.
They are not an illusion, not just an arbitrary interpretation of the
physical world, not ghostly powerless shadows. Philosophy needs help
from software engineers in order to understand all this.

(There is a longer abstract in
http://www.cs.bham.ac.uk/~axs/misc/semabstract.html )
		
-----------------------------------------------------------------------------
-- Thu 19 Oct   Caspar Bowden, Director, Foundation for Information Policy 
                Research, RIP Information Centre: 
                The RIP Saga - Interception, Encryption and Human Rights

The Regulation of Investigatory Powers Act became law in late July, despite
unanimous opposition from the press, industry and independent expert
opinion. What went wrong, what is still wrong, and what will go wrong with
RIP as it is implemented over the next year ? How can individuals and
companies lawfully circumvent its effects ? Now the UK is alone amongst G7
economies in having enacted Government-Access-to-Key (GAK) legislation, what
are the prospects for other countries following suit ? What does the RIP
story (and key escrow before that) tell us about political and institutional
structures for dealing with national security and law enforcement in the age
of the Internet ? FIPR led the analysis and debate on RIP and this talk will
address the full breadth of issues raised - see www.fipr.org/rip for more
details.

-----------------------------------------------------------------------------
-- Thu 26 Oct   Prof. Abbas Edalat, Department of Computing, Imperial College:
                Domain Theory and Differential Calculus
		
We introduce domain theory in differential calculus. Based on a new
structure in domain theory, we define the derivative of a Scott
continuous function on the domain of intervals, which is itself a
Scott continuous function. This leads to a domain-theoretic
generalization of the fundamental theorem of calculus. We then
construct a domain for differentiable real valued functions of a real
variable. The classical $C^1$ functions, equipped with its $C^1$ norm,
is embedded into the set of maximal elements of this domain, which is
a countably based bounded complete continuous domain. The construction
can be generalized to $C^k$ and $C^\infty$ functions and to real
valued functions of several variables. It can also be extended to
analytic functions. As an immediate application, we present a
domain-theoretic generalization of Picard's theorem, which provides a
data type for solving differential equations.

-----------------------------------------------------------------------------
-- Thu  2 Nov   Dr Antoni Diller, School of Computer Science,
                University of Birmingham:
                The Belief-filter Problem

Some people (for example, Brooks, Charniak and McDermott) think that
the ultimate goal of Artificial Intelligence is to design and build
an android who can pass undetected as he lives and interacts with
human beings.  Millions of pounds are being spent, especially in
the USA and Japan, on various projects whose common aim is to
construct a humanoid robot.  Surprisingly, one fundamental human
ability is largely ignored by people working on these projects.
The ability in question is that of learning from other people
by accepting what they say and by believing what they have written.
Before this ability can be programmed into a robot, it first has
to be understood and that is what I am trying to do.

The reason for the lack of interest in this ability is due, I believe,
to one of the central assumptions of empiricist philosophy, namely the
presumption that knowledge has its origins in perception.  Pollock,
for one, has been influenced by this tradition.  In his book
"Cognitive Carpentry", for example, he writes, "The starting point
for belief formation is perception.  Perception is a causal process
that produces beliefs about an agent's surroundings." I do not deny
that an agent gets some of his beliefs by making judgements about his
surroundings, but the number of such beliefs is quite small.  The vast
majority of an agent's beliefs are acquired by accepting the assertions
of other people.  One reason for this is that the sheer amount of
knowledge required to live in an advanced technological society,
in fact, in any society, is greater than that which any one person
could acquire by perception alone.

Some people (for example, Brooks, Charniak and McDermott) think that
the ultimate goal of Artificial Intelligence is to design and build
an android who can pass undetected as he lives and interacts with
human beings.  Millions of pounds are being spent, especially in
the USA and Japan, on various projects whose common aim is to
construct a humanoid robot.  Surprisingly, one fundamental human
ability is largely ignored by people working on these projects.
The ability in question is that of learning from other people
by accepting what they say and by believing what they have written.
Before this ability can be programmed into a robot, it first has
to be understood and that is what I am trying to do.

The reason for the lack of interest in this ability is due, I believe,
to one of the central assumptions of empiricist philosophy, namely the
presumption that knowledge has its origins in perception.  Pollock,
for one, has been influenced by this tradition.  In his book
"Cognitive Carpentry", for example, he writes, "The starting point
for belief formation is perception.  Perception is a causal process
that produces beliefs about an agent's surroundings." I do not deny
that an agent gets some of his beliefs by making judgements about his
surroundings, but the number of such beliefs is quite small.  The vast
majority of an agent's beliefs are acquired by accepting the assertions
of other people.  One reason for this is that the sheer amount of
knowledge required to live in an advanced technological society,
in fact, in any society, is greater than that which any one person
could acquire by perception alone.

-----------------------------------------------------------------------------
-- Thu  9 Nov	Dr David Duke, University of Bath 
                Reasoning about interaction and graphics	

Developments in interactive systems and computer graphics often depend
on properties of the user, in particular the user's capabilities to
perceive, interpret and respond to information presented by the device. 
However, models of human perception and cognition too often provided a
fragmented view of user capabilities, and are often in a form that makes
it difficult to examine design trade-offs or alternatives.  This talk
explains the rationale behind an approach to modelling interaction in
which formal methods are used to represent both the interface and a
model of human cognitive resources.  Issues underlying the use of formal
representations will be raised.  Two new directions opened up by this
work will be described.  The first generalises the approach to give a
framework for "macro-theory", addressing interaction between agents
across a range of abstraction levels.  The second is a specific
application of the modelling approach to understand issues in the
visualisation of large-scale datasets.

-----------------------------------------------------------------------------
-- Thu 16 Nov   Dr Annabelle McIver, Oxford University Computing Laboratory:
                Almost certain temporal properties and abstract probabilities

Many temporal properties of probabilistic, distributed systems are `almost
certain' --- they hold with probability 1 over the computation paths.  
Moreover, the class of `almost certain' problems are independent of the
actual weights associated with the probabilstic transitions, but rather
rely on the `probabilistic connectivity' of the underlying transition
system.

In this talk we introduce the idea of `abstract probabilities' to describe
probabilistic connectivity, and discuss the extent to which they influence
almost certain temporal properties of programs.  By extending the notion
of so-called 0-1 laws of probability theory to more general transition
structures, we show that `probabilistic connectivity' is in a sense
complete for the class of almost certain temporal properties.  As a result
we can simplify languages and proof systems for that class of problem.

-----------------------------------------------------------------------------
-- Thu 23 Nov   Prof. Samson Abramsky, Oxford University Computing Laboratory:
                Bounded types and finite state strategies: towards 
		model-checking for higher-order typed languages

We explore the theme of developing the algorithmic content of semantics,
with a view to applications in automated verification and program
analysis. In  particular, we consider the game semantics of languages
incorporating higher-order procedures and locally scoped state. We
introduce a bounded type system, which allows finite-state
approximations to the meanings of higher-order programs to be
considered. We give a compositional interpretation of programs as finite
automata which precisely charcterizes the meaning of the programs up to
observational equivalence. This can be used as the basis for a decision
procedure for observation equivalence, and for model checking with
respect to formulas expressing program properties.

-----------------------------------------------------------------------------
-- Thu 30 Nov   Dr Peter Coxhead, School of Computer Science, University of 
                Birmingham:
	        No sentence is too difficult to understand: 
                syntax and semantics revisited

The distinction between syntax and semantics is one often raised in
discussions of Natural Language Processing and of AI in general. The
distinction is important, at least to those interested in the 'Strong
AI Hypothesis' [1], because many of those who reject the hypothesis
(from Searle to Good) have used arguments which amount to the claim
that although computers may be able to process syntax they cannot
fully process semantics and hence cannot be said to be intelligent.
In the seminar I will look again at some of the classic examples used
in discussions of the syntax/semantics boundary, asking whether in
fact they do support the distinction that many wish to make, and if
so, whether this has any relevance to discussions of the Strong AI
Hypothesis. I will show for one such example (sentences of the form
No X is too Y to Z) that when a more detailed account of its
semantics is given than is usually attempted, the analysis does not
clearly support either side of the debate and certainly does not
support rejection of the possibility of artificial intelligence.

[1] For the purposes of the seminar I take this to be "Intelligence
is computation and nothing more."

-----------------------------------------------------------------------------
-- Thu  7 Dec   Dr John Eakins, University of Northumbria at Newcastle:
                Content-based image retrieval - challenges and pitfalls

Interest in content-based image retrieval (CBIR) as a research topic
has grown dramatically over the last ten years. So far, though, the
technology has failed to deliver results capable of meeting end-user
needs.

This talk will aim to analyse the difficulties involved in developing
workable CBIR systems, drawing on the experience of the ARTISAN and
SPIRIT shape retrieval projects at the University of Northumbria, and
point the way to potentially fruitful lines for future investigation.

-----------------------------------------------------------------------------
-- Thu 14 Dec   Dr Bill Mitchell, Motorola UK Research Lab:
   (Hills 212)  Concurrent Testing of Requirement Specifications

Often half the life cycle of a telecommunications system is spent
in testing. Systems which are physically disclocated are hard to
test. Distributed systems are sometimes tested using parallel test
components (PTC-s). These are distributed autonomous processes which
run in parallel. They interogatte the system being tested to ensure
that it's observed behaviour matches the requirements
specification. 

There are various technical problems with how these PTC-s can
successfully coordinate with each other. Firstly, how to ensure that
they are cooperating correctly with respect to the test specification,
and secondly how to ensure that they are reporting the correct verdict
after the test.

The talk will look at the problem of how to coordinate
the PTC-s correctly and when it is meaningful to adopt the concurrent
testing approach.

-----------------------------------------------------------------------------