🚀 go-pugleaf

DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES

THEORY SEMINAR

                    -Wednesday, January 27, 1993

Paul  Vitanyi  (CWI/Universiteit  van  Amsterdam), will
speak "On the Information Distance".

TIME:                11:30 a.m. - 12:30 p.m.

ROOM:                DC 1304

ABSTRACT

We  investigate  the  notion  of  absolute  information
distance.  It turns out that very differently motivated
proposals  arising  from  the  physics  notion  of both
reversible  (energy-free)  computations  and reversible
computations   coincide.  This  distance  is  also  the
optimal  cognitive distance, improving earlier results.
A    related    distance   measures   the   amount   of
nonreversibility   (minimum  dissipated  energy)  of  a
computation.  This  work  emerged  from  the physics of
energy-free   computation  and  the  quest  in  pattern
recognition for the notion of `picture similarity'. The
mathematical  techniques  involve Kolmogorov complexity
(Algorithmic  Information  Theory).  This is joint work
with Charles Bennett, Peter Gacs, Ming Li, and Wojtiech
Zurek.