Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

March 5, 2007

Computer Science and Physics

Posted by David Corfield

I recently came across Samson Abramsky’s What are the fundamental structures of concurrency? We still don’t know!. Abramsky forsees greater potential for computer science in interactions with physics rather than biology.

…while biological modelling will surely make new demands on process calculi, and hence lead to new developments …, I don’t believe it is likely to lead to foundational advances for the issues we are discussing. Biology’s foundational and conceptual structures are, if anything, much more plastic than those of Computer Science - for which, of course, it compensates by the exuberant richness and the sheer concrete reality of the existence proofs which it studies.

There is, perhaps, more prospect for guidance in finding fundamental notions of process, information flow, etc. from the rapidly developing interface between Computer Science and Physics, which has grown up around quantum informatics. (p. 3)

A good choice then by John for the two halves of his Quantum gravity seminar.

…the diagrammatics of our categories connect with categorical approaches to the Jones polynomial and other topological invariants, which in turn are strongly connected to quantum groups and topological quantum field theories. (p. 4 n1)

Abramsky’s paper Temperley-Lieb Algebra: From Knot Theory to Logic and Computation via Quantum Mechanics tells us more.

So will those long awaited categorified quantum groups be useful to computer science too?

Posted at March 5, 2007 2:45 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/1190

22 Comments & 1 Trackback

Read the post Gezocht: filosofie van de computerwetenschappen
Weblog: Filosofie voor elke dag
Excerpt: David Corfield komt op het einde van zijn "thought-provoking" boek Towards a Philosophy of Real Mathematics (2003) tot enkele interessante opmerkingen over theoretische computerwetenschappen, dat hij "still in a fairly precarious position" noemt. Computer
Tracked: March 5, 2007 4:41 PM

Re: Computer Science and Physics

Two great looking papers! I thought I’d start with the 5 page one. It’s always nice to see the problem of concurrency let out from under the carpet from time to time, especially when diamond phrases like

there is no single compelling notion […] of a ‘Church’s thesis for concurrency’

get rolled out too! I’ve never felt too comfortable with the phrase “physical Church/Turing thesis” and this strikes me like it could well be the main reason why

Posted by: Allan E on March 6, 2007 5:02 AM | Permalink | Reply to this

Re: Computer Science and Physics

Dear David Corfield,

Interesting post. I’ve been thinking about concurrency and physics in a broad sense during the past few months. Is it possible that nature is fundamentally concurrent?

Thanks,
Christine

Posted by: Christine Dantas on March 6, 2007 12:18 PM | Permalink | Reply to this

Re: Computer Science and Physics

Does the concept ‘concurrent information processing’ provide an explanation for the similarity between learning with nonparametric statistical models and physical field theories?

In Bayesian Field Theory: From likelihood fields to hyperfields, Lemm sets up the situation as follows:

For empirical learning it is convenient to distinguish three groups of variables:

  • 1. observable (visible) independent variables xx representing ‘inputs’ or ‘controlled causes’,
  • 2. observable (visible) dependent variables yy representing ‘outputs’ or ‘measured effects’,
  • 3. not directly observable (hidden, latent) variables ϕ\phi describing the possible (pure) ‘states of Nature’ considered in the model under study.

Now the posterior predictive density is

p(y|x,D,D 0)=dϕp(y|x,ϕ)p(ϕ|D,D 0)p(y|x, D, D_0) = \int d\phi p(y| x, \phi)p(\phi| D, D_0), where DD is the training data and D 0D_0 is the prior knowledge.

Lemm continues:

In nonparametric models where ϕ\phi is a function the integral over ϕ\phi stands for a functional integral. Such integrals are mathematically well defined for Gaussian processes (‘generalized free Euclidean fields’ or ‘generalized Brownian motion’ in the language of physics), but for more general processes (‘(self–)interacting fields’) a general mathematical definition of functional integrals is still an unsolved problem. One possible approach is to define a non–Gaussian functional integral by renormalization procedures in perturbation theory or on a lattice, another simpler possibility is to discretize the function ϕ\phi in some appropriate basis so the functional integral becomes a standard (but typically still extremely highdimensional) integral.The remaining highdimensional integrals can either be approximated by Monte Carlo methods or by the method of steepest descents (Laplace approximation), in this context known as Maximum A Posteriori (MAP) approximation…In principle one can also go beyond the MAP approximation by using the MAP solution as starting point for a perturbation series, for example, graphically expressed by Feynman diagrams.

