tag:blogger.com,1999:blog-74465942014-08-22T00:03:19.532-07:00Bob WaltersRobert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.comBlogger224125tag:blogger.com,1999:blog-7446594.post-75420892542516678912010-05-17T23:54:00.000-07:002014-08-17T06:46:47.706-07:00HypothesesI notice that John Baez has realized a danger of the new scientific order of blog posts, blog comments, labs, mailing lists, expository-style papers, preprints in arxiv, and traditional scientific journal articles.<br /><br />From a comment on the May 15, 2010 post of <a href="http://golem.ph.utexas.edu/category/">n-category cafe</a> (my italics)<br />"This Week’s Finds and my seminar notes are packed with hunches of varying caliber. Sometimes you need to read between the lines a bit to see them — for example, if I say something ‘should’ be true, it means I believe it’s true but haven’t proved it. And sometimes, <span style="font-style: italic;">I’ve said something is true even though I haven’t proved it</span>. By now I realize this is a bad habit… thanks to the following story.<br />Once I went to a talk where somebody said that for any ring R there’s a one-object tricategory Alg(R) consisting of R-algebras, bimodules and bimodule morphisms. I said “Really? Do you know if anyone has ever written that up?” And the speaker said “Sure! It’s in This Week’s Finds!” Which galled me, because <span style="font-style: italic;">while I knew it was true</span>, I’d never seen a proof written up — and I realized then that by claiming it was true in This Week’s Finds, I’d reduced the chances of ever seeing a proof."<br />Another remark:<br />"The last page of my slides was supposed to summarize only the ideas that will surprise and thrill the audience, so I get a standing ovation."<br /><br />I find the current state of n-category theory a confusing mixture of conjecture, unfinished definitions, unfinished proofs, buts lots of exposition.<br /><br />I am old-fashioned and believe that to maintain integrity we must insist that the science exists in the scientific journal articles. Credit should be assigned on the basis of published scientific articles. <br />I don't know what it means to have expository articles of an vaguely developed field.<br /><br />Perhaps we will end with Bogdanovs.Robert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-15018100474322153302012-10-01T08:01:00.003-07:002014-08-17T06:43:52.280-07:00Verba volant, scripta manentWhere do the internet, the blogs, digital photographs, the cloud and internet archives fit in?Robert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-81419325976500468982013-03-04T22:24:00.001-08:002014-08-17T06:43:10.299-07:0070I am seventy years old. Time to write memoirs.<br /><br />5th March 2013Robert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-71951879070905476892013-09-26T04:25:00.002-07:002014-08-17T06:41:53.501-07:00Ross Street's OrientalsI recently had a look at one of Jacob Lurie's expositions (in 111 pages) on<a href="http://www.math.harvard.edu/~lurie/papers/cobordism.pdf"> the clasification of topological field theories</a> - very briefly and with little comprehension. I find it difficult to read mathematics in which not even formal definitions are given: Lurie himself says "In many instances, we have not attempted to give precise definitions, let alone careful proofs".<br /><br />I have always been interested in lower category theory (up to symmetric monoidal bicategories) but only once have ventured beyond. Always we had the idea that natural transformations were like homotopies, and that one could consider homotopies between homotopies and so on, and so one would get higher categories. Thinking about axiomatizing higher categories, in particular higher associative laws lead Ross Street to considering the free n-category on an n-simplex. Mike Johnson and I also worked on this problem.<br /><br />Following this<a href="https://dl.dropboxusercontent.com/u/92056191/Archive/temporary_new_material/Orientals.html"> link</a> there is an early picture produced by Ross of an oriental.<br /><br /><br />This seems to me still an interesting problem but I don't see where it has gone in Joyal and Lurie's work.<br /><br />In any case infinity-category theory seems to be a distinct subject from category theory. Category theory should resist the attempted takeover.Robert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.com1tag:blogger.com,1999:blog-7446594.post-76750608779192553472014-08-05T02:10:00.006-07:002014-08-17T06:39:39.621-07:00The sleeping beauty problem: how some philosphers and physicists calculate probabilityRecently there have been surprising discussions and disputes amongst philosophers and physicists about an elementary probability problem called the Sleeping Beauty problem. The following remarks are, as usual in this blog, the result of discussions with Nicoletta Sabadini.<br /><br />The problem goes as follows: A beauty is told that the following procedure will be carried out. On Sunday a fair coin will be tossed without her knowing the result. She will go to sleep. Then on Monday one of two possibilities will occur.<br /><br />In the case that the toss of the coin resulted in tails she will be wakened and asked her opinion of the probability that the result of coin was heads. She will then have her memory of what happened on Monday erased and will be put to sleep. On Tuesday (again in the case of tails, without a further toss of the coin) she will be wakened and asked her estimate of the result of the coin toss being heads.<br /><br />In the case of heads, on Monday she will be asked her estimate of the probability that the result of the coin toss was heads. In that case she will not be asked again.<br /><br />It seems clear intuitively that, when this procedure is carried out, in all three responses she has learnt nothing about the result of the coin toss, and that she should answer in each case $1/2$.<br /><br />Strangely a considerable number of philosophers and physicists make an elementary error in the calculation of probabilities and believe that she should answer $1/3$.<br /><br /><b>Update:</b> I see also that a recipient of the COPSS Presidents' Award (the Nobel Prize of Statistics, according to Wikipedia), Jeffrey S. Rosenthal, believes the $1/3$ answer.<br /><br /><a name='more'></a>The philosophers who come to this conclusion include professors at Princeton (Adam Elga) and Oxford (Nick Bostrom). The physicists include a Senior Research Associate at Caltech, Sean Carroll, who manages to involve quantum mechanics and the multiverse. Another seems to be a Dirac and Milner prizewinner, Joe Polchinski. (Not all physicists agree - for example, the maverick (or main stream?) physicist <a href="http://motls.blogspot.it/2014/07/the-sleeping-beauty-problem.html">Lubos Motl </a>is scathing about the answer $1/3$.)<br /><br /><b>Update</b>: Lubos Motl has reblogged <a href="http://motls.blogspot.it/2014/08/sleeping-beauty-thirders-rudimentary.html">this post on his blog</a>, with additional interesting comments.<br /><br />Let's see how they manage to come to the $1/3$ conclusion and what their elementary error is.<br /><br />We can describe the procedure by a simple Markov chain, pictured below, in which the initial state (Sunday) is $0$, the state $1$ is Monday in the case of heads, the state $2$ is Tuesday and subsequent dates after heads, the state $3$ is Monday in the case of tails, the state $4$ is Tuesday and subsequent dates in the case tails.<br /><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-okVWhawInl4/U-DIckLs5JI/AAAAAAAABzY/qBMeTS1gCB8/s1600/markov.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-okVWhawInl4/U-DIckLs5JI/AAAAAAAABzY/qBMeTS1gCB8/s1600/markov.jpg" height="234" width="320" /></a></div>Now the argument of the philosophers/physicists mentioned above is that when the beauty is awakened she knows she is in one of states 1, 3 or 4 but she doesn't know which.<br />They claim that being in each of these three states has the same probability, and hence this probability must be $1/3$ (the sum must be $1$). But in state $1$ she knows the coin was heads, and in $3$ and $4$ the coin was tails. So in a third of cases the coin is heads, so she must answer $1/3$.<br /><br /><i><b>The egregious error!</b></i><br />In a Markov process one cannot in general talk about <i>the probability of being in a state. </i>One must talk about the probability<i> </i>of passing from state $x$ to state $y$ in $n$ steps.<br /><i> </i>(If the process is ergodic then in a limiting distribution there is some sense of talking about the probability of being in a state, but that is not the case here.)<br /><br />The three probabilities discussed above are (i) the probability $p_1$ of going from $0$ to $1$ in <i>one step</i>, (ii) the probability $p_3$ of going from $0$ to $3$ in <i>one step</i>, and (iii) the probability $p_4$ of going from $0$ to $4$ in<i> two steps</i>. Each of these three values is clearly $1/2$.<br /><br />What however should the beauty calculate for the probability $p_{3,4}$ of being <i>either</i> in $3$ in one step or $4$ in two steps? The philosophers/physicists are claiming that $p_{3,4}=2p_1$. I claim $p_{3,4}=p_1$. To see this we need to think in general how to calculate the probability of going from state $x$ to $y$ in $m$ or $n$ steps in a Markov chain.<br /><br />Take $x$ to be a fixed initial state, which we wont mention again. The sum over all $y$ of $p_{one}(y)$ (the probability of reaching $y$ in one step) is $1$. The sum over all $y$ of $p_{two}(y)$ (the probability of reaching $y$ in two steps) is $1$. Hence taking $p_{one,two}(y)=p_{one}(y)+p_{two}(y)$ as the physicists/philosophers do would yield $\sum_yp_{one,two}(y)=2$ whereas the total probability should be one.<br />A reasonable definition for $p_{one,two}$ would be $p_{one,two}(y)=\frac{1}{2}( p_{one}(y)+p_{two}(y))$.<br /><br />This definition yields in the sleeping beauty problem that $p_{3,4}=\frac{1}{2}(p_3+p_4)= \frac{1}{2}=p_1$.<br /><br /><br /><br /><br />Robert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.com4tag:blogger.com,1999:blog-7446594.post-40775908205269622232014-08-09T04:54:00.001-07:002014-08-16T00:03:59.369-07:00The sleeping beauty problem: how some statisticians calculate probabilityThis problem was drawn to my attention by calculations of physicists and philosophers (see my last post), but I see that some eminent statisticians (Jeffrey S. Rosenthal) are also convinced that the answer is $1/3$.<br /><br />What I think is the real problem is that statisticians immediately start calculating with conditional probability, Bayes formula etc without modelling the problem mathematically. It is also important to generalize a problem to avoid being confused by particular details.<br />In any case, I want to clarify what I said in the last post by considering a simple example.<br /><br /><a name='more'></a>The essential point of the sleeping beauty problem (see my last post) is that the beauty is asked to estimate a probability without knowing how many steps of the process have occurred.<br /><br /><b>A simpler problem</b><br />Consider the following Markov chain with $100$ states meant to represent the birthdays of my life:<br />$0\xrightarrow{1}1\xrightarrow{1}2 \xrightarrow{1}\cdots \xrightarrow{1}99\xrightarrow{1}100 $,<br />with also a loop of probability $1$ at $100$ when I am in my tomb.<br /><br />Now it is clear that the probability of my being $1$ after $1$ year if $1$, the probability of being $2$ after $2$ years is $1$, the probability of being $n$ after $n$ years is $1$ ($n\leq 99$).<br /><br />Moreover if you ask me what is the probability of being $5$ say during my life (that is, after $0$ or $1$ or $\cdots$ or $99$ years) I might be tempted to answer $1$ since it is certain I will be $5$ during my life.<br /><br />However the sum of the probabilities that I am $n$ ($n\leq 99$) during my life must add to total probability $1$, and hence I must answer that the probability of being $5$ in my life is $1/100$. That is, rarely am I five.<br /><br />Notice that if I ask what is the probability of being alive (that is, in one of the states $n$ (0$\leq n \leq 99$) in a period of $\leq 99,999$ years, I must answer $1/(1000)$; that is, mostly you will find me dead.<br /><br /><b>The sleeping beauty problem</b><br />Applying the same reasoning to the sleeping beauty Markov chain in the last post, sleeping beauty must calculate the probabilities in the case of tails not knowing whether one or two days have passed, and so she must assign $1/4$ to the probability of Monday after tails, and $1/4$ to the probability of Tuesday after tails, so that the probability of Monday or Tuesday after tails is $1/2$.<br /><br />There is a complication I didn't mention explicitly in the last post. In the case of heads the beauty knows that only one step has occurred. Hence she should calculate the probability of the heads case using the probabilities in one step, not one or two steps. Hence she should estimate the probability of Monday as $1/2$ after heads.<br /><br />Notice that she has calculated probabilities in two different probability spaces. The fact that the sum of these two probabilities is $1$ means that knowing that she is being interviewed gives her no new information, or said in another way, conditioning on the fact that an interview is in process does not require normalization of the probabilities.<br /><br /><b>A statistician's argument against</b> $1/2$<br />Let us see how one statistician claims to get a contradiction from this estimate. I will describe an argument from a paper. (The article begins sloppily because in stating the problem it does not specify that the beauty knows the protocol of the procedure to be carried out.)<br /><br />The sample space is not described, and only partial inference is made about probabilities but sufficient to convince the author that $P(Heads)< \frac{1}{2}$. We will see that the error in the argument is that the beauty must make calculations in two different probability spaces (one step, and one or two step).<br /><br />The argument begins as follows: $P(Heads|Monday)=1/2$, $P(Heads|Tuesday)=0$, $P(Tuesday)\geq 0$, $P(Monday)=1-P(Tuesday)$ and hence $P(Monday)< 1$. All these probabilities are conditioned on the fact that an interview is taking place.<br /><br />Aside from the fact that he is really talking about two probability spaces (one step, and one or two steps) I could agree with these probabilities. However the real error comes in his next step, when he seeks to apply the law of total probability:<br />$P(Heads)=P(Heads|Monday)P(Monday)+P(Heads|Tueday)P(Tuesday)$ <br />$P((Heads)=(1/2)P(Monday)+0\times P(Tuesday)< (1/2)$<br />contradicting $P(Heads)=1/2$.<br /><br />The error comes from applying the law of total probability to two different probability spaces where it is not valid. Part of the equation refers to probabilities for one step, the other part to one or two steps.<br /><br /><br /><br /><br /><br /><br /><br /><br />Robert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.com5tag:blogger.com,1999:blog-7446594.post-88958677360042116692010-04-01T10:02:00.000-07:002014-08-15T10:46:11.030-07:00Heat on the netCommunication can become very heated on the net. I remember my first experience of it years ago when a round of emails between me, Max Kelly and Ross Street spiralled, in the course of a couple of hours, in aggression. The only way out of it was to stop writing, and start again later. (We successfully maintained a seminar, with others, which began in 1970, was still active when I left Sydney in 1998, and remains today one of the principal seminars in category theory.)<br /><br />I was reminded of this while thinking of the 20 year success of the Categories List. One needs to be conscious of the new mode of communication in order to produce a stable and productive group communication. I receive other lists which contain nothing but announcements of conferences and of jobs, whereas the categories list has managed to sustain mathematical discussion.<br /><br />I found an interesting page about <a href="http://www.aaup.org/AAUP/pubsres/academe/2007/JF/Feat/Lear.htm">moderated academic lists</a>. I quote one paragraph:<br />"One lesson I learned along the way is that the ecology of an active online community is surprisingly fragile. It can go wildly out of whack, and even self-destruct, in a very short time. I’ve seen any number of lists decline and die over the years. Some merely waste away through attrition and neglect until no one posts <br />to them anymore; others become mere notice boards for calls for papers and the like, without any real interaction among subscribers. A few flame out spectacularly, bursting with so many nasty, off-topic messages that all the “lurkers” unsubscribe, leaving the <br />disputants to fight among themselves until even they grow weary of it. Charting a middle course means achieving a high “signal-to-noise” ratio, in which the list’s content is useful enough to make it worth people’s time to stay involved." <br /><br />Another thing I learnt looking around is the meaning of "internet troll". From <a href="http://en.wikipedia.org/wiki/Internet_forum">wikipedia</a> a quote:<br />"Forum trolls are users that repeatedly and deliberately breach the netiquette of an established online community, posting inflammatory, extraneous, or off-topic messages to bait or excite users into responding or to test the forum rules and policies, and with that the patience of the forum staff. Their provocative behavior may potentially start flame wars or other disturbances. Responding to a troll's provocations is commonly known as 'feeding the troll' and is generally discouraged, as it can encourage their disruptive behavior."Robert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-4451816655428631272010-05-23T23:43:00.000-07:002014-08-15T10:45:35.202-07:00Probability 2 - Boy or Girl paradoxI continue to be amazed by the fact that apparently simple probability problems are often so difficult to resolve. It is particularly surprizing in view of the fact that so much science seems to depend on probability these days: the particle physicists' results are small probabilistic anomalies in incredibly expensive experiments, quantum physicists say that nature is inherently probabilistic, the medicine we take is determined by 'random' trials, evolution apparently occurs by 'random' mutation, etc, etc. (I don't necessarily concur with all this, by the way.) <br /><br />I have been thinking more about this fact since the <a href="http://cameroncounts.wordpress.com/2010/05/02/probability/">blog post of Peter Cameron</a>, which derived from another <a href="http://go2.wordpress.com/?id=725X1342&site=cameroncounts.wordpress.com&url=http%3A%2F%2Falexbellos.com%2F%3Fcat%3D1%26paged%3D2&sref=http%3A%2F%2Fcameroncounts.wordpress.com%2F2010%2F05%2F02%2Fprobability%2F">post by Alex Bellos</a>. The particular problem they consider is this: if someone tells you that they have two children at least one of whom is a boy born on Tuesday, what is the probability that the second child is a boy?<br /><br />Actually, the simpler version of this problem in which there is no mention of the day of birth (possibly introduced by <a href="http://en.wikipedia.org/wiki/Martin_Gardner">Martin Gardner</a> who died 22nd May), has been <a href="http://en.wikipedia.org/wiki/Boy_or_Girl_paradox">discussed and disputed</a> in short and in long, in circles high and low, under the name "The Boy or Girl Paradox".<br /><br />In short, my view is that the answer to this question is 1/2 (under the simplifying assumptions clearly intended; that is, that the birth rates of boys and girls are equal, etc).<br />However a closely related problem which I will explain would yield the answer 1/3, the answer preferred by mathematicians.<br /><br />I think this simple problem benefits from the distinction between states and actions, the states being the quality of being a girl or a boy, and the actions being the declarations made. In the real world problem you need to consider the probability of the action as well as the probability of being in a state.<br /><br />Let's now consider the problem in detail: the simplifying assumptions mentioned above mean that given a family with two children the following four cases are equally likely: BoyBoy, BoyGirl, GirlBoy, GirlGirl. In the case BoyBoy the likelihood of a declaration that there is a boy is 1, in the case of GirlGirl the likelihood of a declaration that there is a girl is 1, but in the other two cases there is a half chance that the declaration is 'boy', and a half chance that the declaration is 'girl'. Now let's look at the total weight of a declaration 'boy': it is 1+1/2+1/2. The weight which corresponds to the case BoyBoy is 1. Hence the proportion of 'boy' answers which correspond to the state two boys is <br />1/(1+1/2+1/2)=1/2. <br /><br />Now a slightly different problem: suppose I interview people with two children, and ask if they have a boy in the family; if they answer yes, what is the probability that the second child is a boy?<br />Again the simplifying assumptions mentioned above mean that given a family with two children the following four cases are equally likely: BoyBoy, BoyGirl, GirlBoy, GirlGirl. In the case BoyBoy the likelihood that they respond 'yes' is 1, in the case of GirlGirl the likelihood that they respond 'yes' is 0; in both the other two cases the likelihood of 'yes' is 1, not 1/2. Now let's look at the total weight of a response 'yes': it is 1+1+1. The weight which corresponds to the case BoyBoy is 1. Hence the proportion of 'yes' answers which correspond to the state two boys is <br />1/(1+1+1)=1/3. <br /><br />If there is also mention of the day of birth there are at least three interpretions:<br />1) a person declares that they have two children at least one a boy born on Tuesday;<br />2) when asked if they have a boy, the response is 'yes, and born on Tuesday';<br />3) when asked if they have a boy born on Tuesday, the response is 'yes'.<br /><br />The probability of the second child being a boy in the first case is 1/2, in the second <br />1/3 and in the third 13/27.<br /><br />In this post I have tried (exaggeratedly) to argue in as simple language as possible, because a simple problem should only require the appropriate distinctions, not a big machinery. However I have earlier proposed (with Sabadini and de Francesco Albasini) a <a href="http://arxiv4.library.cornell.edu/abs/1005.0949">mathematical context</a>, in which many of the perplexities are seen to arise from considering (normalized) probabilities, rather than weights of actions. The precise mathematical point is that normalization does not behave well with respect to sequential operations (which include abstraction). Another simple perplexing example where abstraction does not work well with normalization is Simpson's paradox, the mathematical origin of which is the fact that not always a/b+c/d=(a+c)/(b+d).<br /><br />An extreme example of Simpson's paradox is the following:<br />Consider treatments A,B and diseases X,Y.<br />Treatment A with disease X on one person cures the person (100% cure rate - best possible)<br />Treatment B with disease X on 99 people cures 98 (worse than 100%).<br />So A has a better success rate than B with disease X.<br /><br />Treatment A with disease Y on 99 people cures 1 person (this is better than 0% cure rate)<br />Treatment B with disease Y on one person fails to cure (0% cure rate - worst possible).<br />So A is better than B with disease Y.<br /><br /><br />In both diseases X and Y the treatment A is better than B.<br /><br />However treatment A saves 2 people in 100, B saves 98 in a hundred.<br />B is worse than A???Robert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.com6tag:blogger.com,1999:blog-7446594.post-61935112413282262002010-05-06T08:49:00.000-07:002014-08-15T10:44:56.602-07:00ProbabilityI made the suggestion recently that the Kolmogorov presentation of probability was too abstract, and that this was the cause of elementary confusions like those common in the Monty Hall problem. <br /><br />I must admit to being quite unsure of the foundations of probability theory. The fact that simply stated problems are easy to make errors about hints to me that the gap between theory and practice is too wide. I make some tentative remarks below, which are made more formal in a <a href="http://arxiv.org/abs/1005.0949">small paper</a> we have just written.<br /><br />1. First, I think probability should be about explicitly described systems. (Peter Cameron in his <a href="http://cameroncounts.wordpress.com/2010/05/02/probability/">blog post</a> describes two possible systems ("protocols") which might be behind a particular problem, yielding different results.) This would imply that one needs a notion of system. In this context probabilities are weightings of actions in a particular state of a system. Such a weighting represents information about the cause of actions. It is a kind of primitive dynamical information.<br /><br />2. The Kolmogorov view is that independence is defined in terms of the probabilities of events. This is the attitude that we are observing behaviours, rather than considering systems. For systems there is a clear operation of composition in parallel. Actions may be appear to be independent behaviourally without being actually parallel.<br /><br />3. The fact that the sum of all probabilities must be 1 is another evidence of a behavioural view. A system may have big reasons for making a choice, or small reasons, in both cases, say, with a half and half probability. This doesn't affect observed behaviours. However in composing systems large reasons in one system may overwhelm small reasons in another.<br /><br />To make this more concrete: suppose I am in a situation where I am deciding to eat an apple or a pear (with equal interest), and suddenly I perceive that a car is driving straight towards me, and that with equal choice I must decide whether to run to the left or right to avoid an accident. This is a state in a composition of two systems. It is clear that the weight behind choosing an apple or a pear is overwhelmed by the choice between jumping left or right.<br /><br />At a system level weight is more fundamental than probability, which arises as a normalization of weight.<br /><br /><span style="font-weight: bold;">Update:</span> I see now that Peter Cameron has come to a conclusion (which I quote in full, but with my italics; it refers to a particular calculation which you can see at his <a href="http://cameroncounts.wordpress.com/2010/05/02/probability/">blog</a>):<br />"Mathematically the conditional probability that someone has two boys, given that one of their two children is a boy born on Tuesday, is 13/27. If we started defining the probability of some event in terms of the algorithm that led to the statement being made, all our textbooks would need to be rewritten from the ground up. <span style="font-style: italic;">I think the best way to proceed is to say</span>, we do know how to calculate probability (and how to interpret it), but this requires careful thought, and sometimes our intuition lets us down."<br /><br /><span style="font-weight: bold;">Update:</span> I made a too brief comment on Peter Cameron's blog, namely that<br />"I agree with John Faben [another commenter] that the calculation of probability requires information about the algorithm involved."<br /><br />It is somewhat difficult in blogs to follow which comments are later referred to, but it seems that Peter replied to my comment with the following:<br />"Sorry to have to disagree…<br /><br />Any calculation in probability can be done unambiguously by the rules (based on Kolmogorov’s axioms) provided we specify carefully what is the “sample space” and what is the probability measure on the sample space. If you start bringing in other factors like the algorithm used to generate a statement then all you are doing is changing the measure. That is why I said in my example that I am a covert Bayesian. I happen to think that the probability measure that applies in a given situation depends on everything I know about the situation (which may include information about the algorithm used to generate some statement)."<br /><br />He wrote more which I do not reproduce here.<br /><br />I have been trying to understand why is it difficult to apply the existing theory (Kolmogorov) to apparently simple real world problems, a fact admitted by Peter. (There is a rumour that even Erdos had difficulty with Monty Hall.)<br /><br />My suggested answer to this is that there is too great a gap between real world problems and the theory, and perhaps there could be a more detailed theory in between reducing the gap.<br /><br />The more detailed theory would be prior to the construction of the probability space.<br />It would consist in making more precise the real world problem, by describing a mathematically formal system (algorithm, or protocol). This is not beyond the capacity of mathematics to do.<br /><br />Peter seems to agree when he says "everything I know about the situation", which is another way of saying the precise system under consideration.<br /><br />There is a sleight of hand in the statement "If you start bringing in other factors like the algorithm used to generate a statement then all you are doing is changing the measure". The algorithm is needed to determine the measure; different algorithms determine different measures.Robert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.com1tag:blogger.com,1999:blog-7446594.post-71445593195788768702014-08-15T10:27:00.002-07:002014-08-15T10:38:16.662-07:00Span(Graph) II: Circuits with feedback<a href="http://rfcwalters.blogspot.it/2014/08/spangraph-i.html">Previous Span(Graph) post</a>; next Span(Graph) post.<br /><br />As an introduction to ${\bf Span(Graph)}$ I will describe how to extend the category of straight-line circuits to allow circuits with state and feedback. But before doing that I would like to point out a couple of things about straight-line circuits.<br /><br /><a name='more'></a><br /><br />Firstly, I introduced the operation of twisting two wires $twist:B^2\to B^2$. It is easy to see that using $twist$, $1_B$, product and composition we can write an expression which gives the twisting of two wires against two wires, or $m$ wires against $n$ wires, or in fact any permutation of wires. Let's just look at twisting two across two.<br /><br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/-oEsX68CUVCQ/U-5CIaoFVAI/AAAAAAAABz0/zOfNL8IcW3E/s1600/twist2.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-oEsX68CUVCQ/U-5CIaoFVAI/AAAAAAAABz0/zOfNL8IcW3E/s1600/twist2.jpg" height="106" width="200" /></a></div><br /><br />We can read off the expression:<br /> $(1_B\times twist\times 1_B)(twist\times twist)(1_B\times twist \times 1_B)$.<br /><br />Another operation on wires was the duplication of a wire $\Delta:B\to B^2$. But we can also duplicate two, or $n$ wires. Let's see two:<br /><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-BUysAHDUJng/U-5Ce0hfHuI/AAAAAAAABz8/OnAcRRvvAgk/s1600/diag2.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-BUysAHDUJng/U-5Ce0hfHuI/AAAAAAAABz8/OnAcRRvvAgk/s1600/diag2.jpg" /></a></div><br /><br />We will call this operation $\Delta_2$, defined by $\Delta_2=(\Delta\times \Delta)(1_B\times twist\times 1_B)$. Its input/output behaviour is $(x,y)\mapsto (x,y,x,y)$.<br /><br />A final example before passing to circuits with feedback, namely an equation true for straight-line circuits but false for the circuits with feedback we are about to define. I will draw a picture of the equation: given any arrow $f:B\to B$ (but a similar equation is also true for and $f:B^m\to B^n$):<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-C0T-_GuD2VI/U-5CqhUmvCI/AAAAAAAAB0E/MgIh1iUrsHw/s1600/eqn.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-C0T-_GuD2VI/U-5CqhUmvCI/AAAAAAAAB0E/MgIh1iUrsHw/s1600/eqn.jpg" height="118" width="320" /></a></div><br />That is, $f\Delta=(\Delta\times \Delta)(f\times f)$. If you look at the input/output behaviour of these circuits you can see they are the same namely $x\mapsto (f(x),f(x))$, however the second uses more components.<br /><br />${\bf Boolean\; circuits\; with\; state\; and\; feedback}$.<br />The aim is to define a category, denoted ${\bf Circ}$, again with objects being $B^n$ but with more general arrows, with operations similar to the ones we have defined for straight-line circuits, but with also an operation of feedback.<br /><br />Today I will just describe the arrows, which often I shall call components.<br /><br />An arrow of ${\bf Circ}$ from $B^m$ to $B^n$ consists of a finite graph $G$ whose edges are labelled by pairs of elements $(x,y)$ where $x=(x_1,x_2,\cdots ,x_m)\in B^m$, and $y=(y_1,y_2,\cdots ,y_n)\in B^n$. The vertices of the graph $G$ are called the ${\it states}$ of the component and the edges are called the ${\it transitions}$ of the component. The labels tell you what happens on the left and right hand wires of the component when a transition occurs. A ${\it behaviour}$ of the component is a path in the graph $G$ which yields also a sequence of left and right labels.<br /><br />Let's look at a simple example. Notice that we separate the left and right labels by a slash.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-huP6BYtYrJI/U-5C12hRo_I/AAAAAAAAB0M/wiENDsIdiuc/s1600/delay.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-huP6BYtYrJI/U-5C12hRo_I/AAAAAAAAB0M/wiENDsIdiuc/s1600/delay.jpg" height="171" width="320" /></a></div><br /><br />This is a two state component with four transitions but what should we call it? Let's see what kind of behaviour it has. Remember a behaviour is a path in the graph. The sequence of left-labels on a path may be thought of as a signal occuring on the left as the transitions occur; similarly the sequence of right-labels is the signal on the right.<br /><br />So here is a behaviour starting in state $0$:<br /><br />$0\xrightarrow{0/0}0\xrightarrow{1/0}1\xrightarrow{0/1}0\xrightarrow{0/0}0\xrightarrow{1/0}1\xrightarrow{0/1}0\xrightarrow{0/0}0$.<br /><br />The signal on the left for this behaviour is $0,1,0,0,1,0,0$ whereas the signal on the right is $0,0,1,0,0,1,0 $. You may notice that the signal on the right is the left signal ${\it delayed}$ by one step. In fact this component is a ${\it unit\; delay\; element}$.<br /><br />Why does it act that way? The reason is that the next state is determined by the left signal (the signal is remembered as state) and the next right signal is determined by the current state (which was the last left signal).<br /><br />You may wonder why I speak of left signal, right signal instead of input and output signals. It is crucial for what we do next that left and right do not necessarily correspond to input or output respectively.<br /><div><br /></div>Robert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-18458336497863429232014-08-01T02:35:00.004-07:002014-08-15T10:37:19.916-07:00Span(Graph) I<a href="http://rfcwalters.blogspot.it/2014/08/spangraph-ii-circuits-with-feedback.html">Next Span(Graph) post</a>.<br /><br /><br />I have decided to write a series of tutorial posts about Span(Graph) since I think this work has been unfairly neglected. I am simultaneously introducing a little TeX into the blog, at the encouragement of Keith Harbaugh.<br /><br />We begin with a simpler category as an algebra of straight line circuits which we will use as motivation for then in a later post introducing ${\bf Span}({\bf Graph})$.<br /><a name='more'></a><br /><br /><b>Straight-line Boolean circuits.</b><br /><br />Straightline Boolean circuits are constructed from components $and$, $or$, and $not$, connected by wires but without feedback. An example:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-H_kGkT8MfCE/U9t_sxC5wpI/AAAAAAAAByU/sLfAMRV-MVc/s1600/circuit.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-H_kGkT8MfCE/U9t_sxC5wpI/AAAAAAAAByU/sLfAMRV-MVc/s1600/circuit.jpg" height="134" width="320" /></a></div><br />There is an algebra in which such a circuit may be described as an expression. The algebra is a category with extra operations.<br />The objects of the category are sets of the form $B^n=\{0,1\}^n$, the arrows of the category are all the functions between these sets, composition is composition of functions. We may represent an arrow in the category $B^m\to B^n$ as a box with $m$ input wires and $n$ output wires.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/-gSX0vRn2yMo/U9vfwit8YuI/AAAAAAAAByk/YeW-FwRX72k/s1600/component.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-gSX0vRn2yMo/U9vfwit8YuI/AAAAAAAAByk/YeW-FwRX72k/s1600/component.jpg" height="100" width="200" /></a></div><br />Already in the picture above I have represented the basic components $and$, $or$ and $not$ as (special shaped) boxes with input and output wires.<br /><br />Now composition in the algebra corresponds to joining all the output wires of one component to all the input wires of the next. The algebra has another important operation and some constants.<br /><br />The product of arrows: Given $f:B^m\to B^n$ and $g:B^k\to B^l$ the product of $f$ and $g$, denoted $f\times g$ is an arrow from $B^{m+k}$ to $B^{n+l}$ which applied to an $m+k$ tuple $(x_1,x_2,\cdots,x_m,y_1,\cdots,y_k)$ gives $(f(x_1,x_2,\cdots,x_m),g(y_1,\cdots,y_k)) $. The picture of $f\times g$ is that of $f$ and $g$ side by side. In the case $m=2$, $n=3 $, $k=3 $, $l=1 $ we have $5$ inputs and $3$ outputs:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-of08d8ZRHbA/U9vf5Y4ax7I/AAAAAAAABys/XPnEJeMuK3c/s1600/product.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-of08d8ZRHbA/U9vf5Y4ax7I/AAAAAAAABys/XPnEJeMuK3c/s1600/product.jpg" height="177" width="200" /></a></div><br />The extra constants are operations on wires that allow the circuit to be built up. They are $1_B:B\to B$ (a single wire), $twist:B^2\to B^2$ (a twist of wires), $\Delta:B\to B^2$ (splitting of a wire) and the unique function $B\to B^0=1$ (the cutting of a wire). As functions the are defined by $1_B(x)=x$, $twist(x,y)=(y,x)$, $\Delta(x)=(x,x)$.<br /><br /><br />They are pictured as:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/-aRrEcHkNCBQ/U9vgDfHdGoI/AAAAAAAABy0/x6Q9HZYprFE/s1600/constants.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-aRrEcHkNCBQ/U9vgDfHdGoI/AAAAAAAABy0/x6Q9HZYprFE/s1600/constants.jpg" height="54" width="320" /></a></div><br /><br />Now consider dividing up of the circuit above as indicated in the picture below. The circuit is a composite of the parts between the dotted lines, each of which parts may be expressed using product in terms of the basic components and the constants.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-wQUQpRQI2o8/U9vgJLNQb-I/AAAAAAAABy8/oQWlI5pPEcc/s1600/circuit2.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-wQUQpRQI2o8/U9vgJLNQb-I/AAAAAAAABy8/oQWlI5pPEcc/s1600/circuit2.jpg" height="160" width="320" /></a></div><br /><br />The algebraic expression for the circuit is the composition of first $\Delta\times 1_B\times 1_B$, then $\neg\times twist \times1_B $, then $\vee\times \& $ and finally $\&$, that is (composing from the left)<br /><br />$(\Delta\times 1_B\times 1_B)(\neg\times twist \times 1_B )(\vee\times \&)(\&)$.<br /><br />The evaluation of this expression in the category yields a function $B^3\to B$ which is the input/output behaviour of the circuit. In fact the input/output function of this circuit is $f(x,y,z)=x\& (y\& z)$ and so the circuit is equal to a simpler circuit with two $and$ gates.<br /><br />There are various other things that could be said at this point but I will mention only briefly that (i) every arrow in this category is the input/output behaviour of a circuit, (ii) the extra operations and constants are exactly those of a category with products, (iii) the equations between expressions are exactly those which are valid in a category with products, plus the Boolean algebra equations satisfied by the basic components.<br /><br />The category we have described does not allow components with internal state, delay, feedback. It is to introduce these elements that we will introduce in the next post ${\bf Span}({\bf Graph})$.<br /><br />Robert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-1900396719055053412014-06-04T03:11:00.001-07:002014-08-14T13:08:51.567-07:00Steve Bloom's treeWhen Steve died in 2010 we said we would plant a tree in his memory at our mountain house. Here it is:<br /><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-ANb-hlj2dvw/U47w1AgbS5I/AAAAAAAABt4/oY-lYYbWAPQ/s1600/2014-06-02+19.20.26.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-ANb-hlj2dvw/U47w1AgbS5I/AAAAAAAABt4/oY-lYYbWAPQ/s1600/2014-06-02+19.20.26.jpg" height="300" width="400" /></a></div><br />Robert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-51182685926174106322010-08-11T06:01:00.000-07:002014-08-14T11:51:21.090-07:00Clive Selwyn Davis, 15 April 1916 – 29 October 2009I am rather out of touch with Australian mathematics and so I have just found out by chance that my MSc supervisor Clive Davis died in October last year. There is an <a href="http://www.austms.org.au/Publ/Gazette/2010/Mar10/ObitDavis.pdf">obituary</a> in the Australian Mathematical Society Gazette.<br />I learnt number theory from him, and remember well "the clarity, vigour and high standard of his lectures. His handwriting on the board was immaculate, and his brief<br />dictated final summary of each lecture was much appreciated." (quote from the obituary)<br />I wrote a Master's thesis on continued fractions in 1966 with him, and eventually even wrote a small book on number theory.<br />At that time, if I remember correctly, the first PhD in mathematics at the University of Queensland had yet to be awarded, so I went to Bernard Neumann's department at the ANU in Canberra, and changed direction, with Hanna Neumann as my supervisor. I had considered continuing number theory with Kurl Mahler, but my impression was that he was not very keen on having students.Robert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-49479129512082100702012-11-29T05:28:00.000-08:002014-08-14T11:49:47.256-07:00Videos of Lawvere's lectures January 2008, Como, ItalyI have put up all the videos of Bill's lectures in the Sala dei Nobel, Como, Italy, January 2008, at the following address (in the Como Category Theory Archive):<br /><a href="http://comocategoryarchive.com/Videos/videos.html">http://comocategoryarchive.com/Videos/videos.html</a>Robert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-37595682074261965592011-07-21T08:56:00.000-07:002014-08-14T11:48:32.459-07:00FranceI didn't go to the <a href="http://www.pims.math.ca/scientific-event/110717-ictc2">annual category theory</a> meeting, currently occurring in Vancouver - I am beginning to lose enthusiasm for intercontinental travel. I don't know how many times I have flown from Australia to Europe or America - too many times. And the internet has changed the need for so much travel. I do hope the organizers put up slides of the talks, and I would of course liked to have met old friends.<br /><br />Instead I made a car trip to France<br /><a name='more'></a>, a holiday, with my wife and daughter. We left Italy by Gottardo Tunnel, going to <a href="http://en.wikipedia.org/wiki/Hospices_de_Beaune">Beaune</a>, <a href="http://en.wikipedia.org/wiki/Chartres_Cathedral">Chartres</a>, Paris for a few days, then <a href="http://en.wikipedia.org/wiki/C%C3%B4te_de_Granit_Rose">Brittany</a> for a few days - including <a href="http://en.wikipedia.org/wiki/Carnac">Carnac</a>, returning through the <a href="http://en.wikipedia.org/wiki/Ch%C3%A2teau_d'Azay-le-Rideau">Loira Valley</a>, <a href="http://en.wikipedia.org/wiki/Cath%C3%A9drale_Saint-%C3%89tienne_de_Bourges">Bourges</a>, <a href="http://en.wikipedia.org/wiki/Royal_Monastery_of_Brou">Bourge-en-Bresse</a> and the Monte Bianco Pass. <br /><br />In terms of art and architecture the late 20th century comes out very badly in comparison with <a href="http://www.louvre.fr/llv/oeuvres/detail_departement.jsp?FOLDER%3C%3Efolder_id=1408474395181077&CURRENT_LLV_DEP%3C%3Efolder_id=1408474395181077&FOLDER%3C%3EbrowsePath=1408474395181077&bmLocale=en">Egypt</a>, the <a href="http://en.wikipedia.org/wiki/The_Lady_and_the_Unicorn">middle ages</a>,<br />and renaissance <a href="http://www.louvre.fr/llv/activite/detail_parcours.jsp?CONTENT%3C%3Ecnt_id=10134198673226925&CURRENT_LLV_PARCOURS%3C%3Ecnt_id=10134198673226925&bmLocale=en">Italy</a>.Robert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-76307635423660081712011-06-24T10:51:00.000-07:002014-08-14T11:47:49.440-07:00Ugo Montanari's talk 22 June 2011on the occasion of a celebration in Milan in honour of Gianni Degli Antoni.<br /><br />Ugo spoke about his latest work about a compositional calculus for Petri nets using the wire calculus of Sobocinski.<br /><br />I was disappointed that he didn't mention our work on connectors, which we have spoken about for years, including in joint projects, and which goes back to 1997 or even 1987.<br /><br /><a name='more'></a>In particular because the work of Sobocinski derives from ours. It arose in discussions with me (he even agreed that it was a joint project at the time), and lectures given by me, one at CT 2008 in Calais, where I emphasized the important difference between the parallel communication in Span(Graph) and that in conventional process algebras such as CSP and CCS. The <a href="http://www-lmpa.univ-littoral.fr/CT08/slides/Walters.ppt">slides are available at the CT site</a>.<br />Sobocinski actually carried out a student project with me in 1997 at the University of Sydney on Span(Graph) and was present at our talks at AMAST 1997 in Sydney, one of which was on representing Petri nets in Span(Graph). He refers to both our AMAST papers in his article in CONCUR 2010, including the following quote:<br />"The operations of the calculus presented in this paper are fundamentally different to those utilised in the aforementioned literature. Indeed, they are closer in nature to those of tile logic [13] and Span(Graph) [18] than to the operations of CCS. More recently, similar operations have been used by Reo [2], glue for component-based systems [8] and the wire calculus [30]. Indeed, in [17] Span(Graph) is used to capture the state space of P/T nets; this work is close in spirit to the translation from nets to terms given in this paper."<br /><br />I might say that even Arbab was influenced by us. He visited us in Como in 2000 and was talking about Manifold. I told him his connectors were not compositional. I believe his subsequent work on Reo was influenced by our discussions. Our paper in COORDINATION 2000, prior to Reo, used compositional connectors in modelling IWIM in CospanSpan(Graph).<br /><br />The point of this post is not casual.<br />The main contention in all our work is that concurrency theory has taken a wrong direction for thirty years, because of the choice of the wrong basic operations. We have said this in many forums including IFIP WG1.3 without apparently any reaction. For some more detailed comments see <a href="http://rfcwalters.blogspot.com/2009/06/old-posts-5-hundred-errors-of-ccs-begun.html">this post</a>.Robert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-27550394358305492732009-10-03T00:46:00.000-07:002014-08-14T11:47:10.290-07:00Aesop on the importance of having decisive leadershipLiving in Italy, in particular working in Italian academia, makes one think frequently of the problem of good government. There are <a href="http://66.71.178.156/materiali%20didattici/De%20Benedictis%202004/buongov.htm">famous frescoes</a> of Lorenzetti in the Comune di Siena called "ALLEGORIA DEL BUONO E CATTIVO GOVERNO".<br /><br />We are now at a critical point in the University of Insubria in the discussion of University reform. It looks as if we may finally have to implement the 25% reduction in courses proposed by the minister (for universities which until now had the minimum number of teachers) - though Italians tell me that I am naive to imagine such a definite result. Some of us believe that decisive leadership is crucial at this time. I would prefer wise leadership. Maybe even benevolent leadership.<br /><br />I suppose that is also naive. Consider the <a href="http://it.wikisource.org/wiki/Il_Re_Travicello">following story</a>. <br /><br /><br />THE FROGS WHO WISHED FOR A KING<br /><br />The Frogs were tired of governing themselves. They had so much freedom that it had spoiled them, and they did nothing but sit around croaking in a bored manner and wishing for a government that could entertain them with the pomp and display of royalty, and rule them in a way to make them know they were being ruled. No milk and water government for them, they declared. So they sent a petition to Jupiter asking for a king.<br /><br />Jupiter saw what simple and foolish creatures they were, but to keep them quiet and make them think they had a king he threw down a huge log, which fell into the water with a great splash. The Frogs hid themselves among the reeds and grasses, thinking the new king to be some fearful giant. But they soon discovered how tame and peaceable King Log was. In a short time the younger Frogs were using him for a diving platform, while the older Frogs made him a meeting place, where they complained loudly to Jupiter about the government.<br /><br />To teach the Frogs a lesson the ruler of the gods now sent a Crane to be king of Frogland. The Crane proved to be a very different sort of king from old King Log. He gobbled up the poor Frogs right and left and they soon saw what fools they had been. In mournful croaks they begged Jupiter to take away the cruel tyrant before they should all be destroyed.<br /><br />"How now!" cried Jupiter "Are you not yet content? You have what you asked for and so you have only yourselves to blame for your misfortunes."Robert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-31842617965315531662007-02-21T22:20:00.000-08:002014-08-14T11:45:58.916-07:00New addressI have finally, after being in Italy for more than 8 years, managed<br />to get myself a regular homepage at the University here in Como.<br />To see my future blogs go to that page:<br /><a href="http://dscpi.uninsubria.it/Walters"></a><a href="http://dscpi.uninsubria.it/staff/Walters">http://dscpi.uninsubria.it/staff/Walters</a><br /><br />Robert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.com1tag:blogger.com,1999:blog-7446594.post-41748202623876722072013-12-11T00:07:00.000-08:002014-08-14T11:44:53.113-07:00Tributes to Aurelio CarboniI have placed in the Como Category Archive some <a href="http://comocategoryarchive.com/Archive/conferences/aurelio-carboni/tributes/">articles</a> about Aurelio Carboni, which are based on lectures given at the <a href="http://math.unipa.it/metere/Aurelio2013/index.html">conference in memory of Aurelio</a>, June 2013, in Milan. They will be appearing in a volume of the journal Protagora, edited by Fabio Minazzi of the University of Insubria, Varese.Robert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.com1tag:blogger.com,1999:blog-7446594.post-1140075134526393212006-02-15T23:26:00.000-08:002014-08-14T11:44:11.656-07:00History of an equation - (1 tensor delta)(nabla tensor 1)=(nabla)(delta)This is a personal history of the equation<br />(1 tensor delta)(nabla tensor 1)=(nabla)(delta)<br />now called the <i>Frobenius equation</i>, or by computer scientists S=X.<br /><br /><b>1983 Milano</b> Worked with Aurelio Carboni in Milano, and later in Sydney, on characterizing the category of relations.<br /><b>1985</b> <b>Sydney</b> We submitted to JPAA on 12th February the paper eventually published as<br /><i>A. Carboni, R.F.C. Walters, Cartesian bicategories I, Journal of Pure and Applied Algebra 49 (1987), pp. 11-32.</i> <br />The main equation was the Frobenius law, called by us<i> discreteness</i> or (D) (page 15).<br /><b>1985 Isle of Thorns, Sussex</b>: Lectured on work with Carboni concentrating on importance of this new equation - replacing Freyd's "modular law". Present in the audience were Joyal, Anders Kock, Lawvere, Mac Lane, Pitts, Scedrov, Street. I asked the audience to state the modular law, Joyal responded with the classical modular law, Pitts finally wrote the law on the board, but mistakenly. Scedrov said "So what?" to the new equation and "After all, the new law is equivalent to the modular law". Nobody ventured to have seen the equation before.<br />(I asked Freyd in Gummersbach in 1981 where he had found the modular law, and he replied that he found it by looking at all the small laws on relations involving intersection, composition and opposite, until he found the shortest one that generated the rest. We believe that this law actually occurs also in Tarski,<br /><i>A. Tarski, On the Calculus of Relations, J. of Symbolic Logic 6(3), pp. 73-89 (1941)</i><br />but certainly in the book "Set theory without variables" by Tarski and Givant, though not in the central role that Freyd emphasised<i>.</i>)<br />At this Sussex meeting Ross Street reported on his discovery with Andre Joyal of braided monoidal categories (in the birth of which we also played a part - lecture by RFC Walters, Sydney Category Seminar, On a conversation with Aurelio Carboni and Bill Lawvere: the Eckmann-Hilton argument one-dimension up, 26th January 1983). This disovery was a major impulse towards the study of geometry and higher dimensional categories.<br /><b>1987 Louvain-la-Neuve<i> </i>Conference</b> I lectured on well-supported compact closed categories - every object has a structure satisfying the equation S=X, plus diamond=1. Aurelio spoke about his discovery that adding the axiom diamond=1 to the commutative and Frobenius equations characterizes commutative separable algebras, later reported in<br /><i>A. Carboni, Matrices, relations, and group representations, J. Alg. 136:497–529,1991</i><br />(submitted in 1988). <br />After Aurelio's lecture Andre Joyal stood up and declared that "these equations will never be forgotten". At this, Sammy Eilenberg rather ostentatiously rose and left the lecture - perhaps the equation occurs already in Cartan-Eilenberg?<br />Andre pointed out to us the geometry of the equation - drawing lots of 2-cobordisms.<br />During the conference in a discussion in a bar with Joyal, Bill Lawvere and others, Bill recalled that he had written equations for Frobenius algebras in his work<br /><i>F.W. Lawvere, Ordinal Sums and Equational Doctrines, Springer Lecture Notes in Mathematics No. 80, Springer-Verlag (1969), 141-155.</i><br />The equations did not incude S=X, diamond=1, or symmetry, but the equation S=X is easily deducible (see Carboni, "Matrices, ...", section 2). Bill's interest, as ours, was to discover a general notion of self-dual object. In Freyd's work there is instead the rather non-categorical assumption of an involution satisfying X^opp=X.<br /><b>2004 Joachim Kock's book</b> I jump to this because it enables me to discuss quickly later developments. The fronticepiece of the book<br /><i>Joachim Kock, Frobenius algebras and 2D topological quantum field theories, Cambridge University Press 2004</i><br />is a picture of our equation S=X in the geometric form pointed out to us by Andre Joyal in 1987, the form which suggests the name S=X (maybe Z=X might be more suggestive but I prefer S=X). Kock discusses Lawvere's work on page 121, but, unaware of our introduction of the equation in 1985, he states that<br />"The first explicit mention of the Frobenius relation, and a proof of 2.3.4, were given in 1991 by Quinn" in<br /><i>Frank Quinn, Lectures on axiomatic topoogical quantum field theory, in Geometry and quantum field theory, American Mathematical Society, 1995.</i><br /><i></i>Kock's very pleasant book is a readable account of the relation between the algebra and the geometry of the Frobenius equation. It does not describe the physical intuition behind topological field theory, a concept introduced by Witten in 1988 in<br /><i>Edward Witten, Topological quantum field theory, Communications in mathematical physics, 117, 353-38, 1988. </i><br /><br />For another account of the history of category theory from an Australian point of view see the article<br /><i>Ross Street, An Australian conspectus of higher categories, Institute for Mathematics and Applications Summer Program: n-categories: Foundations and Applications, June 2004.</i><br />Curiously, this article does not mention our discovery of the Frobenius equation.Robert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-1140110068482898032006-02-16T09:13:00.000-08:002014-08-14T11:43:57.176-07:00My interest in monoidal bicategories<b>An old article first posted in 1997</b><br /><b></b><br /><b>My interest in monoidal bicategories.</b><br /><b>RFC Walters 7th April 1997</b><br /><br /><b>1966-70</b> In my PhD thesis (ANU) about category theory and universal algebra I used the 2-category structure of Cat to define things and hence became interested in pasting cells.<br /><b>1970</b> I visited Mac Lane (Chicago) as research associate and discovered that the category PA of presheaves on a small category is 'total' which lead to a collaboration with Ross Street beginning in 1970 of the 2-categorical properties of yoneda yA:A->PA. We were trying to characterize Sets in Cat but in analogy to studying 2 in Sets by looking at arrows A->PB (here PB means subsets of B) we studied functors A->PB.<br /><b>1974</b> I spoke on his work at a conference at UNSW organized when Peter Freyd was here by Max Kelly. The paper appeared much later in "Yoneda structures". The beginning of the study of Mod and Rel was already there.<br /><b>1980</b> I visited Milan and discovered that the sheaf condition can be expressed in terms of Cauchy completeness of categories enriched over a bicategory of 'relations' - this work appeared in Cahiers. A group of us studied categories enriched over bicategories, and bimodules between them. We looked at properties which lifted from the base bicategory to the bicategory of bimodules.<br /><b>1982</b> Lifting the tensor product lead to my idea with Lawvere and Carboni that the classical treatment of this in terms of symmetry could be explained in terms of a tensored one-object bicategory and a Eckman-Hilton argument - I gave a lecture on this on 26th January 1983 which inspired Ross to discover braided monoidal categories with Joyal (whose motivation was different).<br /><b>1983</b> I began the study with Carboni of Rel as a monoidal bicategory in Milan December 1983. It was completed in January 1985. Aurelio had previously done work in the direction of Freyd on relations regarding Rel as a category and using the mysterious 'modular law'.<br /><b>1985</b> I believe I lectured on Rel at Sussex. The paper had been submitted some time before and Scedrov had written a report recommending rejection, but it was eventually accepted. A third strand was that Mike Johnson and I had begun work (ask Mike when he began as my student) on an alternative version of the n-category generated by an n-simplex - the higher associative laws. (I had suggested to him originally a different problem: describing cech cocyles as categories enriched over an n-category.)<br /><b>1985</b> Mike and I presented this at Bangor. At around that point I began to be interested in computer science. I gave a couple of lectures in the Sydney Category Seminar. I occasionally tried to get divert Mike's attention in this direction. That took me off into distributive, extensive categories, only to return to monoidal bicategories (now with feedback) in 1994.<br /><b>1992</b> I began the study of concurrency with Nicoletta Sabadini.<br /><b>1994</b> After a visit of Bloom, seeing his work on iteration theories I gave a lecture at the Sydney Half-hour Seminar on machines as arrows (29th April). Since then Giulio Katis, Nicoletta Sabadini and I have worked extensively on this idea, one result being the 1997 paper "Bicategories of Processes". An earlier version of the paper was written presented at CATS '94. The work with Henry Weld on circuits, and the earlier work with Wafaa Khalil on 'functional processes' have been very influential - in fact there is an exercise in the 1992 Cambridge version on my book which appropriately interpreted is about the monoidal bicategory of Elgot automata.Robert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.com1tag:blogger.com,1999:blog-7446594.post-1165569145716283402006-12-08T01:10:00.000-08:002014-08-14T11:43:25.715-07:00Formiche mentaliI have come to the conclusion that many scientific works deserves the name formiche mentali. That is to say, complications which prevent thought.<br />If I have the courage I will give some examples.<br /><a href="http://photos1.blogger.com/x/blogger/869/459/1600/750913/formichementale.jpg"><img alt="" border="0" src="http://photos1.blogger.com/x/blogger/869/459/320/245221/formichementale.jpg" style="cursor: hand; display: block; margin: 0px auto 10px; text-align: center;" /></a><br />The quadro is by Dino Buzzati, from a series of fictional "ex voto".Robert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-85071937919842176252009-06-23T11:08:00.000-07:002014-08-14T11:42:54.083-07:00Old posts 1: My interest in monoidal bicategories (7th April 1997)I am gradually importing old posts from my <a href="http://dscpi.uninsubria.it/staff/Walters">department pages</a>.<br />I fear that very shortly I will lose my departmental page at the University of Insubria and hence I am starting to move my old posts to this blog spot. The department which was originally formed at request as a kernel of a possible Arts faculty in Como seems to have lost support at all levels (and is under attack by other departments) - this all in the context of university reforms. I regret the situation since I think this department could have been an interesting and productive collaboration, of considerable value to Como.<br />An old article first posted in 1997<br /><br />My interest in monoidal bicategories.<br />RFC Walters 7th April 1997<br /><br />1966-70 In my PhD thesis (ANU) about category theory and universal algebra I used the 2-category structure of Cat to define things and hence became interested in pasting cells.<br />1970 I visited Mac Lane (Chicago) as research associate and discovered that the category PA of presheaves on a small category is 'total' which lead to a collaboration with Ross Street beginning in 1970 of the 2-categorical properties of yoneda yA:A->PA. We were trying to characterize Sets in Cat but in analogy to studying 2 in Sets by looking at arrows A->PB (here PB means subsets of B) we studied functors A->PB.<br />1974 I spoke on his work at a conference at UNSW organized when Peter Freyd was here by Max Kelly. The paper appeared much later in "Yoneda structures". The beginning of the study of Mod and Rel was already there.<br />1980 I visited Milan and discovered that the sheaf condition can be expressed in terms of Cauchy completeness of categories enriched over a bicategory of 'relations' - this work appeared in Cahiers. A group of us studied categories enriched over bicategories, and bimodules between them. We looked at properties which lifted from the base bicategory to the bicategory of bimodules.<br />1982 Lifting the tensor product lead to my idea with Lawvere and Carboni that the classical treatment of this in terms of symmetry could be explained in terms of a tensored one-object bicategory and a Eckman-Hilton argument - I gave a lecture on this on 26th January 1983 which inspired Ross to discover braided monoidal categories with Joyal (whose motivation was different).<br />1983 I began the study with Carboni of Rel as a monoidal bicategory in Milan December 1983. It was completed in January 1985. Aurelio had previously done work in the direction of Freyd on relations regarding Rel as a category and using the mysterious 'modular law'.<br />1985 I believe I lectured on Rel at Sussex. The paper had been submitted some time before and Scedrov had written a report recommending rejection, but it was eventually accepted. A third strand was that Mike Johnson and I had begun work (ask Mike when he began as my student) on an alternative version of the n-category generated by an n-simplex - the higher associative laws. (I had suggested to him originally a different problem: describing cech cocyles as categories enriched over an n-category.)<br />1985 Mike and I presented this at Bangor. At around that point I began to be interested in computer science. I gave a couple of lectures in the Sydney Category Seminar. I occasionally tried to get divert Mike's attention in this direction. That took me off into distributive, extensive categories, only to return to monoidal bicategories (now with feedback) in 1994.<br />1992 I began the study of concurrency with Nicoletta Sabadini.<br />1994 After a visit of Bloom, seeing his work on iteration theories I gave a lecture at the Sydney Half-hour Seminar on machines as arrows (29th April). Since then Giulio Katis, Nicoletta Sabadini and I have worked extensively on this idea, one result being the 1997 paper "Bicategories of Processes". An earlier version of the paper was written presented at CATS '94. The work with Henry Weld on circuits, and the earlier work with Wafaa Khalil on 'functional processes' have been very influential - in fact there is an exercise in the 1992 Cambridge version on my book which appropriately interpreted is about the monoidal bicategory of Elgot automata.Robert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-19818291976600780932009-06-24T05:35:00.000-07:002014-08-14T11:42:33.679-07:00Old posts 2: History of an equation - (1 tensor delta)(nabla tensor 1)=(nabla)(delta) (15 February 2006)This is a personal history of the equation (1 tensor delta)(nabla tensor 1)=(nabla)(delta) now called the Frobenius equation, or by computer scientists S=X. <br /><br />1983 Milano Worked with Aurelio Carboni in Milano, and later in Sydney, on characterizing the category of relations.<br />1985 Sydney We submitted to JPAA on 12th February the paper eventually published as A. Carboni, R.F.C. Walters, Cartesian bicategories I, Journal of Pure and Applied Algebra 49 (1987), pp. 11-32. <br />The main equation was the Frobenius law, called by us discreteness or (D) (page 15). 1985 Isle of Thorns, Sussex: Lectured on work with Carboni concentrating on importance of this new equation - replacing Freyd's "modular law". Present in the audience were Joyal, Anders Kock, Lawvere, Mac Lane, Pitts, Scedrov, Street. I asked the audience to state the modular law, Joyal responded with the classical modular law, Pitts finally wrote the law on the board, but mistakenly. Scedrov said "So what?" to the new equation and "After all, the new law is equivalent to the modular law". Nobody ventured to have seen the equation before.<br />(I asked Freyd in Gummersbach in 1981 where he had found the modular law, and he replied that he found it by looking at all the small laws on relations involving intersection, composition and opposite, until he found the shortest one that generated the rest. We believe that this law actually occurs also in Tarski, A. Tarski, On the Calculus of Relations, J. of Symbolic Logic 6(3), pp. 73-89 (1941) but certainly in the book "Set theory without variables" by Tarski and Givant, though not in the central role that Freyd emphasised.)<br />At this Sussex meeting Ross Street reported on his discovery with Andre Joyal of braided monoidal categories (in the birth of which we also played a part - lecture by RFC Walters, Sydney Category Seminar, On a conversation with Aurelio Carboni and Bill Lawvere: the Eckmann-Hilton argument one-dimension up, 26th January 1983). This disovery was a major impulse towards the study of geometry and higher dimensional categories.<br />1987 Louvain-la-Neuve Conference I lectured on well-supported compact closed categories - every object has a structure satisfying the equation S=X, plus diamond=1. Aurelio spoke about his discovery that adding the axiom diamond=1 to the commutative and Frobenius equations characterizes commutative separable algebras, later reported in A. Carboni, Matrices, relations, and group representations, J. Alg. 136:497–529,1991 (submitted in 1988). <br />After Aurelio's lecture Andre Joyal stood up and declared that "these equations will never be forgotten". At this, Sammy Eilenberg rather ostentatiously rose and left the lecture - perhaps the equation occurs already in Cartan-Eilenberg? Andre pointed out to us the geometry of the equation - drawing lots of 2-cobordisms. During the conference in a discussion in a bar with Joyal, Bill Lawvere and others, Bill recalled that he had written equations for Frobenius algebras in his work F.W. Lawvere, Ordinal Sums and Equational Doctrines, Springer Lecture Notes in Mathematics No. 80, Springer-Verlag (1969), 141-155.<br />The equations did not incude S=X, diamond=1, or symmetry, but the equation S=X is easily deducible (see Carboni, "Matrices, ...", section 2). Bill's interest, as ours, was to discover a general notion of self-dual object. In Freyd's work there is instead the rather non-categorical assumption of an involution satisfying X^opp=X.<br />2004 Joachim Kock's book I jump to this because it enables me to discuss quickly later developments. The fronticepiece of the book Joachim Kock, Frobenius algebras and 2D topological quantum field theories, Cambridge University Press 2004 is a picture of our equation S=X in the geometric form pointed out to us by Andre Joyal in 1987, the form which suggests the name S=X (maybe Z=X might be more suggestive but I prefer S=X). Kock discusses Lawvere's work on page 121, but, unaware of our introduction of the equation in 1985, he states that "The first explicit mention of the Frobenius relation, and a proof of 2.3.4, were given in 1991 by Quinn" in Frank Quinn, Lectures on axiomatic topoogical quantum field theory, in Geometry and quantum field theory, American Mathematical Society, 1995. Kock's very pleasant book is a readable account of the relation between the algebra and the geometry of the Frobenius equation. It does not describe the physical intuition behind topological field theory, a concept introduced by Witten in 1988 in Edward Witten, Topological quantum field theory, Communications in mathematical physics, 117, 353-38, 1988. <br /><br />For another account of the history of category theory from an Australian point of view see the article Ross Street, An Australian conspectus of higher categories, Institute for Mathematics and Applications Summer Program: n-categories: Foundations and Applications, June 2004. <br /><br />Curiously, this article does not mention our discovery of the Frobenius equation.Robert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.com0tag:blogger.com,1999:blog-7446594.post-75706681519450604542009-06-24T05:43:00.000-07:002014-08-14T11:42:10.817-07:00Old posts 4: The hundred errors of CCS - (Begun 19 December 2007, last addition 8 September 2008)(with Nicoletta Sabadini)<br /><br />The hundred and one errors of CCS, Comment commenced 19 December 2007<br /><br />I have been thinking a bit more about CCS. I agree that processes are fundamental.<br />A mathematical theory of such is of great importance, perhaps equal to the importance of a theory of functions. One of the main issues is the parallel composition of processes.<br /><br />This means that the attempts to develop such a theory should be subject to the fiercest debate. Any mistake at the beginning would lead to endless confusion.<br /><br />In this spirit I would like to argue that there are many misdirections taken in the theory proposed by Robin Milner. Perhaps not 100 mistakes but many. In this page I would like to record my opinion. So far I have described only 20 errors (by 30th December 2007) but the page will gradually be updated.<br /><br />I am very happy to receive corrections and comments on my list: in particular with respect to my misconceptions about CCS, but also with regarding divergence of opinion about the nature of processes.<br /><br />I can immagine that this list may be regarded as solely negative; "it is easy to criticize".<br />Instead it should be understood as taking the programme of Milner and others seriously; an attempt to help in understanding the fundamental notion of "process", and parallelism; a program initiated and researched mainly by the concurrency community.<br /><br />Mistake 1. The parallel communicating composition of processes should not involve broadcast as the basic communication method.<br />One consequence of broadcast is that parallel composition (even of two atomic processes) needs to be complicated in order to be associative. <br /><br />Mistake 2. A theory of processes should begin with a clear model. <br />Syntax should come second. This applies even at the stage of developing a theory of processes.<br /><br />Mistake 3. Interleaving is a mistake.<br /><br />Mistake 4. In CCS it is impossible to say that a process returns to the same state it was in previously. This means that it is impossible to describe even finite automata.<br />Added 8 September 2008 Suppose we regard CCS expressions as states of processes. Then it would seem that we could describe automata by expressions, for example the process p which is the solution of p=ap would give rise to the automaton with one state p, and one transition a:p->p. Let's look at processes q and r<br />which are the soluions of q=aaq and r=a(ar+nil). The automata corresponding to q and r are isomorphic: <br />a:q->aq, a:aq->q<br />a:r->(ar+nil), a:(ar+nil)->r.<br />However the two automata corresponding to aq and ar are NOT isomporphic.<br />The automaton corresponding to aq has two states:<br />a:aq->q, a:q->q<br />The automaton corresponding to r has three states:<br />a:ar->r,a:r->ar+nil, a:ar+nil->r. <br /><br />Mistake 5. In CCS there is no distinction between channel and signal on a channel.<br />What does the handshake - channels or signals?<br /><br />Mistake 6. The geometry of processes should be explicit and distinct from states of processes.<br /><br />Mistake 7. In CCS there is no distinction between fx1:AxA->AxA and f:A->A.<br />As a result there is no distinction between fxg:AxA->AxA and gf:A->A such that gf=fg.<br />Hence any meaning of causality is lost. <br /><br />Mistake 8. P || Q should not be equal to Q || P; at most they should be isomorphic.<br /><br />Mistake 9. There is no distinction between non-communicating parallel and communicating parallel.<br /><br />Mistake 10. Composition should hide the interface of communication.<br /><br /><br />Mistake 11. Lack of Zero communication. There is a single tau, but it does not play the role of indicating that two processes have zero communication.<br /><br />Mistake 12. n processes should be able to synchronize in a single action. This is related to the following:<br /><br />Mistake 13. There should be processes for each channel which are the identity with respect to parallel <br />- that transmit at the same time as they receive.<br /><br />Mistake 14. The simplest examples of processes are functions. <br />So the category of sets and functions should be an algebra of processes. It has sequential and parallel composition which are related through a distributive law.<br /><br />Mistake 15. The relation between sequential and parallel should be a distributive law/exactness condition.<br /><br />Mistake 16. The operation of hiding a channel has the effect of preventing action, not just hiding.<br />This seems to me to be unphysical, very difficult to implement. Seems a purely mathematical operation.<br /><br />Mistake 17. The only notion of cycle is through recursion. Real processes cycle through returning to the same state. <br />Recursion is a different phenomenon, also important. An algebra of processes should have both.<br /><br />Mistake 18. A process which consists of an infinite number of processes in parallel may be defined.<br /><br />Mistake 19. The meaning of a CCS term is given by a behaviour, not a process.<br />A process should have a behaviour, but not just be a behaviour.<br /><br />Mistake 20. Programs should be expressions in the algebra of processes. Instead, in process algebras programs come first (that is, the free algebra comes first), and processes are defined to be elements of a quotient algebra.<br /><br />Expanded comment on Mistakes 4 and 17., 10 April 2008<br />My first problem with a compositional semantics of CCS in terms of automata (abstract labelled transition systems) is as follows:<br /><br />If you only want automata up to bisimulation you can do it because every automaton is bisimilar to its unfolding tree - but in this case you never can say you returned to the same state - which is one of my basic requisites for state.<br /><br />Instead a real compositional semantics in terms of transition systems/automata would involve:<br />(i) defining the automaton A(t) (with initial state) corresponding to a term t by developing rules, (states being terms), (I notice that you only get reachable automata that way)<br />and<br />(ii) defining abstract operations on automata, and<br /><br />(iii) proving that A preserves operations from terms to automata.<br /><br />If you try to do that then a parallel operation on automata is plausible.<br />The one I have more difficulty with is instead P+Q.<br />The only abstract operation on automata I can imagine is gluing the two automata only on the initial state. There is no information to form some kind of union.<br /><br />However the non-initial part of A(P+Q) can't be the disjoint because at the level of terms we can't distinguish between some identical terms and not others.<br />How can we tell if states as terms are equal without examining the terms?<br />The usual LTS of P+Q is not the abstract operation on automata discussed above.<br /><br />It seems to me you are forced to look at trees instead of automata - that is to deny that you can return to the same state. OR you take automata modulo bisimulation which is the same thing.<br />In my view, trees and bismulation may be used (and perhaps originated so) to fix a <br />broken theory. Of course bisimultaion is fundamental as an adjunction to a correct theory. <br /><br />After writing the above I found in Winskel and Nielsen (Models for Concurrency, 1993) some similar remarks, though they do not arrive at the same conclusions.<br /><br />"Unfortunately the relationship between the transition systems obtained denotationally and operationally is a little obscure. There are several mismatches.<br />One is that the categorical sum makes states of the two components of a sum disjoint, a property which cannot be shared by the transition system of the operational semantics, essentially because of incidental identifications of syntax. Furthermore, the transition system for recursive processes can lead to transition systems with transitions back to the initial state. As we have<br />seen this causes a further mismatch between the denotational and operational treatment of sums. Indeed the denotational treatment of recursive processes will lead to acyclic transition systems, which are generally not obtained with the present operational semantics. Less problematic is the fact that from the very way it is defined the transition systems obtained operationally must consist only of reachable states and transitions. This property is not preserved by the categorical operation of restriction used in the denotational semantics.<br />Of course, if we use a coarser relation of equivalence than isomorphism then the two semantics can be related. In the next section, it will be shown that, given any term, there is a strong bisimulation (in the sense of [55]) between the reachable states of the transition system obtained denotationally and those got from the operational semantics.<br /><br />[55] Milner,A.R.G., Communication and concurrency, Prentice Hall,1989."<br /><br />Mistake 21. (5 May 2008) There is nothing canonical about the parallel operation. <br />There have been many suggested alternatives, also non-canonical.<br />At this level of abstraction in mathematical development we seek canonicity. <br /><br />Mistake 22. (5 May 2008) The fact that CCS is built on Kleene's algebra of behaviours, has permitted the development of an algebra of behaviours without systems. <br />This is already a conceptual error in Kleene's theorem - which should express the fact that actual behaviour is a morphism of algebras from systems to possible behaviours, together with the fact that every system is generated in the algebra of systems from some particularly simple ones.<br />The problem with Kleene is that not all automata are given by Kleene expressions.<br />This has permitted a looseness of ideas in CCS, namely that we are only talking about systems up to bisimulation. Which looseness has of course been justified philosophically.<br /><br />Mistake 23. (5 May 2008) In my view the principal error (and the chief obstacle to my understanding) of CCS has been the reliance on giving meaning to expressions by means of the primitive methods of SOS.<br />If instead a system had been associated compositionally to a CCS expression, "operational semantics" would then be straightforward.<br />It is a delusion to immagine that SOS gives meaning. <br /><br />Mistake 24. (28 May 2008) The tau action seems to me to be a bad idea, because it is not just the absence of a signal on the boundary, but a positive signal which prevents other synchronizations occurring simultaneously.<br /><br />Mistake 25. (4 June 2008) A big problem is the lack of appreciation of reflexive graphs, that is of the reflexive transition of a state. <br />The reflexive edge means lack of communication, not like tau which means positive communication of internal transition.<br />The reflexive edge allows true concurrency. Tau forces interleaving.<br />In the presence of reflexive transition there are two possible meanings for restriction, <br />that of CCS which prevents transmission of signals externally but also prevents some internal transitions, and an alternative, the projection of signals onto the reflexive edge, which is a pure restriction of transmission of signals (the physical cutting of a channel).<br /><br />Mistake 26. (29 July 2008)<br />In CCS there are no names for entities, just names for states of entities.<br />This follows from a decision made by Milner not to distinguish states and agents:<br />From Communication and Concurrency, Prentice Hall 1989, pages 18,19: "We may loosely think of agent expressions like C and C'(x) as standing for the different possible states of an agent; in general there will be many states which an agent may traverse. <br />Rather than distinguishing between two concepts - agent and state - we find it convenient to identify them, so that both agent and state will always be understood to mean an agent in some state."<br />"Truth will sooner come out of error than from confusion." - F. BaconRobert Waltershttp://www.blogger.com/profile/11168659017114792898noreply@blogger.com0