User talk:Allan McInnes/Archive2

Archive of User talk:Allan McInnes covering 2005-05-14 through 2006-06-30

Hi

Thank you for a nice talk. You are very nice to talk with. I am an old retired guy. I did lots of computer science stuff years ago, but moved away from it over the last couple decades. I mostly wrote stuff in assembly for scientific instrumentation and government cold war projects. But my real interest has always been in artificial intelligence. Can I strike up a conversation with you on something of mutual interest? What is the current hot topic in computer science acedemia from your point of view? What do you think of predictions concerning the point in time when designed intelligence equals biologically evolved intelligence? WAS 4.250 00:20, 15 May 2006 (UTC)

Well, CS is a pretty broad field, so picking just one "hot" topic would be tough. I can, however, give you my own personal view of what I consider to be a challenging area, and one which is receiving a lot of attention at present. That area is the development of a general theory for understanding concurrent and distributed systems, and of languages and tools to support building such systems. This area has obvious importance to the internet, but is also likely to be critical in other fields as well due to the growing ubiquity of embedded microprocessors and mesh networks. So-called ubiquitous computing is necessarily both concurrent and distributed.

Regarding "predictions concerning the point in time when designed intelligence equals biologically evolved intelligence", I'm assuming that you are referring to the technological singularity. To be honest, I'm skeptical that we're ever likely to design an intelligence — in my opinion the structure of the kinds of complex systems that humans are cognitively capable of reliably designing (modular and with low coupling between subsystems) is very different from the structure of the systems I think are likely to give rise to intelligence (highly coupled and highly self-referential). That is not to say that I think artificial intelligence is impossible. Rather that I doubt it will be "designed" in the same way that, say, a microprocessor is. It seems more likely to me that such intelligences will be evolved (albeit artificially). I'm not sure we really know how to do that yet though. However, if you grant the assumption that artificial intelligences will somehow be developed, then I think the singularity is a fairly plausible future. --Allan McInnes (talk) 02:38, 15 May 2006 (UTC)

The first paragraph, I'll deal with tomorrow. The second I'll respond to now. I think the key is a seed that rapidly learns to learn better in an unbounded way; noting that the universe itself is a seed that has learned to learn in a terribly slow fashion. I think of the internet as a (but maybe not the) pre-singularity containing a variety of evolving primordial entities exchanging genes and aquiring new genes from many methods including from the mind of humans who are collectively the mother hen hatching this egg (while in the bowels of various intelligence agencies, specific attempts at totally controllable pre-singularities are being attempted). To my mind the big question is when (2020? 2070?). In 1980 I predicted (to myself) that the "crux point" (as I called it then) would occur no earlier than 1995 and no later than 2010. I still have a couple years... WAS 4.250 15:55, 15 May 2006 (UTC)

My response to:

• Concurrency (computer science)
• Distributed computing
• Mesh networks
• Ubiquitous computing

is:

• Nanorobotics
• Microbotics
• Swarm robotics
• Smartdust
• Finite state machine
• Swarm intelligenceWAS 4.250 17:15, 16 May 2006 (UTC)

I'm a little unclear on the meaning of your response. Do you mean to suggest that these are other hot topics? Or that the topics I listed have application to swarm systems? If the latter, then I agree with you 100%. In fact, this paper is specifically about how concurrency theory (specifically process calculi) might be applied to understanding the behavior of swarm-based space missions. --Allan McInnes (talk) 17:31, 16 May 2006 (UTC)

Both this paper and process calculi seem oriented towards theoretical computer science. Is that your current interest? Is that what you feel will prove most interesting or critical or important in computer science? Earlier you said "That is not to say that I think artificial intelligence is impossible. Rather that I doubt it will be "designed" in the same way that, say, a microprocessor is. It seems more likely to me that such intelligences will be evolved (albeit artificially)." and I agree. But evolving a highly complicated software suite and using theory to design the end product are at opposite ends of the spectrum. Everything we know in the world of great complexity that works has evolved from simple to complex. I don't think you can design your way there. I think you have to grow your way there. So "a formal model of ANTS" would be a waste of money, right? The nature of emergent behavior would seem to rule out even being able to ask to right questions. If it is complicated enough to have interesting and useful emergent behavior, you would have to run it to see what it does, right? What do you think? I think people who manage these programs want assurances that are not possible. WAS 4.250 20:30, 16 May 2006 (UTC)

Theory and practice

My current interest does indeed lie in theoretical computer science. But what I am interested in doing is making the theoretical useful in practice. I think that the theory of concurrency is interesting and critical and important for those parts of computer science that deal with networked and distributed systems, and ubiquitous computing. I believe that the same theory can be applied to swarm systems, in order to verify that the emergent behavior produced by a swarm has the properties we desire — note that this does not imply that we could necessarily "design" (from first principles) a swarm to have certain properties, but rather that we could verify that a given swarm configuration will do what we want (the difference here is between computing a solution, and verifying that an existing solution is correct... the latter is much simpler). Given a test for correctness (i.e. emergent behavior has desired properties), it may well be possible to evolve a swarm design using classical genetic algorithm techniques — the correctness criteria become a type of objective function or fitness function. Such work has already been done for very simple sequential and logic programs (see here), and could presumably be extended to concurrent systems. As for the need to "run it to see what it does", much of the current work in concurrency theory involves figuring out what we can infer about a system without running it, and how to infer other things by "executing" an abstracted model of the system. --Allan McInnes (talk) 20:56, 16 May 2006 (UTC)

I don't know much about theoretical computer science so this conversation may limp to a close;

That's a shame — this little conversation has given me considerable food for thought. --Allan McInnes (talk) 03:10, 17 May 2006 (UTC)

Ahhh good; then we are both enjoying this. WAS 4.250 17:25, 17 May 2006 (UTC)

but I know a bit of physics and cognitive science and applied computer science and I try to follow nanotechnology somewhat.

Well, feel free to steer the conversation back onto things in which you have greater knowledge or interest. --Allan McInnes (talk) 03:10, 17 May 2006 (UTC)

OK. WAS 4.250 17:25, 17 May 2006 (UTC)

