Об одном случае неразрешимости проблемы эквивалентности программ

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