Algorithmic Information and Automata Theory

A Workshop with Hands-on Training, Rovaniemi, Finland, 21-29 May 1996

Sponsored by
Regional Council of Lapland
European Social Fund
Sun Microsystems Oy

This 7-and-a-half day workshop, held in the Rovaniemi Institute of Technology, covered the following topics: symbolic computing, algorithms, complexity and incompleteness.

The lectures and their subjects were as follows:

Professor Gautam Dasgupta:
Hands-on Introduction to Programming in Mathematica (11 hours)

Dr. Gregory Chaitin:
A New Version of Algorithmic Information Theory (21 hours)

Professor Klaus Sutner:
Automata Theory in Mathematica (21 hours)

Dr. Eric Wagner:
Abstract Data Type Theory (2 hours)

This event was attended by researchers, engineers, teachers and students (also from high schools). The number of participants ranged from 27 to 35 depending on the day. Participants came from England (1), Finland (16-24), Russia (4), and the USA (6).

The workshop started with hands-on training sessions by Professor Gautam Dasgupta from Columbia University, New York. The first session was a Hands-on Introduction to Mathematica (21 May, afternoon). The second day as a whole was a Tutorial Day on Programming in Mathematica (22 May). Then Dr. Gregory Chaitin (IBM, New York), Professor Klaus Sutner (Carnegie-Mellon University, Pittsburgh), and Dr. Eric Wagner (Wagner Mathematics, New York), conducted a General Lecture Day on 23 May. Dr. Chaitin and Professor Sutner taught on Laboratory Sessions from 24 to 29 May. The hands-on training sessions were held in the Mathematica laboratory of the Rovaniemi Institute of Technology.

The scientific programme was accompanied by an ample social programme which included a smoke sauna bath offered by Matti Pelttari, the Mayor of Rovaniemi, excursions to the Arctic Center and to the Finnish National Park in the Pyhätunturi region, a workshop dinner and a night party (with the midnight sun).

Photos from the Workshop

The subjects of lectures and laboratory sessions are explained below.

Hands-on Introduction to Programming in Mathematica

The teacher of these sessions, Professor Dasgupta, is a faculty member of the department of civil engineering and engineering mechanics, Columbia University, New York. He develops computer based courseware for engineers, scientists and teachers. Professor Dasgupta is the chair of the executive committee of the International Mathematica Symposium (IMS) - a series of research oriented symposia on the applications of Mathematica in science, mathematics, technology, business and education.

The topics of this part of the course included List Manipulation, Pattern Matching and String Objects, along with the various Programming Styles in Mathematica.

For more information about Professor Dasgupta, please visit

A New Version of Algorithmic Information Theory

Dr. Chaitin has figured out how to actually program the algorithms in the proofs of all the key information-theoretic incompleteness theorems in algorithmic information theory. His research explores the limits of mathematics and his results even enhance and strengthen Kurt Gödel's fundamental incompleteness theorems (from 1931) which many regard as the most fundamental to the foundations of mathematics. Moreover, Gödel's theorems are central in the philosophy of conciousness as discussed by Roger Penrose in his new book, The Shadows of the Mind (Oxford University Press, 1995).

Basically, the results of Dr. Chaitin say that some things in mathematics are true for no reason at all, i.e., accidentally or at random. Remarkably, he is able to explain his profound (and technically complicated) results in such a simple way that is understandable for the laity, too.

Dr. Chaitin starts his newest report as follows: "In a remarkable development, I have constructed a new definition for a self-delimiting universal Turing machine (UTM) that is easy to program and runs very quickly. This provides a new foundation for algorithmic information theory (AIT), which is the theory of the size in bits of programs for self-delimiting UTM's. Previously, AIT had an abstract mathematical quality. Now it is possible to write down executable programs that embody the constructions in the proofs of theorems. So AIT goes from dealing with remote idealized mythical objects to being a theory about practical down-to-earth gadgets that one can actually play with and use."

With the aid of the Mathematica computing environment, Dr. Chaitin has developed LISP interpreters, which in turn are used, for example, in producing the monster exponential diophantine equation that leads in the area of arithmetic, where reasoning of solutions (finite number or not) is completely powerless.

It was fascinating to hear Dr. Chaitin's views on how his results justify experimental mathematics.

For further information concerning the results by Dr. Chaitin, see:

Related exciting books are also:

Automata Theory in Mathematica