What is "the theory of concurrency"? Aren't there many?

By "the theory of concurrency" I meant "the theoretical study of concurrency". Sorry for not being more precise in my use of words. You are correct that there are many "theories of concurrency". Although, in recent years there's been a lot of work put into reconciling them all. Ultimately, it seems like we might be able to reach a point where there is one unified "theory", but many possible notations for expressing different aspects of that theory. That's all pie-in-the-sky at the momment though. --Allan McInnes (talk) 03:10, 17 May 2006 (UTC)

By what criteria will it be known if a "unified theory of concurrency" has been successfully created? Are there established hoops it must jump through to be called "unified"? By "unified" is "complete" meant? or just combining some subset of "theories of concurrency"? WAS 4.250 17:25, 17 May 2006 (UTC)

Well, I don't think there are any official criteria. And "unified" may be too strong a word. I guess what I meant is that we'll be able to reconcile all of the various models and notations for concurrency in such a way that one could easily translate from one representation to another (and know what information would be lost in such a transformation). It's not clear that there will ever be a "one true theory", because the particular representation you need to use depends on the problem you are trying to solve, and the properties that you need to be able to understand. --Allan McInnes (talk) 23:44, 26 May 2006 (UTC)

translate from one representation to another Got it. Thank you for the answer. WAS 4.250 17:46, 27 May 2006 (UTC)

Yes, you can create a "test for correctness (i.e. emergent behavior has desired properties)" but how can you know what other emergent behaviors it might have that might affect important behaviors in unforeseeable ways? The more interesting and complicated the designed emergent behaviors, the more unforeseeable other emergent behaviors must be.

Well, that's the reason that we would want to use some kind of concurrency theory. Using such a theory, it is possible to ensure that some assertion about the emergent behavior of a system holds in a global sense (i.e. for all possible interactions between constituent parts — see theorem prover and model checker). Those assertions can be things like "this desirable kind of behavior may occur", "this desirable behavior must occur", "this undesirable behavior must never occur". Obviously, we're still left with the problem of deciding what is and is not desirable... --Allan McInnes (talk) 03:10, 17 May 2006 (UTC)

You say Using such a theory, it is possible to ensure that some assertion. Don't Gödel's incompleteness theorems and the Halting problem have something to say about this? WAS 4.250 17:25, 17 May 2006 (UTC)

Gödel says that some things within a logical system are unprovable, within a given logic system. However, it is (from what I understand) feasible to avoid self-reference, and thereby avoid the problems induced by Gödel's theorem. The same holds for the halting problem. Another way to look at it is that, yes, these things are theoretically problems that we need to deal with. But in practice they just don't seem to come up that often — theorem provers and model checkers have been successfully applied on a wide variety of real-world projects. --Allan McInnes (talk) 23:44, 26 May 2006 (UTC)

OK. Here we may have hit on something I would find really really interesting. What is the most complex or most intelligent or most universal data transforming/analysing existing computer software program that you know of off hand that provably avoids self reference such that Gödel's incompleteness theorems and the Halting problem don't apply? I'm not aware of any beyond trivial toy programs. I apologize if this conversation becomes more like work than fun, but it is something I care about a lot; and I'm hoping you feel the same way. WAS 4.250 17:46, 27 May 2006 (UTC)

As I understand it (and my understanding is admittedly not that good), the incompleteness theorem essentially makes it impossible for an automated theorem prover to be applied to itself, to prove its own consistency (in other words, no bootstrapping). But that does not mean that a theorem prover cannot be successfully applied to other systems. Similarly, the halting problem boils down to not being able to apply a termination-detecting program to itself. Again, that doesn't mean that one can't successfully detect termination in other systems. As for non-trivial examples of the use of theorem-provers, model-checkers, and the like, you might try the following:

• http://www.cs.uta.fi/algo/20040527/slides.pdf
• http://citeseer.ist.psu.edu/cimatti00industrial.html
• http://citeseer.ist.psu.edu/havelund00formal.html
• http://citeseer.ist.psu.edu/624487.html
• http://www.cs.uoregon.edu/~fickas/NASA/hase.pdf
• http://citeseer.ist.psu.edu/21400.html

My understanding of both is very different from yours, but its been decades since I got into it. It'll be fun for me to revisit it. Also I'll check out the above links because whatever theory has to say, it is always instructive to look at real cases. It is possible the real cases will show we are talking about related but different concepts in terms of what the managers are trying to aquire confidence in when they wish to predict emergent behaviors. I'll get back to you in a couple of days after I get a chance to research the above. WAS 4.250 20:39, 27 May 2006 (UTC)

"Much of the current work in concurrency theory involves figuring out what we can infer about a system without running it, and how to infer other things by 'executing' an abstracted model of the system." What to abstract and what not to abstract; therein lies the problem. The evolution of complex systems can take some curious twists. WAS 4.250 02:05, 17 May 2006 (UTC)

Sure. As a result, one of the interesting questions in concurrency theory is: what can we guarantee about a system that is analyzed using a certain kind of abstract model. Given answers to those questions, it's up to the "designer" to select an abstract modelling paradigm suitable for verifying the kind of properties that are important for the system at hand. There's still a lot of room for error here, of course. But then even the design of traditional systems is fraught with difficulty and the possibility of modelling errors. I don't see any reason why we should expect "complex systems" to be any different. --Allan McInnes (talk) 03:10, 17 May 2006 (UTC)

I think systems simple enough to be sufficiently anayzable to know how they act without running them are too simple to be called intelligent. WAS 4.250 17:25, 17 May 2006 (UTC)

Possibly. But it's hard to really know, since we don't have a good definition of what constitutes "intelligence". --Allan McInnes (talk) 23:44, 26 May 2006 (UTC)

Yes. Exactly. I find it convenient to define intelligence (in the context of this discussion; meaning something more like real AI) in such terms that my above assertion becomes tautologically true. WAS 4.250 17:46, 27 May 2006 (UTC)

Well yes, if you define "intelligent" as "something we don't know how to formally analyze (yet)", then formal approaches are obviously not much help with "intelligent" systems :-) --Allan McInnes (talk) 18:50, 27 May 2006 (UTC)

