# Bulletin of the American Physical Society

# APS March Meeting 2018

## Monday–Friday, March 5–9, 2018; Los Angeles, California

### Session P47: Nonlinear Dynamics and Chaos

2:30 PM–5:30 PM,
Wednesday, March 7, 2018

LACC
Room: 507

Sponsoring
Units:
GSNP DFD

Chair: Alexander Levine, Univ of California - Los Angeles

### Abstract: P47.00012 : The minimal “hidden” computer needed to implement a computation*

4:42 PM–4:54 PM

#### Presenter:

David Wolpert

(Santa Fe Institute)

#### Authors:

David Wolpert

(Santa Fe Institute)

Jeremy Owen

(MIT)

Artemy Kolchinsky

(Santa Fe Institute)

We consider the problem of constructing a physical process to implement some desired (single-valued) function f over a set of “visible” states X. The physical process is represented as a time-inhomogeneous continuous-time Markov chain (CTMC), for example modeling the dynamics of a driven system connected to a heat bath. A prototypical example is a physical implementation of a logical gate in a circuit.

In general, there exists functions f which are not implementable by any possible CTMC, even approximately. However, we demonstrate that for any f, an implementation is always possible if the system has access to some additional "hidden" states not in X. We then consider a natural decomposition of any such CTMC-based implementation into a countable set of discrete steps, demarcated from one another by the raising or lowering of barriers restricting probability flow between states. We demonstrate a tradeoff between the minimal number of hidden states and the minimal number of such steps needed to implement any given f. This tradeoff is analogous to space / time tradeoffs in computational circuit complexity theory - except that it arises even within each gate in such a circuit.

*We acknowledge support of Grant No. FQXi-RFP-1622 from the FQXi foundation, and NSF Grant No. CHE-1648973.

## Follow Us |
## Engage
Become an APS Member |
## My APS
Renew Membership |
## Information for |
## About APSThe American Physical Society (APS) is a non-profit membership organization working to advance the knowledge of physics. |

© 2018 American Physical Society
| All rights reserved | Terms of Use
| Contact Us

**Headquarters**
1 Physics Ellipse, College Park, MD 20740-3844
(301) 209-3200

**Editorial Office**
1 Research Road, Ridge, NY 11961-2701
(631) 591-4000

**Office of Public Affairs**
529 14th St NW, Suite 1050, Washington, D.C. 20045-2001
(202) 662-8700