Tapes, Queues and Communicating Automata in DIAC

摘要

The paper defines the wheel-machine to be a finite state machine equipped with asingle queue. It then shows that wheel machines are equivalent with Turing machines. In the DIAC project the dispatching of tasks is implemented using models of devices consisting of finite state machines that have individual mailboxes. The paper gives a precise definition of mailbox automata and of the class Lambda sub M of all languages that can be accepted by mailbox automata. It gives some properties of these languages. In particular, it shows that Lambda sub 3 is contained in Lambda sub M is contained in Lambda sub 1. It shows that these mailboxes can be used as queues, in this way showing that the dispatcher model, which consists of a set of communicating mailbox automata, is Turing complete. (Copyright (c) 1992 by Faculty of Technical Mathematics and Informatics, Delft, The Netherlands.)