The purpose of this workshop was to introduce the user to automata, a Mathematica based package that deals with finite state machines and their syntactic semigroups, as well as one-dimensional cellular automata. The package creates an environment that makes it fairly easy and natural to calculate with finite state machines, the way a hand-held calculator facilitates computation with real numbers.

automata is obviously suited as a teaching tool. Professor Sutner presented a number of notebooks that can be used as electronic lecture notes in the usual course on automata theory or discrete mathematics. The package has also turned out to be useful in research, notably in the area of cellular automata. Examples were shown to demonstrate how the combination of fast external code and Mathematica as a central computing engine and repository makes for a productive environment.

While all algorithms in automata are fully implemented in Mathematica code and can be used in a pure Mathematica session, a crucial part of the package is an external calculator that can be called via Mathlink. The calculator is based on C++ library and can also be used independently of Mathematica to perform very large computations. The external code has been designed very carefully to allow the user to add on his/her own special purpose algorithms.

The Structure of the Automata Computing Environment is found here.

There were an abundance of lecture notes and hand-outs, some printed and some in electronic form.

Lectures for Automata Theory in Mathematica discussed the following topics:

The Automata Package can be downloaded from here.

Abstract Data Types:
An Introduction to the ``Algebraic Approach''

Dr. Eric Wagner from Wagner Mathematics, New York, writes about his lecture as follows:

"Informally speaking, data types are the entities that programming languages manipulate. Early programming languages tended to employ only a small, fixed collection of data types such as Integers, Reals, Arrays and, sometimes, Booleans. However, starting in the 1970 's, programming languages were developed that gave the user the power to define data types. These developments were accompanied by parallel efforts in the theoretical computer science community to understand, describe, and specify data types in a language independent manner. The algebraic approach centers on the idea that a data type is not just a collection of entities but also includes an associated collection of operations on these entities. On the practical side, this idea matches the concept of module (in SIMULA or MODULA) or package (in ADA). On the theoretical side, it is essentially the concept of a ``universal south''. Since the 1970's this connection between practical data types and universal south has been explored and exploited by a wide group of researchers and has lead to the development of many techniques for the specification of data types and programs."

In his talk Dr. Wagner introduced the basic ideas of the algebraic approach to data types, gave indications of its powers and limitations, and made remarks about the potential connections with Mathematica.


This training course was a self-contained hands-on minicourse on automata and algorithmic information theory.

Even though the main contents of this training course were theoretical in nature, it clearly turned out that for developing the concepts, the use of computers was well justified. Indeed, the computers allowed the participants to build executable algorithms that could be used for experiments right away. Especially the feedback from high school students was very encouraging. The teachers and organisers of the workshop regard this as a remarkable fact for education - it was possible, in a very concrete manner, to take hold of the abstract concepts involved.

Dr. Chaitin's and Professor Sutner's software packages offer fascinating educational tools for studying the limits of mathematics and automata theory. Moreover, the Automata Package (with External Calculator) offers an environment for very large computations with automata in research and engineering.

Both Dr. Chaitin and Professor Sutner have developed their Mathematica (and MathLink) environment for UNIX workstations. Nevertheless, during the workshop the participants were able to use these software packages on Macintosh and MS-Windows machines as well.

A photograph of Dr. Chaitin and Professor Sutner and
a photograph of Professors Dasgupta and Sutner can be seen from here.


From here you may obtain information about Rovaniemi and the region of the Arctic Circle.

Further details:

Dr. Veikko Keränen, Department of Mathematics
tel +358 16 331 3360, +358 400 289 509 (GSM),,

Dr. Antero Hietamäki, Department of Physics
tel +358 16 331 3320,

Sec. Merja Kähkönen, Department of Further Education and Technology Services
tel +358 16 331 3353, fax +358 16 331 3322,

Rovaniemi Institute of Technology, Jokiväylä 11, 96300 Rovaniemi, Finland

The organisers at the Rovaniemi Institute of Technology wish to express their gratitude to all the keynote lecturers and to all the participants for their warm and active participation in the Workshop.

With Best Regards,

Antero, Jalil, Juha, Markku, Matti, Merja, Mika, Olli, Veikko, ...


Structures, Graphics and Music
This link provides information about our research on avoidable regularities in strings.
The included graphics and music is based on an abelian square-free string over a four letter alphabet
(by Veikko Keränen, Tomi Laakso, and Erik Jensen).