In my mind it is more along the lines of beyond a very minimal open ended system, open ended systems have to be run to see what they do and in order to produce interesting (intelligent) (emergent) results a system needs to be open ended. My thoughts along these lines were formed in the 70s and 80s when I studied computer intelligence and its limits. Whether what I'm saying makes any sense or not is directly related to the above issue concerning recursion and halting issues. So this thread connects back to that one at this point. WAS 4.250 20:39, 27 May 2006 (UTC)

About Algorithms

Please, don't repeat each word of K Root, this is enough with him. I was not understood. The article is essential because it is the entry point of a giant amout of information about algos. If the link is removed, we have to replace it with another link as entry point to this part of Wikipedia. Of course, the article itself must be valuable.
About the removal of external links, apparently you consider we have to link to each article of each algorithm rather than on the general algorithm page. Not sure. Readers may need for links sources of algos without to have to search each algo in the Wikipedia. Links are part of content, they must not be removed without discussion. Splang 06:50, 15 May 2006 (UTC)

I'm not sure that I understand what you are saying. The Algorithm article is not going to be removed from Wikipedia. It will still be available as an entry point to Wikipedia. All that is being voted on is whether the Algorithm article, as currently written, deserves featured article status. I believe that if you read Wikipedia:What is a featured article? you will find that in fact Algorithm does not meet many of the requirements to be a featured article.

As for links to algorithm implementations: I don't see any need for them in the main article. The article already contains links to more detailed information on specific kinds of algorithms (see Algorithm#Classes and Category:Algorithms), which includes both detailed descriptions of how the algorithms work, and links to implementations. People reading the main Algorithm article are unlikely to be looking for algorithm implementations, they will be seeking a general understanding of what an algorithm is. Please bear in mind that Wikipedia is an Encyclopedia, not a directory of links. --Allan McInnes (talk) 15:20, 15 May 2006 (UTC)

Thanks for the links. I was not aware of this conflict for the programming language in the articles, and this makes some mysteries clear now (as the grimness of R._Koot to remove Scriptol).

About the removal of Algorithms, the process is stopped as an INVALID NOMINATION.

No comment about the admin (the same above) that has started this process.

The purpose of this message is that you have removed the Dmoz link, along with scriptol.org and further added the link again. This proves we need for links in the main article. Scriptol.org provides pages for lists of implementations of various algos and can't be dispatched, must be in the main page, as Dmoz. Please add it again. I can't do it for reasons above.

About the pseudo code, it is strangely similar to Python, but I will discuss that in the proper page. Splang 14:01, 17 May 2006 (UTC)

I added the dmoz link because it provides a directory of links to both sites that contain algorithm implementations, and to other sources of information about algorithms (journals, conferences, etc.). In other words, it is a general source of information on algorithms.

Wikipedia is not a directory. We can't list every site that contains sample algorithm implementations in the external links section of Algorithm. Such a list would dominate the article, and be contrary to the principles of the Wikipedia guidance on external links. However, dmoz is a directory, and in fact is an open directory, which makes it preferable from Wikipedia's point of view. Why don't you try getting the Scriptol.org link added to the dmoz algorithm page? That seems (to me at least) to be a much more appropriate location for such a link. --Allan McInnes (talk) 15:15, 17 May 2006 (UTC)

It is already added to the Dmoz directory. But it is not normal a website dedicated to Algos and programming languages, with more than 70 pages of valuable content is not linked to WP too. Splang 12:08, 20 May 2006 (UTC)

hello

thanks for the welcome. was it auto-generated? In any case, I am familiar with your name from following the CarlHewitt controversy. I am very pleased to meet you.

Ideogram 22:18, 26 May 2006 (UTC)

The welcome message was generated using the {{welcome}} template. But I manually placed the template on your talk page, so there was some personal attention involved ;-)

Anyway, welcome to Wikipedia. I am also pleased to meet you. I was not aware that there was anyone following the Hewitt controversy, outside of those few of us involved in the arbitration case. --Allan McInnes (talk) 22:28, 26 May 2006 (UTC)

That's one of the great things about wikipedia, all official proceedings are public, so us anonymous cowards can lurk before deciding to participate.

I've long been a fan of Carl Hewitt's work. I won't publically air any of my less complimentary concerns.

Ideogram 23:37, 26 May 2006 (UTC)

Well sure, it's public (which I agree is a good thing). That doesn't mean anyone's actually looking at it :-)

As for Carl: he has done some truly ground-breaking work in the past (more than I had realized before I became embroiled in a few arguments with him, and started looking back through old MIT reports to try to understand where he was coming from), and I think it's safe to say that he's been ahead of his time in many ways. I suspect he hasn't got nearly as much recognition as he deserves in the CS world. Unfortunately, Wikipedia isn't really (IMHO) the right place to try to correct that (nor to push new theories). That said, I'm very disappointed that Carl chose to depart Wikipedia, and have told him as much in private emails. --Allan McInnes (talk) 23:51, 26 May 2006 (UTC)

Pioneers are often individualists. Wikipedia is a community. Ideogram 00:00, 27 May 2006 (UTC)

That's a very good point, and one which I had not really considered before. --Allan McInnes (talk) 00:10, 27 May 2006 (UTC)

?

Is our interesting conversation over, or just on hold? WAS 4.250 23:32, 26 May 2006 (UTC)

Oops! Sorry! Been a bit busy lately. Will post something soon. --Allan McInnes (talk) 23:33, 26 May 2006 (UTC)

FP in clear

I should be done with any major restorations to Functional programming. There are still things that could use touching up, but I think I'm managed to get all the basic mass-deleted content restored (and in many cases, put in some wording improvements while doing so... I guess it's good to be prompted to do that, despite the annoyance factor). LotLE×talk 02:29, 28 May 2006 (UTC)

I like most of the current article and I don't see anything major I wish to delete. Sorry I annoyed you. May I start editing again? Ideogram 03:05, 28 May 2006 (UTC)

models of concurrency

Hello Allan. I've decided to take a break from FP and editing and I wanted to discuss concurrency theory with you. I hope you have the time.

