Abstract. Computation- and construction-universality in cellular automata(CA), first studied by von Neumann, has attracted steady research efforts, over the years, most employing synchronous CA. Asynchronous cellular automata(ACA),though of interest as most interactions in nature are asynchronous, have not been used for this task, other than by the indirect way of simulating a synchronous CA. In this paper, we propose a universal constructor on a self-timed cellular automaton (STCA), a particular type of ACA, in which cells are divided in four partitions, each with four states.

DOI: 10.1007/b102055