Дискретно-непрерывные системы: алгоритмический аспект

Работа посвящается связи между дискретными и непрерывными системами. Обсуждается вопрос, когда непрерывная система может служить моделью дискретной. Особое внимание уделяется динамическим системам, задаваемым дифференциальными уравнениями с кусочно-постоянными правыми частями (что типично для непрерывных систем с дискретными регуляторами), – КПС. Показывается, что любую машину Тьюринга можно смоделировать при помощи КПС размерности 3. С другой стороны, в размерности 2 невозможно смоделировать функционирование некоторых конечных автоматов. Во второй части обсуждаются алгоритмические вопросы, связанные с КПС. В [6] был получен алгоритм, позволяющий полностью исследовать поведение КПС на плоскости, в частности решать для них задачу достижимости. Из приведенных в первой части статьи результатов о моделировании следует алгоритмическая неразрешимость этой задачи для трехмерных КПС.