I've thought about it off and on since 1990, and the Actors model has been very influential on my thinking.

Basically I've decided that the fundamental concept should be the Event. In Actor terms this would be a message. A function call as used in sequential programming is actually composed of two Events, the call and the return (sorry if I'm stating the obvious). In a sequential programming system focusing on one task there is nothing else to return to, so unifying the two events is reasonable. but in a parallel distributed system there may be many processors working on many tasks. in this case you clearly need to be able to control where the results of a computation go. thus i feel that attempts to extend the concept of a function to parallel distributed system, such as RPC, are the wrong approach.

Historically I was led to the concept of an Event by my experience programming the X Window System. If you are not familiar with GUI programming, one usually writes the program as a loop with a giant switch statement that collects events and dispatches them. This is clearly an Actor.

Parallel distributed programming, and the Actor model, are traditionally considered hard to understand. But here I found an application of the Actor paradigm that was being used because it made things easier.

Events have the advantage that they make explicit the fundamental concepts of parallel distributed programming which sequential programming lacks. In parallel distributed programming events happen at a time, maybe the same time, and a place, as opposed to sequential programming where everything happens one at a time in the CPU. Events make clear what is essential about programming in both models, namely the notion of causality, which imposes a partial ordering on the time sequence of events.

The model used in "Distributed Algorithms" by Nancy Lynch, for instance, assumes that state transitions (which in my model are caused by and therefore map to events) still occur one at a time, except that certain sets of state transitions may happen in nondeterministic order. In terms of my model it is clear that events linked by causality do not form these sets, while events that do form these sets may happen at the same time. Although I understand Professor Lynch's need to reduce parallel distributed programming to something amenable to theory, I am dissatisfied with her model since it does not correspond to my intuitive understanding of what happens in a parallel distributed system.

However, one should note that in my system it is not possible to speak of the entire system as being in one "state". This obviously makes it hard to reason about, but it does correspond to my intuition of what's actually happening.

Let me stop here and wait for feedback before continuing. Ideogram 07:07, 28 May 2006 (UTC)

You may be interested in taking a look at the process calculi (such as CSP, ACP, or the Pi-calculus), if you're not already familiar with them (disclaimer: I'm somewhat biased, since I'm interested in process calculi; OTOH they really do sound like they fit with your ideas to a certain extent). Process calculi take "events" as the primitives, and build "processes" from causal sequencing of events, parallel composition of processes, and inter-process synchronization. I shoud probably note here that most (all?) process calculi use an "interleaving" semantics (i.e. concurrency is represented as nondeterministic ordering of transitions). I don't personally see this as a big problem, since in my experience "true" simultaneity isn't that useful a concept for concurrency modeling — it's only really relevant in models where you're assuming that time is not infinitely divisible, in which case you probably need to include an abstract clock-tick event anyway. That said, there has been some work on so-called "true concurrency" in process calculi, such as [1], [2], and [3]. If you are interested in considering both the time and place of event occurrences, you may find some of the recent work on bigraphs interesting (although I must admit my own knowledge of bigraphs is pretty limited at this point).

--Allan McInnes (talk) 07:30, 28 May 2006 (UTC)

I am not well-versed in theory. I am primarily interested in paradigms as guides to implementation, not as formal systems to prove theorems about. That said, I am curious why process-calculi include synchronous communication, since in the Actor paradigm all communication is asynchronous. Also I've looked at CSP and I thought it depended on locking for synchronization, which I don't like. I am a fan of guardians; since messages in Actor programming have to be sequenced by an arbiter any data you need to protect with a lock can be protected with a guardian.

CSP doesn't "depend on locking" so much as assume synchronization (much the same way the Actor model assumes fairness). There are many different ways to implement synchronization. Note also that process calculi fully encapsulate state - there are no need for locks, since the only way to access data is via message-passing to with whatever process holds the data. The reason that the process calculi tend to focus on synchronous communication as a primitive is that it makes algebraic analysis more tractable. But you can model asynchronous systems within a synchronous framework, and vice versa.

As for paradigms to guide implementation: CSP (and process calculi in general) have been used as the basis for a number of different languages and systems. CSP in particular was heavily influential in the design of occam and the JCSP concurrency library for Java. It also influenced the design of concurrency in Ada and Concurrent ML. Other process calculi have influenced the design of languages such as Pict and the Join calculus. If you prefer asynchronous message-passing, you might want to look at the way Erlang works. It's implementation shares much with the Actors model.

CSP is focused on "processes" which calls to my mind a traditional unix process, a thread of control along with a protected memory space locked to one processor. But if you focus on the events you realize that a "process" may be spread out as patterns of message passing across processors spread out in time and space, linked by causality. I don't know if this makes a difference to the theory, but it feels different to my intuition. Ideogram 07:48, 28 May 2006 (UTC)

Processes in the process calculi are simply an abstraction that represents a pattern of message passing. While you might choose to model a collection of OS-level processes as individual processes, it's also feasible to algebraically manipulate the process expressions into a variety of other forms. Since a single "process" in a process calculi can be created through parallel composition of multiple component processes (i.e. the grammar of processes is recursive), a process certainly doens't represent a single thread of control.

CSP has been used for analyzing everything from network-level interactions down to individual synchronous (and asynchronous) logic gates. Variations on the pi-calculus have recently become popular for modelling interactions at the cellular and sub-cellular level in biological systems. --Allan McInnes (talk) 16:46, 28 May 2006 (UTC)

In the Actor model messages pass between actors. If processes in the process calculi are patterns of messages, what are actors in process calculi? Is the distinction necessary?

This actually touches on one of the fundamental differences between the Actor model and the process calculi. Actors have identity. Processes do not. Of course, we generally give names to particular processes to help identify them when writing process descriptions. But the names themselves are not used to identify the processes during communications. Rather, communications are carried out anonymously, and take place via "channels", of which a given process may have several. It is this lack of process identity that makes it possible to algebraically manipulate process descriptions. That said, identity can be simulated by providing a process with a single channel, which represents its "identity". --Allan McInnes (talk) 20:30, 28 May 2006 (UTC)

