Jarkko Kari
Encyclopedia
Jarkko J. Kari is a Finnish
mathematician
and computer scientist
, known for his contributions to the theory of Wang tile
s and cellular automata. Kari is currently a professor at the Department of Mathematics, University of Turku
.
s are unit square
s 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 tesselation 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 it. 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 machine
s. 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
. For 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.
Finland
Finland , officially the Republic of Finland, is a Nordic country situated in the Fennoscandian region of Northern Europe. It is bordered by Sweden in the west, Norway in the north and Russia in the east, while Estonia lies to its south across the Gulf of Finland.Around 5.4 million people reside...
mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
and computer scientist
Computer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
, known for his contributions to the theory of Wang tile
Wang tile
Wang tiles , first proposed by mathematician, logician, and philosopher Hao Wang in 1961, are a class of formal systems...
s and cellular automata. Kari is currently a professor at the Department of Mathematics, University of Turku
University of Turku
The University of Turku , located in Turku in southwestern Finland, is the second largest university in the country as measured by student enrollment, after University of Helsinki. It was established in 1920 and also has faculties at Rauma, Pori and Salo...
.
Biography
Kari received his Ph.D. in 1990 from the University of Turku; his dissertation, supervised by Arto K. Salomaa.Research
Wang tileWang tile
Wang tiles , first proposed by mathematician, logician, and philosopher Hao Wang in 1961, are a class of formal systems...
s are unit square
Unit square
In mathematics, a unit square is a square whose sides have length 1. Often, "the" unit square refers specifically to the square in the Cartesian plane with corners at , , , and .-In the real plane:...
s 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 tesselation is undecidable
Undecidable
Undecidable may refer to:In mathematics and logic* Undecidable problem - a decision problem which no algorithm can decide* "Undecidable" is sometimes used as a synonym of "independent", where a formula in mathematical logic is independent of a logical theory if neither that formula nor its negation...
, and its undecidability rests on finding sets of Wang tiles that can only tesselate the plane aperiodically
Aperiodic tiling
An aperiodic tiling is a tiling obtained from an aperiodic set of tiles. Properly speaking, aperiodicity is a property of particular sets of tiles; any given finite tiling is either periodic or non-periodic...
, 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 it. 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
Beatty sequence
In mathematics, a Beatty sequence is the sequence of integers found by taking the floor of the positive multiplesof a positive irrational number...
by Mealy machine
Mealy machine
In the theory of computation, a Mealy machine is a finite-state machine whose output values are determined both by its current state and the current inputs. The outputs change asynchronously with respect to the clock, meaning that the outputs change at unpredictable times, making timing analysis...
s. 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
Hyperbolic plane
In mathematics, the term hyperbolic plane may refer to:* A two-dimensional plane in hyperbolic geometry* A two-dimensional plane in Minkowski space...
, 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
Reversible cellular automaton
A reversible cellular automaton is a cellular automaton in which every configuration has a unique predecessor. Several methods of constructing reversible cellular automata are known, including the block cellular automaton and second-order cellular automaton methods...
. For 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.