Tapes, Queues and Communicating Automata in DIAC

摘要

A study which defines the wheel machine to be a finite state machine equipped with a single queue is presented. Wheel machines are shown to be 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. A precise definition of mailbox automata and of the class L(sub M) of all languages that can be accepted by mailbox automata is given. Some properties of these languages are given. It is shown 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.