We propose a new physical medium for computation: colliding solitons. As particlelike nonlinear waves, solitons can carry and exchange information, thus acting as computing agents. Optical solitons have pulse widths measured in picoseconds or femtoseconds, and this approach could ultimately offer an alternative to electronics. This work grew from an abstract computational model called the particle machine (PM), which uses discrete propagating and colliding particles to compute. We show that this model is universal, and describe several efficient PM algorithms, such as convolution, certain systolic-array computations, and linear-time, arbitrary-precision arithmetic, including an iterative algorithm for division. This leads to the question of physical instantiation of PMs that could do useful computation, and optical solitons provide a natural example. Propagating solitons carry information in their amplitudes, velocities, and phases. We show how colliding solitons can transfer such information in nontrivial ways, thus making computation possible. We characterize the state transformations caused by collisions in a particular system of coupled optical solitons — the Manakov system — and show how to implement several computations, such as a NOT processor and certain other reversible operators. Our results resolve some questions about computational power in different soliton systems, and serve as first steps towards realizing a practical soliton-based computer.