Education
Kari received his Doctor of Philosophy in 1990 from the University of Turku. His dissertation, supervised by Arto Salomaa.
mathematician computer scientist
Kari received his Doctor of Philosophy in 1990 from the University of Turku. His dissertation, supervised by Arto Salomaa.
Kari is currently a professor at the Department of Mathematics, University of Turku. Wang tiles are unit squares with colored markings on each side. They may be used to tesselate the plane, but only with tiles that have matching colors on adjoining edges.
The problem of determining whether a set of Wang tiles forms a valid tessellation is undecidable, and its undecidability rests on finding sets of Wang tiles that can only tesselate the plane aperiodically, in such a way that no translation of the plane is a symmetry of the tiling.
The first set of aperiodic Wang tiles found, by Robert Berger, had over 20,000 different tiles in lieutenant Kari reduced the size of this set to only 14, by finding a set of tiles that (when used to tile the plane) simulates the construction of a Beatty sequence by Mealy machines.
The same approach was later shown to lead to aperiodic sets of 13 tiles, the minimum known. Kari has also shown that the Wang tiling problem remains undecidable in the hyperbolic plane, and has discovered sets of Wang tiles with additional mathematical properties.
Kari has also used the Wang tiling problem as the basis of proofs that several algorithmic problems in the theory of cellular automata are undecidable.
In particular, in his thesis research, he showed that it is undecidable to determine whether a given cellular automaton rule in two or more dimensions is reversible. Foreign one-dimensional cellular automata, reversibility is known to be decidable, and Kari has provided tight bounds on the size of the neighborhood needed to simulate the reverse dynamics of reversible one-dimensional automata.