So processes in the process calculi are both actors and patterns of message-passing? because actors can receive messages (have channels) while patterns of message-passing cannot. Ideogram 05:46, 29 May 2006 (UTC)

Er... yes and no. And I realize that's not a particularly satisfactory answer. You can view processes as actors or agents. But the processes themselves are essentially just patterns of events which, when composed with other processes that share some of those events, produce the appearance of communication. Let me give an example, which I hope will clear things up some:

Let's say we have a process (in CSP notation) P = chan?x -> do.x -> Stop. This expression defines a process which can receive a value over the channel "chan", bind that value to "x", and then engage in some action "do.x".

If we place that process in parallel with another process Q = chan!laundry -> Stop, we get the composite process PQ = P |{|chan|}| Q, where |{|chan|}| means that P and Q synchronize on all events involving channel "chan".

Now, how does the process PQ actually behave? Process Q wants to output "laundry" on "chan". P and Q synchronize on that event, so PQ can be observed to perform the communication event "chan.laundry". Then, since P has bound "x" to laundry, it will perform "do.laundry". The message "laundry" has been communicated from process P to process Q.

But wait! From our description of PQ, it sounds like PQ is, as a result of the way P and Q synchronize, a purely sequential process. In fact, PQ is algebraically equivalent to PQ' = chan.laundry -> do.laundry -> Stop. Same pattern of events. No message passing involved. PQ' is a single process.

Now let's take another look at process P. Assume for the moment that the only messages that can traverse "chan" are "laundry", "shopping", and "taxes". Then one way to look at P is as a process that is initially willing to synchronize on any of the events "chan.laundry", "chan.shopping", and "chan.taxes". So P is equivalent to a process P' = (chan.laundry -> do.laundry -> Stop) [] (chan.shopping -> do.shopping -> Stop) [] (chan.taxes -> do.taxes -> Stop), where [] denotes a choice over initial events. This view of P exposes the pattern of events defined by the notion that P's actions depend on the message that it receives over "chan" - the notation chan?x, which represents message reception, is simply a convenient shorthand for a branching pattern of events.

Now, this is obviously a pretty trivial example. But hopefully it illustrates the idea. If not, then all I can really suggest is to take a look at something like Tony Hoare's CSP book, which gives a pretty readable introduction to these ideas. I'm not sure I'll be able to achieve much more here on a talk page (now if we just had mutual access to a whiteboard...). --Allan McInnes (talk) 08:48, 29 May 2006 (UTC)

How do the process-calculi handle the problem that the composition of actors is not necessarily a single actor with a single message queue?

By allowing multiple processes to communicate via multiple channels. One can form "process networks", in which groups of processes are interconnected in different ways. Furthermore, some process calculi permit multi-way synchronization between several processes operating on a single channel. Others allow broadcast communications. --Allan McInnes (talk) 20:30, 28 May 2006 (UTC)

I was not clear. The intent was not to ask how to implement a composition of actors in the process calculi, but to say there is a problem with the Actor model in that a composition of actors is not an actor. Namely that the multiple message queues can lead to race conditions (I believe), and make it hard to implement abstraction (since the set of actors is not closed under composition). Ideogram 05:46, 29 May 2006 (UTC)

The ability to be closed under composition is one of the reasons that processes were made to be anonymous, rather than having identities the way actors do. Processes do not have a single message queue. Since the "interface" of a process is simply defined by the set of channels it can communicate over, composing two processes produces a new process with an enlarged interface formed from the union of the component process interfaces. Since even an individual process can potentially choose between several channels when receiving a message, it's straightforward to allow composite processes the same kind of choice.

Does that answer your question? --Allan McInnes (talk) 08:48, 29 May 2006 (UTC)

How do the process-calculi handle the implementation detail that some actors are physical (CPUs) while some are virtual, and can move between physical CPUs, and even be created (allocated) and destroyed (deallocated)? The article on CSP mentions an issue with mobility, is this related? Ideogram 19:48, 28 May 2006 (UTC)

This becomes a question of choosing the right process calculus for the job (ther are, after all, many process calculi). CSP does not permit a direct representation of mobility (although it can be emulated in a relatively straightforward manner), so is probably not a good choice for modelling systems that involve highly mobile code. However, calculi such as the pi-calculus and the ambient calculus do provide ways of representing and reasoning about mobile code. --Allan McInnes (talk) 20:30, 28 May 2006 (UTC)

Can the process-calculi be used to analyze performance; time, memory space, and number of physical processors used? Ideogram 19:53, 28 May 2006 (UTC) and bandwidth Ideogram 20:05, 28 May 2006 (UTC)

There's no single answer to this. You could presumably perform the same kinds of execution time/space calculations on a process calculus expression that you could on, say, the lambda calculus (although I'm not sure if anyone's actually done that). But that only gives you Big-O bounds. However, there are some process calculi that incorporate notions of time, and resource consumption, which would presumably allow you to compute more "real-world" performance figures. My knowledge of these things is hazy though. Number of physical processors, I'm not sure about - that seems likely to depend on a lot of factors outside of the process design. I suppose that bandwidth is a possibility, if you were using a timed model, and could assign some kind of approximate size in bits to each message. --Allan McInnes (talk) 20:30, 28 May 2006 (UTC)

what would you say are the differences between current models of concurrency that would need to be resolved to achieve a "universal model"? Ideogram 19:38, 28 May 2006 (UTC)

Whew! Tough question. Uhhh... a few things spring to mind, but I'm hardly an expert. Here're the things that come to my mind immediately:

• Reconciliation between the various process calculi - how different kinds of process equivalences map between different calculi
• Handling of spatial distribution of processes in calculi in a way that aligns well with Petri nets (bigraphs deal with this to a certain extent)
• True concurrency vs. interleaving concurrency - being able to represent both in the same model would be handy I guess

Having said all that, there's alerady lots work being done in all of these areas. From what I understand, bigraphs seem to hold the most promise for bringing things together at this point, since they seem to allow a unification of Petri nets and process calculi. Hoare, Milner, and others have done some work on bridging the gap between the various process calculi. There's also been work on encoding the Actor model in a process calculus, and on developing process calculi specifically for representing Actor systems. The combination of those things would seem to bring together the three major strands of event-based concurrency. Underlying it all is work on the duality between events and states, which shows some promise for being able to unify event-based concurrency with the assertional state-based concurrency found in things like Lamport's Temporal Logic of Actions.

