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

Биография

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

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

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

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

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

Примечания

Ссылки