Does all of this make sense from the physics side?

Posted by: David Corfield on March 6, 2007 12:56 PM | Permalink | Reply to this

unsolved; Re: Computer Science and Physics

“… for more general processes (‘(self–)interacting fields’) a general mathematical definition of functional integrals is still an unsolved problem…”

Even for electromagnetism, a complete solution to electrodynamics is not known. After a century of effort, there is not yet a satisfactory “theory of the electron” as the Dirac equations for the self interaction of the electron with its own field have “nonphysical solutions” as well a physical solutions. There are arguments for a new kind of relativistic shock wave, where relativistic plasmas collide (as may happen astrophysically) according to these equations.

Notoriously, Feynman diagrams are the tip of a baffling iceberg, whose general case is unknown.

Ane even with breakthroughs in the Math and Physics of Brownian motion, there are still mysteries afoot in percolation theory.

Perturbing indeed!

Posted by: Jonathan Vos Post on March 7, 2007 12:24 PM | Permalink | Reply to this

Re: Computer Science and Physics

So will those long awaited categorified quantum groups be useful to computer science too?

I think the answer is, “Yes, of course.” From a certain point of view category theory is nothing but[*] ordinary mathematics properly modularized, and thanks to the Curry-Howard correspondence every modularity mechanism in mathematics gives rise to one in programming languages, and vice versa.

[*] “nothing but” – a tremendous bald-faced lie, like all useful philosophical perspectives.

Posted by: Neel Krishnaswami on March 8, 2007 1:48 AM | Permalink | Reply to this

Re: Computer Science and Physics

I stopped doing this for a living a long time ago but… I think Samson is coming to this story rather late. Certainly when I talked to Carl Adam Petri at the GmD in 1990 (he was about to retire, I was on my first postdoc) he was explicitly concerned with finding the right mathematics to describe concurrency in the sense of physical systems. That’s partly why my first collection of papers was entitled “3 papers on classical concurrency theory” – because I was trying to find the right way to reason about the kind of concurrency that makes sense in a Newtonian world. Partly spurred by Vaughan Pratt’s poset models, Robin Knight and I subsequently proved a neat result about which causal orders could be fully and faithfully embedded in Minkowski space of arbitrary dimension.

The point of this is not to belatedly publicise long dead papers, but rather to emphasise that some people in computer science have been interested in using concurrency theory to describe aspects of purely physical systems for a long time: it goes back at least as far as Petri’s original work.

Posted by: David Murphy on March 8, 2007 9:56 PM | Permalink | Reply to this

Re: Computer Science and Physics

Dear David Murphy,

I’m interested in reading you paper with Robin Knight. I would very much appreciate, if possible, to receive a copy of it.

christinedantas $#at#$ yahoo.com

Thank you,
Christine

Posted by: Christine Dantas on March 9, 2007 2:49 AM | Permalink | Reply to this

Re: Computer Science and Physics

I’ve mailed you the paper, Christine. If anyone else wants a copy please let me know.

Posted by: David Murphy on March 12, 2007 9:41 PM | Permalink | Reply to this

Re: Computer Science and Physics

I can confirm that this connection was apparently well enough known for my lecturers to discuss in my undergraduate classes (in ‘94).

To illustrate the issue they’d start by describing some system (eg a vending machine) using a formalism like the pi-calculus, then “break” it by asking us to consider a new situation with some extra physical parameter (eg time) which wasn’t amenable to the model.

After considering a more few examples (realistic bounds on the in-degree of processes, heat dissipation, hardware design, …) they made the case that the logical conclusion was to consider physics as a “model” of concurrency — but that for this line of thought to be useful to computer scientists, we’d prefer a concurrent model of physics! (as Christina suggests!)

What strikes me about Abramsky and Coeke’s papers is the suggestive and amazingly simple new formalism. You can really imagine specifying systems in it (well, at least after the nice clear examples they give), which is as far as I know a first for this area.

