Thursday, October 22, 2009

Concurrent Communicating Processes

Transformation of a symbol to another takes time, however small. Thus, some action must occur for a transformation to take place. We assume a certain number of transformations (functions) and a few ways of combining them provide us with the set of computable functions. By automating the actions needed to perform these transformations and ways of combining them we arrive at what can be automated. In this sense, what can be automated and what can be computed are synonyms.

However, there are actions other than those needed for the set of computable functions that can be automated. For instance, when we accept that a Turin machine can write a symbol on its tape, we are saying that the action of writing the symbol can be automated. The sending of a message from one computer to another is another example. Thus, what can be automated is a larger set than what can be computed.

In the same sense, an algorithm can be extended to mean a finite sequence of actions that can be automated in order to accomplish tasks, which may involve computations. For instance, imbedded computers allow robots to perform many physical operations algorithmically. Such robots will generally perform computations in order to accomplish their tasks. But they also perform actions that are not related to a computation.

Through simulation one can show that two stack machines are equivalent to a Turing machine. The cooperation of the two stack machines is achieved via implicit communication. In other words, when we add communication between two or more entities we get more than the sum of individual entities. Nonetheless, regardless of number of Turing machines put together, we do not get a larger set of computable functions. This is because communication among Turing machines is not needed in order to arrive at the set of computable functions, at least not the set as we understand it now.

Suppose we have designed a robot that can act like a carpenter and make a large collection of tables, algorithmically by following a set of pre-determined programs. Now, suppose we need tables that their construction will take the cooperation of two carpenters. Replace the carpenters with two communicating robots. In this case, the robots will need to synchronize their actions while putting together certain parts. In other words, by adding the dimension of communication we have extended the (automated) set of tables that can be constructed. Each robot will have a Turing machine inside it for performing the computations it needs for its movements. However, the set of tasks they can accomplish together is larger than the set of tasks each of the robots could accomplish alone.

Concurrent communicating processes refers to two or more separate entities with imbedded computers that accomplish automated tasks via communication. The main characteristic of this scenario is that the processes may use rendezvous, but they certainly use interruption (signaling). That is, after sending a message the sending process does not necessarily halt until the other process sends its response back. Basically, one process anticipates certain changes required in the state of another processes. It signals that process and passes the data to it. The recipient accepts the data and sets its new state accordingly, which may change its future computations for performing its operations.

The use of shared memory between two processes on a single machine seems like a simulation of concurrent communicating processes. A reasonable and simple simulation can also be achieved via two Z++ threads using common objects. This use of concurrent communicating processes is for convenience in computing algorithms that can also be completed sequentially. The use of algorithm in our case is more general than computations involving mathematical functions alone. Indeed, in our model an algorithm involves simultaneous participation of individual entities in accomplishing a common task. After all, the purpose of a mathematical computation is to take some action. When a task requires more than one entity, communication is a necessity rather than a convenience.

The formalization of this model of automation requires more refined research. The model cannot be mapped to a single entity with an imbedded Turing machine. Rather, it seems more like cooperative distributed computing that requires more than one computing entity. In order to have a name for the notion, we call this model concurrent communicating processes. We may need to work more seriously on this model for controlling intelligent space entities of the future in order to extend our knowledge beyond the capabilities of telescopes. The Z47 processor is a good start.

Labels: , , ,