Информационные системы и технологии УДК 519.1: 681.3 В.Е.ХАЧАТРЯН, Я.Г.ВЕЛИКАЯ, А.И.СУНЦОВА СТРУКТУРНЫЕ ПРЕОБРАЗОВАНИЯ МОДЕЛИ ВЫЧИСЛЕНИЙ Для распознавания эквивалентности некоторых моделей вычислений применим трансформационный метод. <...> Последний использует графическое представление модели, для которой строится древовидное покрытие. <...> В тех случаях, когда трансформационный метод позволяет доказать разрешимость проблемы эквивалентности, древовидное покрытие строится однозначно. <...> В общем случае построение такого покрытия осуществляется неоднозначно. <...> В работе предлагается такое преобразование модели, после которого измененная модель, оставаясь в классе эквивалентности, обладает единственным покрытием. <...> For recognition of equivalence of some models of calculations it is applicable a transformation method. <...> Last uses graphic representation of model for which the treelike covering is under construction. <...> When the transformation method allows to prove resolvability of a problem of equivalence a treelike covering is under construction unequivocally. <...> In work such transformation of model after which the changed model, remaining in an equivalence class is offered, possesses a unique covering. <...> Под моделью вычислений в широком смысле понимают множество конструктивных объектов с приписанной ему универсальной процедурой, посредством которой каждому объекту сопоставляется порожденное ему множество. <...> Одной из фундаментальных проблем моделей вычислений является проблема эквивалентности – нахождение алгоритма, который по любой паре объектов модели определяет, обладают они одинаковыми порождаемыми множествами или нет. <...> В работах [1,2,3,4,5] рассматривается трансформационный метод распознавания эквивалентности, который для некоторых моделей вычислений, в частности, для многоленточных автоматов с непересекающимися циклами [2], задает для проблемы эквивалентности разрешающий алгоритм. <...> Рассмотрим использование трансформационного метода для двухленточных бинарных автоматов. <...> Двухленточный бинарный автомат будем представлять в виде диаграммы переходов, которая представляет собой конечный ориентированный граф с размеченными <...>