So it seems to me (although I have never done this for a living) that this exciting area is still in it’s infancy. Eg one of the operational semantics for the pi-calculus was a lot of fun – the “chemical abstract machine” (CHAM) was based on the notion of processes as a reactive gas which would perform computation as it was “heated” and “cooled”. So what about a “physical abstract machine” — would I be right in guessing that this is close to the ideas you were asking about Christina? (maybe at a higher mathematical level than I’ve described?)

Posted by: Allan E on March 9, 2007 4:03 AM | Permalink | Reply to this

Re: Computer Science and Physics

Dear Allan E,

I’m enthusiastic with the possibility of seeing a new field, “concurrent physics”, emerging. As you mention, this idea is probably latent for some time now. What I have been randomly writing over at my blog are just incipient ideas that have been crossing my mind somewhat intuitively. I’m an astrophysicist who have been working in the past 2 years with concurrency in the context of real-time, critical software development for space applications. No, I have nothing mathematically sophisticated developed yet. This is too difficult. One thing that the experts here are able to address is the prospectiveness of n-Category to be the mathematical framework for concurrent physics.

Best,
Christine

Posted by: Christine Dantas on March 10, 2007 12:32 AM | Permalink | Reply to this

Re: Computer Science and Physics

I just happened on this post by David Murphy (hello David - long time no see).

If only David M had looked at my short discussion paper which David Corfield originally referenced, starting this thread, he would have seen that much of it was explicitly about Petri’s pioneering contributions in this direction!

This little piece attracted the attention of the Petri net community, who have invited me to speak at their annual conference in July.

The current developments are in my view very exciting, and going much further in both scope and depth than those pioneering contributions did.

For example, there will be a session on these links between Computer Science and Physics at the MFPS conference next month. See:

http://www.math.tulane.edu/~mfps/program23.html

See also:

http://se10.comlab.ox.ac.uk:8080/FOCS/CKCinOXFORD_en.html

And the QICS project, a European project which has just started up, involving both Computer Scientists and Physicists. See:

http://web.comlab.ox.ac.uk/oucl/work/ross.duncan/qics/

Posted by: Samson Abramsky on March 16, 2007 8:01 PM | Permalink | Reply to this

Re: Computer Science and Physics

Dear Samson:

Hi! I’ll modify your post so the links work.

One can do this oneself by writing something like

⟨a href=”http://se10.comlab.ox.ac.uk:8080/FOCS/CKCinOXFORD_en.html”⟩this⟨/a⟩

which has the effect of producing

this

Note the obnoxious necessity of writing “a href” and “a” in lower case.

Posted by: John Baez on March 16, 2007 8:26 PM | Permalink | Reply to this

Re: Computer Science and Physics

Hi John!

Many thanks - I’ll try to do this the right way in future.

Posted by: Samson Abramsky on March 16, 2007 9:22 PM | Permalink | Reply to this

Re: Computer Science and Physics

Hi Samson

Thanks for the comment - it has indeed been a long time… and it’s really nice to see these things bubbling back to the surface. I did indeed read your paper: part of what I was trying to say, albeit imperfectly, was that you were right to discuss Petri’s contribution, but that perhaps the level of ambition of his programme didn’t come over. In the English speaking tradition there is perhaps a tendency to take a slightly watered down perspective on Petri nets, (not least because it is so difficult to say anything compositional beyond the Winskel or Montanari style settings) but I think that we can agree that as a descriptive tool they have some interest well beyond computer science.

I’ll just go back to lurking now and leave it to the professionals…

David.

Posted by: David Murphy on March 17, 2007 7:20 PM | Permalink | Reply to this

Re: Computer Science and Physics

Dear Allan and Christine

I’m enthusiastic with the possibility of seeing a new field, “concurrent physics”,
emerging. As you mention, this idea is probably latent for some time.

I guess what I was trying to say in my original post was that Carl Adam Petri thought he was doing that already… Perhaps we have better tools now - and I agree with Allan that paradigms like the CHAM are interesting - but the basic problem remains that the paradigm of concurrency is too primitive do deal with ongoing interactions. Process calculi for instance allow instantaneous, unitary interactions. But we could not even begin to write down the interactions involved in two body Newtonian gravity in any concurrency theory I know of. It’s not that I am deeply enamoured of continuous mathematics in general or field theory in particular, but it does do that job rather well. What might perhaps be interesting is to think what the logic of interaction in that kind of setting is…

