Information Flow in Cellular Automata

Joseph Razavi (Manchester)

Frank Adams 1,

A long standing intuition about physical computations is that
they satisfy two constraints: a finite region can hold only a finite
amount of information, and information must flow continuously through
space.

In concrete models, it is usually physical state, rather than information,
which is modelled, and continuous information flow is formalized by local
determinism. This seems too strong; for instance, it may be true locally
(near each moment of time) while failing to be true globally.

I will discuss cellular automata, a locally deterministic model. By
reinterpreting local state as local information, I will show that local
determinism can be relaxed to something which looks more like continuity,
without allowing uncomputable phenomena.
Import this event to your Outlook calendar
▲ Up to the top