## When Can Solitons Compute?

**Mariusz H. Jakubowski****Ken Steiglitz***Deptartment of Computer Science,**Princeton University, Princeton, NJ, USA*

**Richard K. Squier***Deptartment of Computer Science,**Georgetown University, Washington, DC, USA*

#### Abstract

The possibility of using soliton interactions in a one-dimensional bulk medium is explored as a basis for a new kind of computer. Such a structure is "gateless,'' that is, all computations are determined by an input stream of solitons. Intuitively, the key requirement for accomplishing this is that soliton collisions be *nonoblivious*; that is, solitons should transfer state information during collisions. All the well-known systems described by *integrable* partial differential equations (PDEs) such as the Korteweg--de Vries, sine-Gordon, cubic nonlinear Schrödinger, and perhaps *all* integrable systems, are oblivious when displacement or phase is used as state. A cellular automaton (CA) model is presented, the *oblivious soliton machine* (OSM), that captures the interaction of solitons in systems described by such integrable PDEs. We then prove that OSMs with either quiescent or periodic backgrounds can only do computation that requires time at most cubic in the input size; and thus, are far from being computation-universal. Next, a more general class of CA is defined, *soliton machines* (SMs), which describe systems with more complex interactions. It is shown that an SM with a *quiescent* background can have at least the computational power of a finite-tape Turing machine, whereas an SM with a *periodic* background can be universal. The search for useful nonintegrable (and nonoblivious) systems is challenging: We must rely on numerical solution, collisions may be at best only near-elastic, and collision elasticity and nonobliviousness may be antagonistic qualities. As a step in this direction, it is shown that the logarithmically nonlinear Schrödinger equation (log-NLS) supports quasi-solitons (gaussons) whose collisions are, in fact, very near-elastic and strongly nonoblivious. It is an open question whether there is a physical system that realizes a computation-universal soliton machine.