Kind regards

David.

Posted by: David Murphy on March 12, 2007 9:51 PM | Permalink | Reply to this

Re: Computer Science and Physics

I guess what I was trying to say in my original post was that Carl Adam Petri thought he was doing that already… Perhaps we have better tools now

According to a paper by Sokolowski, “Directed topology and concurrency - a short overview”, local po-spaces generalize several classical models of concurrency. In increasing generality:

Petri nets -> transition systems -> higher dimensional automata -> cubical complexes -> local po-spaces…

Best,
Christine

Posted by: Christine Dantas on March 13, 2007 4:24 PM | Permalink | Reply to this

Re: Computer Science and Physics

Dear Christine

Yes and no. That dimension of refinement does give us better tools than, say, labelled transition systems, but they are (I suspect - the details would take a while to check) no more descriptive than Petri nets and anyway they have atomic actions.

Here’s the issue. Concurrency theory uses the idea that two processes P and Q somehow atomically synchronise. In a Petri net this is via a token being on a common place: in process calculus it is via agreement on an action (CSP) or on an action and a coaction (CCS): in the po space models it is via a shared oriental. The largest thing we have in any of these settings are w-colimits of algebraically specified objects.

In a physical system in contrast an *infinitesimal* change in P is affected by the field of Q and vice versa. So we need much bigger objects (and much more care about avoiding pathologies) to talk about their joint behaviour.

David.

Posted by: David Murphy on March 14, 2007 8:56 PM | Permalink | Reply to this

Re: Computer Science and Physics

Dear David,

Thank you for a clarifying and interesting comment. There are, however, some terms I am not acquainted with: “shared oriental” and “w-colimits”. I have searched the internet but was not very successful. I would appreciate to receive some pointers to the literature on these concepts, if possible. I don’t know how far we are diverting from the current thread, so perhaps we should continue the discussion via email?

Thank you.
Christine

Posted by: Christine Dantas on March 15, 2007 3:50 AM | Permalink | Reply to this

Re: Computer Science and Physics

Dear Christine

Shall I just explain the two terms in the message above then we can flip to email.

In a labelled transition system there is no difference between first a then b happening or the reverse and them happening concurrently. Thus the choice between ab and ba and a par b has the same semantics. In an HDA we distinguish them by adding a membrane between them: think of a square with a ‘2 cell’ between ab and ba. In general if we have n things in parallel we will have cells at dimension n. Since time flows in one direction they are oriented. Now if P and Q cooperate on one of these parallel executions they share one of these orientals: hence shared oriental.

The reason we only care about ω colimits is that in computer science we care about recursion, but only the kind that you can specify effectively. The old style way of doing that was domain theory where these desired ‘fixed points’ could be found: in categorical language these fixed points are colimits, but ones of certain countably infinite diagrams. Again from distant memory, see for instance Coquand’s dI domains for a setting where these are guaranteed to exist.

Inituitively the problem in physics is harder because we want to identify some smooth forms of continuous interaction. By analogy the joint behaviour of two processes interacting should then again be a colimit, but it is no longer \omega filtered. Figuring out a way to ban the pathologies of continuous behaviour from the semantics (so for instance you can’t have a process that does one thing for each instant t if t is rational and another if t is irrational) yet has all the richness you do actually want isn’t all that easy.

David.

Posted by: David Murphy on March 15, 2007 8:31 AM | Permalink | Reply to this

Re: Computer Science and Physics

I have added a reply to David Murphy’s original post to this thread.

Posted by: Samson Abramsky on March 16, 2007 8:08 PM | Permalink | Reply to this

Re: Computer Science and Physics

Good day, dear researchers. :)

Are you thinking about higher quantum computers (string computers) or may be you are thinking about thinking about them at least?

Posted by: Ignorant man from a street on March 19, 2007 6:49 PM | Permalink | Reply to this

Re: Computer Science and Physics

For those who want a gentler introduction to many of Abramsky’s interests, I recommend his chapter in this Handbook.

Posted by: David Corfield on March 23, 2007 9:31 AM | Permalink | Reply to this

Post a New Comment