You're really starting to push the edges of my knowledge on concurrency theory now, so I'm really not sure how close we are to a real "unification" or what actually is left to be done. --Allan McInnes (talk) 20:30, 28 May 2006 (UTC)

operating system not listed in category:computing

how do I add it? Ideogram 10:04, 28 May 2006 (UTC)

C programming language isn't listed in category:programming languages either. Ideogram 10:07, 28 May 2006 (UTC)

To add an article to a category, you simply need to edit the article to place the appropriate category link (for example, [[Category:Computing]]) at the bottom of the page. However, not in this case that operating system is a member of Category:Operating systems, which is in turn a subcategory of Category:System software, which is a subcat of Category:Software, which is a subcat of Category:Computing. In general, articles should not appear in both a category and a subcategory of that category (see Wikipedia:Categorization), so operating system is probably fine where it is. I'd imagine the same holds for C programming language, although I haven't checked it. --Allan McInnes (talk) 16:29, 28 May 2006 (UTC)

Emergence

Emergence says For a phenomenon to be termed emergent it should generally be unpredictable from a lower level description. You said in order to verify that the emergent behavior produced by a swarm has the properties we desire. I think this gets to the heart of our miscommunication or misunderstanding or differences of opinion. I'm not sure "emergent" means much when applied artificial intelligence if it doesn't mean you have to run it to see what it does. You appear to be using "emergent" to mean something less than that. What in the context of in order to verify that the emergent behavior produced by a swarm has the properties we desire should "emergent" be defined or identied as? Obviously not For a phenomenon to be termed emergent it should generally be unpredictable from a lower level description. WAS 4.250 15:19, 28 May 2006 (UTC)

It does seem that we have somewhat definitions of "emergence". As always, language is getting in the way of communication  :-)

To me, "emergent" behavior is behavior that results (i.e. emerges) from interactions between the parts of a system. Systems that do not display "emergence" are those in which the behavior of the system is a straightforward linear combination of the behavior of the parts, rather than the result of interaction. In that sense, "emergent" behavior is "unpredictable from a lower level description", because it requires knowledge of how the parts are interconnected, not just what the parts are. Different connection topologies can produce different emergent behaviors from the same set of parts. But given a system-level description (i.e. an description of the interconnections), predicting the behavior becomes possible.

Anyway, that's my take on emergence. Obviously not the same as yours. --Allan McInnes (talk) 08:21, 29 May 2006 (UTC)

Now in order to verify that the emergent behavior produced by a swarm has the properties we desire makes perfect sense. Whenever I wrote stuff that had timing issues, I always made sure the subroutines using time-sensitive data had logically-defined, specific and few relevant states that covered all logical possiblities (I implemented tractable virtual state devices). This made sure they always did what was specified, even if sometimes what was specifid turned out to be not what was desired :) WAS 4.250 11:55, 29 May 2006 (UTC)

Algorithm

Yea, at one point today, I actually was on a very separate article called "Computer Algorithm", with about a paragraph of information, but I'm not sure what happened to it. Perhaps an incorrect spelling? maybe it was deleted? But thanks for letting me know.Adambiswanger1 05:20, 29 May 2006 (UTC)

Hmmmm... I hunted around a bit, and I'm guessing that your were looking at Computer algorithms (note the s). After looking at the page, there's not really anything to merge (since essentially everything there is already in the Algorithms article), so I'm just going to turn it into a redirect. --Allan McInnes (talk) 08:09, 29 May 2006 (UTC)

thanks

Thank you for your kind words. I will certainly refrain from editing FP for a while (if not permanently). I may try to edit other articles but after this experience and your comment about avoiding radical changes I will keep my edits small. I certainly found our conversation on models of concurrency enlightening so I will probably confine most of my participation to talk pages.

Thanks again. Ideogram 20:43, 29 May 2006 (UTC)

I'm enjoying my interaction with Wikipedia very much. I'm glad I didn't leave. Ideogram 18:17, 31 May 2006 (UTC)

ptolemy project

I was a big fan of the ptolemy project, what happened to your draft for this? Was the subject too OR? Ideogram 16:57, 31 May 2006 (UTC)

I too am a big fan of the Ptolemy project, as well as Ed Lee's other work on embedded systems. As for the draft: I simply never got around to starting it. The link on my user page is a place holder to remind me to make a start on it at some point. But I've been too busy with other things recently. Ptolemy is certainly not "too OR" & mdash; there's been plenty published on it. There's a Ptolemy Project stub article that someone put together while ago. I've done a small amount of work on it, but it's sorely in need of expansion. Dive on in, if you're interested! --Allan McInnes (talk) 17:08, 31 May 2006 (UTC)

References in format

I just didn't how to do them and didn't want to spend the time learning, to be frank. (This wiki-thing does take a lot of time!) Is there a place where i can go to learn? lemme know, thanks.wvbaileyWvbailey 18:20, 31 May 2006 (UTC)

If you're talking about the citation templates, the template pages themselves ({{cite book}} and {{cite journal}} - just click on the links to go to them) have pretty good instructions on the corresponding talk page. The usage is pretty straightforward (similar to BibTeX if you've ever used that). As for inline references, the Wikipedia:Footnotes page I pointed you to earlier has some pretty good instructions. If you have any questions, please feel free to ask me. I'm still figuring out how best to use these tools myself, so perhaps we can work out any problems together. --Allan McInnes (talk) 18:54, 31 May 2006 (UTC)

Hi again, wvbailey here: the history on the algorithm page is growing and growing. I'm finding it interesting stuff; it ties together, esp. when we consider what cool inventions influenced these guys as they were doing the math, and all the battles between the Intuitionists and logicists, and all the amazing math that was going on, etc. But its getting awfully big.

I personally like a lot of quotes. Some folks want it spoon-fed to them.

