Введение

Финский математик и компьютерный ученый Jarkko J. Kari - финский математик и компьютерный ученый, известный своим вкладом в теорию плиток Ван и клеточных автоматов. В настоящее время Кари является профессором кафедры математики Университета Турку.

Биография

Кари получил степень доктора философии. Д. в 1990 году в Университете Турку; его диссертация, под руководством Артo Salomaa. Он женился на Лиле Кари, позже студенте математики в Турку; они развелись, и впоследствии Лила Кари стала профессором информатики в Университете Западной Онтарио в Канаде.

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

Плитка Ван - это единичные квадраты с цветными отметками с каждой стороны; они могут использоваться для теселирования плоскости, но только с плитками, которые имеют соответствующие цвета на смежных краях. Проблема определения того, образует ли набор плиток Ванга действительную тесселяцию, остается нерешенной, и ее нерешительность основана на поиске наборов плиток Ванга, которые могут только апериодически тесселировать плоскость таким образом, чтобы никакой перевод плоскости не был симметрией плитки. Первый набор апериодных плиток Ван, найденный Робертом Бергером, содержал более 20 000 различных плиток. Кари сократил размер этого набора до 14, найдя набор плиток, которые (когда используются для плитки самолета) имитируют построение последовательности Битти машинами Мели. Позже было показано, что тот же подход приводит к апериодным наборам из 13 плиток, минимально известным. Кари также показал, что проблема перемещения Ванга остается нерешимой в гиперболической плоскости, и обнаружил множества плиток Ванга с дополнительными математическими свойствами. Кари также использовал проблему вангских плиток в качестве основы доказательств того, что несколько алгоритмических проблем в теории клеточных автоматов являются нерешительными. В частности, в своем исследовании диссертации он показал, что невозможно определить, является ли обратимым данное правило клеточного автомата в двух или более измерениях. Известно, что для одномерных клеточных автоматов обратимость является решаемой, и Кари предоставил жесткие границы по размеру окрестностей, необходимых для моделирования обратной динамики обратимых одномерных автоматов.