Copy Link
Add to Bookmark
Report
Alife Digest Number 113
Alife Digest, Number 113
Wednesday, October 27th 1993
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~ Artificial Life Distribution List ~
~ ~
~ All submissions for distribution to: alife@cognet.ucla.edu ~
~ All list subscriber additions, deletions, or administrative details to: ~
~ alife-request@cognet.ucla.edu ~
~ All software, tech reports to Alife depository through ~
~ anonymous ftp at ftp.cognet.ucla.edu in ~ftp/pub/alife (128.97.50.19) ~
~ ~
~ List maintainer: Greg Werner ~
~ Artificial Life Research Group, UCLA ~
~ ~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Today's Topics:
Calendar of Alife Related Events
Alife simulator info request
A-life video tapes
Comprehensive Kolmogorov Complexity/Randomness/Algorithmic Information
Learning robots and classifier systems
Artificial Life Workshop Announcement
****************************************************************************
Subject: Calendar of Alife Related Events
Neural Information Processing Systems, Denver, CO Nov 29-Dec 2, 1993 v98
A. L.: A Bridge towards a New AI,San Sebastian, Spain Dec 10-11, 1993 v113
Vancouver Cognitive Science Conference, BC, Canada Feb 11-12, 1994 v111
Third Conf on Evolutionary Programming, San Diego, CA Feb 24-25, 1994 v103
AAAI Spring Symposium, Stanford CA Mar 21-23, 199 v110
Cybernetics and Systems Research, Vienna April 5-8, 1994 v101,103
Florida AI Research Symposium, Pensacola Beach, FL May 5-7, 1994 v113
Integrating Knowledge and Neural Heuristics May 9-10, 1994 v111
Intnl Conf Knowledge Rep and Reasoning, Bonn, Germany May 24-27, 1994 v101
IEEE Computational Intelligence, Lake Buena Vista FL Jun 26-Jul 2, 1994 v106
Alife IV, Cambridge MA July 6-8, 1994 v108
Simulation of Adaptive Behavior, Brighton, UK Aug 8-12, 1994 v101
>From Perception to Action, Lausanne, Switzerland Sept 7-9, 1994 v111
Parallel Problem Solving in Nature, Jerusalem, Israel Oct 9-14, 1994 v102
Congress on Medical Informatics, Sao Paulo, Brazil Sept 9-14, 1995 v91
****************************************************************************
----------------------------------------------------------------------
From: Howard Andrew GUTOWITZ <gutowitz@amoco.saclay.cea.fr>
Subject: Alife simulator info request
Howard Gutowitz
Dear Alife Researcher,
I am collecting information for a monograph, "Artificial-Life
Simulators and Their Applications." While this is to be a broad
survey, I am particularly interested in 1) general-purpose Alife
simulators, and 2) simulation projects with near-to-middle term
practical applications. If you have documents and/or software which
should be referred in this report, please bring them to my attention.
Insofar as possible, I would like to be able to personally check
out all programs cited. If you have software available for
distribution, please let me know how to obtain it. I would be grateful
as well for any relevant bibliographies.
Thank you in advance for your help,
Howard Gutowitz
Email:
gutowitz@amoco.saclay.cea.fr
*or*
hag@santafe.edu
Address:
Ecole de Physique et de Chimie
Laboratoire d'Electronique
10 rue Vauquelin
75005 Paris
FRANCE
Phone:
(331) 4079-4697
or
(331) 4079-4464
Fax:
(331) 4079-4425
------------------------------
From: emmeche@connect.nbi.dk (Claus Emmeche)
Subject: A-life video tapes
I was asked by a journalist (working on the impact of the computer
revolution upon science) about the eventual existence of a video
giving some visually appealing and easy to understand examples of
artificial life/computer life systems. The only thing I could remember
was that Chris Langton once, on a chaos and biological evolution
workshop here in Denmark, played a video tape showing some very
exciting dynamic computer graphics and with general discussion about
a-life . Could anyone give me a reference to a video on artificial
life systems that might be adequate for the general public?
Thanks in advance for your help,
sincerely,
Claus Emmeche
------------------------------
From: Paul.Vitanyi@cwi.nl
Subject: Comprehensive Kolmogorov Complexity/Randomness/Algorithmic Information
(Text)Book: Appeared September 93.
Ming Li and Paul Vitanyi,
AN INTRODUCTION TO KOLMOGOROV COMPLEXITY AND ITS APPLICATIONS,
Springer Verlag, August 1993, xx+546 pp, 38 illus.
Hardcover $59.00/ISBN 0-387-94053-7/ISBN 3-540-94053-7.
(Texts and Monographs in Computer Science Series)
BLURB:
Written by two experts in the field, this is the first unified
treatment of the central ideas and their applications of Kolmogorov
complexity---the theory dealing with the quantity of information in
individual objects. The book presents a thorough, comprehensive
treatment of the subject with a wide range of illustrative
applications. Such applications include topics in general induction,
machine learning, statistical inference, theory of computation, formal
language theory, combinatorics, average case analysis of algorithms
like HEAPSORT, lower bound proof techniques, the incompressiblity
method, probability theory, randomness of individual objects or
sequences, structural complexity theory, logical depth, physics and
computation, information distance, and Boltzmann entropy.
The book is ideal for advanced undergraduate students, graduate
students and researchers in computer science, mathematics, cognitive
sciences, philosophy, electrical engineering, statistics and physics.
The text is comprehensive enough to provide enough material for a two
semester course and flexible enough for a one semester course.
Although it discusses the mathematical theories of Kolmogorov
complexity and randomness tests in detail, it does not presuppose a
background in heavy mathematics. The book is self contained in the
sense that it contains the basic requirements of computability theory,
probability theory, information theory, and coding. Included are
numerous problem sets, comments, source references and hints to
solutions of problems, as well as extensive course outlines for
classroom use.
CONTENTS:
Preface v
How to Use This Book viii
Acknowledgements x
Outlines of One-Semester Courses xii
List of Figures xix
1 Preliminaries 1
1.1 A Brief Introduction 1
1.2 Mathematical Preliminaries 6
1.2.1 Prerequisites and Notation 6
1.2.2 Numbers and Combinatorics 7
1.2.3 Binary Strings 11
1.2.4 Asymptotics Notation 14
1.3 Basics of Probability Theory 16
1.3.1 Kolmogorov Axioms 17
1.3.2 Conditional Probability 18
1.3.3 Continuous Sample Spaces 19
1.4 Basics of Computability Theory 22
1.4.1 Effective Enumerations and Universal Machines 26
1.4.2 Undecidability of the Halting Problem 32
1.4.3 Enumerable Functions 34
1.4.4 Feasible Computations 35
1.5 The Roots of Kolmogorov Complexity 45
1.5.1 Randomness 46
1.5.2 Prediction and Probability 55
1.5.3 Information Theory and Coding 61
1.5.4 State Symbol Complexity 79
1.6 History and References 80
2 Algorithmic Complexity 87
2.1 The Invariance Theorem 90
2.2 Incompressibility 95
2.3 Complexity C(x) as an Integer Function 101
2.4 Random Finite Sequences 105
2.5 *Random Infinite Sequences 112
2.6 Statistical Properties of Finite Sequences 126
2.6.1 Statistics of 0's and 1's 127
2.6.2 Statistics of Blocks 130
2.6.3 Length of Runs 132
2.7 Algorithmic Properties of 134
2.8 Algorithmic Information Theory 140
2.9 History and References 165
3 Algorithmic Prefix Complexity 169
3.1 The Invariance Theorem 171
3.2 Incompressibility 175
3.3 Prefx Complexity K(x) as an Integer Function 177
3.4 Random Finite Sequences 177
3.5 *Random Infinite Sequences 180
3.6 Algorithmic Properties of K(x) 188
3.7 *The Complexity of the Complexity Function 190
3.8 *Symmetry of Algorithmic Information 194
3.9 History and References 209
4 Algorithmic Probability 211
4.1 Enumerable Functions Revisited 212
4.2 A Nonclassical Approach to Measures 214
4.3 Discrete Sample Space 216
4.3.1 Universal Enumerable Semimeasure 217
4.3.2 A Priori Probability 221
4.3.3 Algorithmic Probability 223
4.3.4 The Coding Theorem 223
4.3.5 Randomness by Sum Tests 228
4.3.6 Randomness by Payoff Functions 232
4.4 Continuous Sample Space 234
4.4.1 Universal Enumerable Semimeasure 234
4.4.2 A Priori Probability 238
4.4.3 *Solomonoff Normalization 242
4.4.4 *Monotone Complexity and a Coding Theorem 243
4.4.5 *Relation Between Complexities 246
4.4.6 *Randomness by Integral Tests 247
4.4.7 *Randomness by Martingale Tests 254
4.4.8 *Randomness by Martingales 256
4.4.9 *Relations Between Tests 258
4.5 History and References 268
5 Inductive Reasoning 275
5.1 Introduction 275
5.2 Bayesian Reasoning 279
5.3 Solomonoff's Induction Theory 282
5.3.1 Formal Analysis 284
5.3.2 Application to Induction 290
5.4 Recursion Theory Induction 291
5.4.1 Inference of Hypotheses 291
5.4.2 Prediction 292
5.4.3 Mistake Bounds 293
5.4.4 Certification 294
5.5 Pac-Learning 295
5.5.1 Definitions 296
5.5.2 Occam's Razor Formalized 296
5.6 Simple Pac-Learning 300
5.6.1 Discrete Sample Space 301
5.6.2 Continuous Sample Space 305
5.7 Minimum Description Length 308
5.8 History and References 318
6 The Incompressibility Method 323
6.1 Two Examples 324
6.2 Combinatorics 328
6.3 Average Case Complexity of Algorithms 334
6.3.1 Heapsort 334
6.3.2 Longest Common Subsequence 338
6.3.3 m -Average Case Complexity 340
6.4 Languages 344
6.4.1 Formal Language Theory 344
6.4.2 On-Line CFL Recognition 349
6.4.3 Multihead Automata 351
6.5 Machines 356
6.5.1 *Turing Machine Time Complexity 356
6.5.2 Parallel Computation 362
6.6 History and References 370
7 Resource-Bounded Complexity 377
7.1 Mathematical Theory 378
7.1.1 Computable Majorants 381
7.1.2 Resource-Bounded Hierarchies 386
7.2 Language Compression 392
7.2.1 With an Oracle 393
7.2.2 Without an Oracle 396
7.2.3 Ranking 399
7.3 Computational Complexity 401
7.3.1 Constructing Oracles 402
7.3.2 P-Printability 405
7.3.3 Instance Complexity 406
7.4 Kt Complexity 410
7.4.1 Universal Optimal Search 411
7.4.2 Potential 413
7.5 Logical Depth 421
7.6 History and References 428
8 Physics and Computation 433
8.1 Reversible Computation 434
8.1.1 Energy Dissipation 434
8.1.2 Reversible Logic Circuits 435
8.1.3 A Ballistic Computer 436
8.1.4 Reversible Turing Machines 439
8.2 Information Distance 441
8.2.1 Max Distance 442
8.2.2 Picture Distance 446
8.2.3 Reversible Distance 448
8.2.4 Sum Distance 450
8.2.5 Metrics Relations and Dimensional Properties 452
8.2.6 Thermodynamics of Computing 455
8.3 Thermodynamics 458
8.3.1 Classical Entropy 458
8.3.2 Statistical Mechanics and Boltzmann Entropy 461
8.3.3 Gibbs Entropy 467
8.4 Entropy Revisited 468
8.4.1 Algorithmic Entropy 469
8.4.2 Algorithmic Entropy and Randomness Tests 473
8.4.3 Entropy Stability and Nondecrease 478
8.5 Chaos, Biology, and All That 486
8.6 History and References 490
Bibliography 493
Index 527
------------------------------
From: root@trivia.coginst.uwf.edu (trivia operator)
CALL FOR PAPERS
FLAIRS-94
Florida AI Research Symposium
Pensacola Beach, Florida
May 5-7, 1994
The Seventh Annual Florida AI Research Symposium seeks high quality
international submissions in all areas of AI. We are especially
interested in papers describing knowledge-based approaches to the
construction of intelligent systems. The symposium will strive for a
balance between theory and practice. All accepted papers will appear
in the conference proceedings.
SUBMISSION OF PAPERS
Authors must submit 6 copies of an extended abstract of 1200 to 1600
words. The extended abstract should not identify the author or
affiliation in any manner. Please include one separate cover page
containing the author's name(s), address, phone number, affiliation,
paper title, and topic area. In case of multiple authors, all
correspondence will be sent to the first author unless otherwise
requested.
Abstracts must be received by October 18, 1993. Abstracts received
after this date will not be considered. The Program Committee's
decisions will be mailed during December of 1993. Authors of accepted
papers will be expected to submit their final camera-ready copy of
their full papers by February 14, 1994.
For information concerning submissions or to submit an abstract contact:
Douglas D. Dankel II
FLAIRS-94 Program Committee Chair
E301 CSE, C.I.S., University of Florida
Gainesville, FL 32611
Tel: 904-392-1387, Fax: 904-392-1220
ddd@panther.cis.ufl.edu
WORKSHOPS
In addition to the FLAIRS conference, four workshops are being planned
for May 4, 1994. One workshop registration fee will be waived for
those who register for FLAIRS. If you are interested in any of the
workshops -- please contact the Workshop organizer directly.
1. Artificial Life and AI:
Pat Hayes, University of Illinois
Email: hayes@hpp.stanford.edu or phayes@cs.uiuc.edu
2. Analogy & Computation:
Eric Dietrich, SUNY Binghamton
Email: dietrich@bingsuns.cc.binghamton.edu
3. Temporal Representation & Reasoning:
Scott Goodwin & Howard Hamilton, University of Regina
Email: Time94@cs.uregina.ca
4. AI & Ethical Reasoning:
Umar Khan, U.S. Department of Treasury
Email: khan@itd.nrl.navy.mil
GENERAL CHAIRS:
Alberto J. Canas
University of West Florida
Tel. 904-474-2253 Fax. 904-474-3023
acanas@ai.uwf.edu
David Kuncicky
Florida State University
Tel. 904-644-4290 Fax. 904-644-0058
kuncick@nu.cs.fsu.edu
PROGRAM COMMITTEE:
J. Adams-Webber, Brock University
C. Araya, Instituto Tecnologico de Costa Rica
J. Bezdek, University of West Florida
P. Bobbie, FAMU
L. Boggess, Mississippi State University
G. Boy, EURISCO
J. Bradshaw, EURISCO
H. Chung, Texas A&M University
W. Clancey, IRL
V. Dahl, Simon Fraser University
C. deBessonet, Louisiana Law Institute
E. Dietrich, SUNY Binghamton
J. Dukes-Schlossberg, Lockheed AI Center
A. Ericsson, Florida State University
M. Fishman, Eckerd College
K. Ford, University of West Florida
L. Fu, University of Florida
J. Glasgow, Queen's University
A. Gonzalez, University of Central Florida
S. Goodwin, University of Regina
N. Groleau, NASA
T. Gruber, Stanford University
H. Hamilton, University of Regina
M. Harandi, University of Illinois
P. Hayes, University of Illinois
F. Hoffman, Florida Atlantic University
S. Hruska, Florida State University
M. Huhns, MCC
J. Kelly, Tulane University
U. Khan, U.S. Dept. of the Treasury
H. Kyburg, University of Rochester
D. Leake, Indiana University
W. Lehnert, University of Massachussetts
R. Loganantharaj, Univ. of SW Louisiana
S. Louis, Indiana University
G. Luger, University of New Mexico
R. Morris, Florida Institute of Technology
F. Petry, Tulane University
R. Plant, University of Miami
A. Rappaport, Neuron Data
P. Selfridge, AT&T Bell Labs
D. Setliff, University of Pittsburg
V. Shalin, SUNY at Buffalo
E. Simoudis, Lockheed
J. Stewman, Eckerd College
D. Subramanian, Cornell University
D. Tamir, Florida Institute of Technology
J. Tenenberg, Indiana Univ. at South Bend
S. Walczak, University of Tampa
W. Walker, University of Florida
J. Wertheimer, M.I.T.
R. Yager, Iona College
**CONFERENCE IS SPONSORED BY THE FLORIDA AI RESEARCH SOCIETY**
------------------------------
From: mdorigo@ulb.ac.be (Marco DORIGO)
Subject: Learning robots and classifier systems
The following technical report is available
Marco Colombetti, Marco Dorigo
TR-93-023, International Computer Science Institute, Berkeley, CA.
"Training Agents to Perform Sequential Behavior"
This paper is concerned with training an agent to perform sequential
behavior. In previous work we have been applying reinforcement
learning techniques to control a reactive robot. Obviously, a pure
reactive system is limited in the kind of interactions it can learn.
In particular, it can only learn what we call pseudo-sequences, that
is sequences of actions in which the transition signal is generated by
the appearance of a sensorial stimulus. We discuss the difference
between pseudo-sequences and proper sequences, and the implication
that these differences have on training procedures. A result of our
research is that, in case of proper sequences, for learning to be
successful the agent must have some kind of memory; moreover it is
often necessary to let the trainer and the learner communicate. We
study therefore the influence of communication on the learning
process. First we consider trainer-to-learner communication
introducing the concept of reinforce ment sensor, which let the
learning robot explicitly know whether the last reinforcement was a
reward or a punishment; we also show how the use of this sensor
induces the creation of a set of error recovery rules. Then we
introduce learner-to-trainer communication, which is used to
disambiguate indeterminate training situations, that is situations in
which observation alone of the learner behavior does not provide the
trainer with enough information to decide if the learner is performing
a right or a wrong move. All the design choices we make are discussed
and compared by means of experiments in a simulated world.
Hardcopies can be requested to
Marco Dorigo, Ph.D.
IRIDIA
Universite Libre de Bruxelles
Avenue Franklin Roosvelt 50
CP 194/6
1050 Bruxelles, Belgium
mdorigo@ulb.ac.be
Tel. +32-2-6503167
Fax +32-2-6502715
or to
Mark Kempson
International Computer Science Institute
1947 Center Street
Suite 600
Berkeley, California 94704-1105
USA
kempson@icsi.berkeley.edu
------------------------------
From: arantza@cogs.susx.ac.uk (Arantza Etxeberria)
Subject: Artificial Life Workshop Announcement
"Artificial Life: a Bridge towards a New Artificial Intelligence"
Palacio de Miramar (San Sebastian, Spain)
December 10th and 11th, 1993
Workshop organised by the
Department of Logic and Philosophy of Science,
Faculty of Computer Science
&
Institute of Logic, Cognition, Language and Information (ILCLI)
of the
University of the Basque Country (UPV/EHU)
Directors:
Alvaro Moreno (University of the Basque Country)
Francisco Varela (CREA, Paris)
This Workshop will be dedicated to a discussion of the impact of
works on Artifical Life in Artificial Intelligence. Artificial
Intelligence (AI) has traditionally attempted to study cognition as an
abstract phenomenon using formal tools, that is, as a disembodied
process that can be grasped through formal operations, independent of
the nature of the system that displays it. Cognition appears as an
abstract representation of reality. After several decades of research
in this direction the field has encountered several problems that have
taken it to what many consider a "dead end": difficulties in
understanding autonomous and situated agencies, in relating behaviour
in a real environment, in studying the nature and evolution of
perception, in finding a pragmatic approach to explain the operation
of most cognitive capacities such as natural language, context
dependent action, etc.
Artificial Life (AL) has recently emerged as a confluence of very
different fields trying to study different kinds of phenomena of
living systems using computers as a modelling tool, and, at last,
trying to artificially (re)produce a living or a population of living
systems in real or computational media. Examples of such phenomena
are prebiotic systems and their evolution, growth and development,
self-reproduction, adaptation to an environment, evolution of
ecosystems and natural selection, formation of sensory-motor loops,
autonomous robots. Thus, AL is having an impact on classic life
sciences but also on the conceptual foundations of AI and new
methodological ideas to Cognitive Science.
The aim of this Workshop is to focus on the last two points and to
evaluate the influence of the methodology and concepts appearing in AL
for the development of a new ideas about cognition that could
eventually give birth to a new Artificial Intelligence. Some of the
sessions consist on presentations and replies on a specific subject by
invited speakers while others will be debates open to all participants
in the workshop.
MAIN TOPICS:
* A review of the problems of FUNCTIONALISM in Cognitive Science
and Artificial Life.
* Modelling Neural Networks through Genetic Algorithms.
* Autonomy and Robotics.
* Consequences of the crisis of the representational models of cognition.
* Minimal Living System and Minimal Cognitive System
* Artificial Life systems as problem solvers
* Emergence and evolution in artificial systems
SPEAKERS
S. Harnad
P. Husbands
G. Kampis
B. Mac Mullin
D. Parisi
T. Smithers
E. Thompson
F. Varela
Further Information:
Alvaro Moreno
Apartado 1249
20080 DONOSTIA
SPAIN
E. Mail: biziart@si.ehu.es
Fax: 34 43 311056
Phone: 34 43 310600 (extension 221)
34 43 218000 (extension 209)
------------------------------
End of ALife Digest
*******************
