Кари, Яркко

Яркко Кари (Jarkko Kari) — финский математик и программист, известный за вклад в разработку теорий «Домино Вана» и клеточного автомата. В данный момент Кари работает профессором на математическом отделении Университета Турку.

Биография

Степень кандидата наук Кари получил в 1990 году в Университете Турку. Его диссертационную работу курировал Арто Саломаа.

Был женат на Лиле Кари, которая одно время училась в Турку. После развода Лила Кари стала профессором информатики в Университете Западного Онтарио в Канаде.

Исследования

Домино Вана — это множество единичных квадратов, стороны которых закрашены по-разному. Из них можно выложить целую мозаику, однако таким образом, чтобы друг к другу примыкали только рёбра одного цвета. Проворачивать квадраты и отражать их зеркально для выполнения этой задачи нельзя. Задача Вана связана с проблемой неразрешимости в математической логике. Ван предположил, что мозаика, выложенная при помощи различных квадратов, примет в конечном итоге форму периодической мозаики. Для решения задачи Вана в 1964 году Роберт Бергер использовал 20426 различных квадратов. В свою очередь, Кари использовал набор, состоявший только из 14 квадратов, что позволило ему найти набор, который повторял процесс создания последовательности Битти на автоматах Мили. Впоследствии такой подход позволил выложить апериодическую мозаику из набора, состоявшего из 13 квадратов, что является на данный момент набором с минимальным на сегодняшний день числом квадратов. Кари также продемонстрировал, что проблема Вана остаётся неразрешимой для гиперболической плоскости, обнаруживая при этом элементы Вана с дополнительными математическими свойствами.

Кари также, опираясь на проблему Вана, доказал, что в теории клеточного автомата существует ряд алгоритмических проблем, которые можно считать неразрешимыми. В частности, Кари показал, что невозможно определить, является ли данный клеточный аппарат в двух или более измерениях реверсивным или нет. Для одномерных клеточных автоматах реверсивность считается разрешимой, и Кари обозначил жёсткие границы для размера окрестности точки, необходимого для имитации обратной динамики реверсивных одномерных автоматов.