![[Previous]](http://www-psrg.lcs.mit.edu/Hyperlatex-1.3/docsleft.gif)
![[Up]](http://www-psrg.lcs.mit.edu/Hyperlatex-1.3/docsupar.gif)
![[Next]](http://www-psrg.lcs.mit.edu/Hyperlatex-1.3/docsrigh.gif)
The first published description of the smallest known universal Turing machine. Encompassed by Minsky's more widely available book [Minsky-67].
ftp://ftp-pubs.lcs.mit.edu/pub/lcs-pubs/listings/abstracts/TR-597.html.
http://www.cs.princeton.edu:80/TR/PRINCETONCS:TR-478-94.
Abstract: In this paper we show how to embed practical computation in one-dimensional cellular automata using a model of computation based on collisions of moving particles. The cellular automata have small neighborhoods, and state spaces which are binary occupancy vectors. They can be fabricated in VLSI, and perhaps also in bulk media which support appropriate particle propagation and collisions. The model uses injected particles to represent both data and processors. Consequently, realizations are highly programmable, and do not have application-specific topology, in contrast with systolic arrays. We describe several practical calculations which can be carried out in a highly parallel way in a single cellular automaton, including addition, subtraction, multiplication, arbitrarily nested combinations of these operations, and finite- impulse-response digital filtering of a signal arriving in a continuous stream. These are all accomplished in time linear in the number of input bits, and with fixed-point arithmetic of arbitrary precision, independent of the hardware.