Let someone else massage the stuff I've found? Ruud reverted the stuff quoted from Knuth. I'm become timid. I can't stand reversion-wars and fighting about this word and that word-- hate it hate it hate it -- and silly bullshitty know-nothing arguments about e.g. copyright issues (there aren't any ferchrissake). Any thoughts re outline, content, whatever? I mean I could make a stab at it but if Ruud reverts it, I say fuck it, I'm done with it. It's too much work to have it slashed and burned, and to then have to fight over the rotten body-parts that are left. I've got other, more profitable things I could be doing. That's why I'm asking for guidance here. Thanks. wvbaileyWvbailey 19:14, 5 June 2006 (UTC)

Well, as I said on Talk:Algorithm, I think the history you've dug up is very interesting, and will make a worthwhile addition to the "History" section. That said, I don't know that extensive quotes within the text itself are necessarily appropriate (that is of course a matter of taste; but I rearely see Wikipedia articles containing extensive quotes). What I would like to do is to have the history section discuss the key people and issues, and perhaps have any necessary supporting quotes included in the footnotes. I may take a stab at integrating some of the historical references you've supplied into the article when I get some more free time.

As for Knuth, I think he's a good source for a definition of "algorithm", but again I'm not sure an extensive quote is necessarily such a good idea. A summary of Knuth's definition and explanation, along with a relevant reference to TAoCP would probably be more widely accepted by other editors. At least in my opinion. You are of course free to add whatever you like to the article.

--Allan McInnes (talk) 19:25, 5 June 2006 (UTC)

CSCOTW

we have three votes. what is the procedure, do we wait for the end of the week? Ideogram 21:55, 5 June 2006 (UTC)

Well, since there are no other nominations, you can probably just run with it. The important thing is to get people actually working on the article in question. I'd suggest that (a) you make sure that the 3 people who voted all actually do some work on the article, and (b) you post something on the WPCS talk page to let other people know. Part of the reason that CSCOTW kind of died off is that no one actually worked on the collaborations. --Allan McInnes (talk) 23:14, 5 June 2006 (UTC)

How do I make programming language show up in the box on the CSCOTW page? Ideogram 23:27, 5 June 2006 (UTC)

You need to edit Template:CSCOTW current. I've gone ahead and inserted Programming language there. --Allan McInnes (talk) 23:40, 5 June 2006 (UTC)

What is the best way to "prod" one of the voters to work on it? I was thinking of a note like: "Hi! Since you voted to make programming language the CSCOTW, please join in the discussion!" Ideogram 10:05, 8 June 2006 (UTC)

That's probably a good way to approach it. I've seen similar notices for other (non-CS) COTWs. --Allan McInnes (talk) 15:01, 8 June 2006 (UTC)

voting procedure

We have a disagreement at programming language which we would like to settle with a vote. Is there a procedure to follow? Ideogram 21:58, 5 June 2006 (UTC)

Wikipedia doesn't tend to operate by vote. That said, it's sometime useful to run some kind of "straw poll" to help build consensus. You can find some guidance on doing straw polls here: Wikipedia:Straw polls. --Allan McInnes (talk) 23:16, 5 June 2006 (UTC)

During the discussion three people spoke up on one side, and one on the other (who is the person calling for the vote). What is the best way to handle this? Ideogram 23:19, 5 June 2006 (UTC)

That kind of situation can be hard to deal with. From the sound of it, it's unlikely that a vote will settle anything. From what I can gather from the talk page, the problem seems to come down to a disagreement as to what the section should contain. My suggestion is that you start by trying to define (in one sentence) what the section is about, and get the objecting user to agree that having a section covering X (whatever X is) is a worthwhile thing. That might give you a better idea of what the title should be (which I gather is also a point of contention). Then try to define, in bullet form, the key ideas that will make up the section. Again, get agreement from the objecting user. Finally, flesh out the section. Of course, I can't guarantee that'll work. But it might help you make some progress, instead of arguing over minor points of wording.

My understanding is that you're trying to write a section that explains "why we need programming languages, and what makes them different from natural languages". Is that correct?--Allan McInnes (talk) 23:54, 5 June 2006 (UTC)

Yes, that's a fair assessment. I'll see what I can do. Ideogram 00:00, 6 June 2006 (UTC)

uncooperative user

