Abstract and-parallel machines

Several abstract models of fine-grained parallelism, suited to symbolic pro gramming languages, are suggested. The first, the and-parallel Turing machi ne, can be viewed as a generalization of the deterministic Turing machine i n which the infinite tape is replaced by an infinite tree-like tape on whic h processors work in parallel. with this model one can express in a very na tural way communication between processors, suspension, and synchronization . There are examples in which the processing time is polylogarithmic in the size of the input while for a nondeterministic Turing machine that looks a t its input the time must be at least of the order of magnitude of the size of the input. Then a stronger model, the parallel rewriting machine, is in troduced. Transitions are formulated as rewrite rules, resulting in a machi ne that is much easier to program. This also adds a 'pointer capability' to the previous machine. Since this machine gets the program in a form that r eflects its meaning, problems of synchronization are easily handled-rewrite rules just cannot be applied before arguments reach the right form. In bot h models a processor can launch other processors on subcomputations, but pr ocessing at a parent node must wait for answers from all of its "children". One can introduce more powerful models that contain the possibility of an interrupt-if the answer from one child (or several children) is sufficient to continue the computation at the parent, the computation started by the o ther children can and should be interrupted. These interrupt machines are m uch more powerful than the previous two, but it does not seem to be much mo re difficult to implement them. Although the machines considered are very p owerful-the parallel rewriting machine can compute the permanent in polynom ial time and the and-parallel Turing machine with interrupt can simulate a nondeterministic Turing machine and an alternating Turing machine-they can be seen as models of realistic machines if time and space are suitably rest ricted.