User: Derek farn has repeatedly reverted edits with no attempt made at discussion (see history for programming language. I fear that his interference will drive contributing editors away. This is unacceptable. What am I supposed to do? Ideogram 02:09, 6 June 2006 (UTC)

Wikipedia:Resolving disputes outlines the options. Since negotiation seems to be breaking down (based on the most recent posts I'v seen on the talk page), you might start by asking someone from the Mediation Cabal to step in and try informal mediation. --Allan McInnes (talk) 02:31, 6 June 2006 (UTC)

thanks again

I don't know what I would have done without you, on many many occasions. Ideogram 03:27, 6 June 2006 (UTC)

You're welcome. Glad to help out. Although I'm afraid I may have caused you to jump the gun a little on the medcabal. I didn't mean to suggest that you should submit a cabal request right away (going back and reading what I wrote, I can see how it might be interpreted that way though). It never hurts to step away from the keyboard for a few hours (or overnight), and take another look at things later. That said, it probably wouldn't hurt to have someone from medcabal stop by and calm things down a bit. --Allan McInnes (talk) 03:40, 6 June 2006 (UTC)

I was very frustrated. Don't worry, I take full responsibility for my actions :-). Ideogram 03:44, 6 June 2006 (UTC)

ta for the help

I feel a little foolish.... I did indeed put that stuff on my user page. I did not write the text which is why I didnt recognise it as my writing it I wrote the template that expanded into that display text, that I recognised as soon as I went into edit mode to remove it as suggested. blush.

It seemed like a good idea to test it there at the time. I have been having some other confusion(deleting conflict) as I adapt to the wikipedia way and the way it values its content and contributors. They all got mixed up my head. Oh well I live to learn. delete at will. AccurateOne 08:36, 6 June 2006 (UTC)

You're welcome. Happy to help! If you have any other questions, please don't hesitate to ask. --Allan McInnes (talk) 14:37, 6 June 2006 (UTC)

Do they use "ta" Down Under or is it mainly a British thing? Ideogram 05:30, 7 June 2006 (UTC)

They do indeed use "ta" down under. --Allan McInnes (talk) 07:13, 7 June 2006 (UTC)

Interview

Hi Allan, it's been a while. I am wondering if you could help me with a project of mine. Would you be interested in being interviewed regarding Wikipedia? I would be asking about your views of the current system and questions such as how it could be improved and how do you think Wikipedia would develop in the near future. Thank you. -- ^Evanx(tag?) 17:25, 7 June 2006 (UTC)

Hi! Uh... I guess I would be amenable to be interviewed. Although I'm not sure I have any coherent views on how WP could be improved, or things of that nature. But anyway, what exactly did you have in mind? --Allan McInnes (talk) 01:19, 8 June 2006 (UTC)

I am doing a project regarding an investigation of Wikipedia which would include its origins, analysis of advantages and disadvantages of such a system and speculation regarding its development (realisitically as well as ideologically). I will be preparing a set of questions on a page relative to my user page and would be asking you several questions. Of course, you may wish to contribute some questions of your own. I have asked you as I believe that with your credentials and contribution history, you make a very reliable and trustworthy academic source. -- ^Evanx(tag?) 22:19, 8 June 2006 (UTC)

I have posted a preliminary copy at User:Evanx/Interview. Please take a look and make suggestions, if any. -- ^Evanx(tag?) 23:22, 8 June 2006 (UTC)

Are the questions to your approval? -- ^Evanx(tag?) 03:56, 11 June 2006 (UTC)

Sorry for my lack of response - I've been pushing to get a conference paper finished up the last couple of days. The questions look fine. I'll try to answer them sometime this week. Do you want me to just insert my answers at the appropriate places in the page? --Allan McInnes (talk) 17:20, 12 June 2006 (UTC)

Sure! -- ^Evanx(tag?) 19:32, 12 June 2006 (UTC)

Hey Allan I'd love to see your answers to these questions. Ideogram 03:59, 11 June 2006 (UTC)

Template:Major programming languages

Can we delete this yet? Ideogram 21:01, 7 June 2006 (UTC)

You need to have an administrator take a look at the discussion, decide what the consensus was, and take the appropriate action. I'm afraid that I can't help you there, because I'm not an admin. --Allan McInnes (talk) 22:31, 7 June 2006 (UTC)

Portal:Information technology

Can we get the Computer science portal into the related portals on this page?

Also, there seems to be considerable overlap and confusion between Information technology and Computer science. Even their Selected article is Java programming language which I would think belongs to Computer science. Ideogram 10:03, 11 June 2006 (UTC)

I think you'll find that the CS portal redirects to the IT portal. I tried suggesting the creation of a CS portal on the WPCS talk page a few months back, but got a very lukewarm response. --Allan McInnes (talk) 17:22, 12 June 2006 (UTC)

Ah. I see that Rudy has created a new CS portal. --Allan McInnes (talk) 17:43, 12 June 2006 (UTC)

relational database rewrite

I'm trying to rewrite relational database; do you think this article falls under Computer science or should I look elsewhere for contributors? Ideogram 10:36, 11 June 2006 (UTC)

Can't see why it wouldn't fall under CS. --Allan McInnes (talk) 17:23, 12 June 2006 (UTC)

al-Khwarizmi

I have asked R.Koot for his thoughts on this matter on his talk page. I would love to see your thoughts as well. Ideogram 12:48, 13 June 2006 (UTC)

I've followed the al-Khwarizmi firefights on and off for the last few months. In my opinion it's mostly the result of people trying to score points for their particular "team" (i.e. nationality or religion), rather than trying to make an encyclopedia. Perhaps it will cool down now that the world cup is on :-) --Allan McInnes (talk) 15:52, 13 June 2006 (UTC)

Is the entry doomed to endless edit-warring? Can nothing be done? Ideogram 15:57, 13 June 2006 (UTC)

Well, the page could presumably be protected if things got out of hand. But I don't really feel like I'm in a position to make that call. Rudy's been heavily involved in the article, and I'm sure he would get it protected if he felt it warranted protection. He may be holdng off so that the article can still be edited to improve it. I don't know. --Allan McInnes (talk) 16:00, 13 June 2006 (UTC)

Derek farn

I've tried to open a dialogue with Derek farn here but he insists he is still trying to ignore me. I think he respects you (and you know I respect you) so could you try to reason with him? I will be forever in your debt (heck, I am already :-). Ideogram 11:20, 17 June 2006 (UTC)

I've been considering how I might intercede in this situation, and haven't come up with anything yet that's likely to be effective. I would suggest that you consider that tryng to force the situation with Derek is not likely to be productive. It might be better to restrict you interactions with him to the PL talk page, where you potentially have others who can argue with him as well. --Allan McInnes (talk) 15:34, 19 June 2006 (UTC)

It's been a week since he edited. I am at once relieved that I don't have to fight with him and disappointed that we don't have access to his formidable knowledge. (watchlisted you) Ideogram 17:59, 27 June 2006 (UTC)

welcome note

thanks Allan for the welcome note,am sure you have seen my work and found how stupid i am the truth i have this passion for computer science was tought alittle of c and c++ programming language that we do in writing like there algorithms but do not often go to the extend of executing and things like that, find out how it works, because of lack of computers,you must wonder where am from Africa,Kenya in the interior a very remote small university and since i had scored and loved mathematics they took me in but then i decided to do computer science and i enjoy the little i know and i thought by getting to your site wikipedia i would benefit alot in what i want to achieve.i hope am in the right place as most of the guys work that are in here are post graduates or know exactly what they are doing.and i hope i can catch up on my own with your help fast.thanks again Allan —The preceding unsigned comment was added by El-fridah (talk • contribs) .

You're most welcome! Don't worry if you feel like you don't know as much as others here (I feel like that all the time). Wikipedia is a great place to learn things - from the articles, from other editors, and from doing the research necessary to fill out an article. As long as you're willing to learn (which it sounds like you are), I have no doubt you'll be a great contributor. --Allan McInnes (talk) 15:10, 30 June 2006 (UTC)