Конспект установочных лекций по комплексному курсу Информатика, Теория информации



Модуль Общая характеристика последовательных - часть 7


Теорема 3. Не существует такого автомата Неймана-Черча, в котором можно было бы микроструктурно моделировать вычислительную среду. (Доказательство опираеться на тот факт, что элементы вычислительной среды теоретически могут не иметь задержки пр передаче информации, а в автоматах Неймана-Черча задержка обязательно присутствует).

Теорема 4. В двухмерной вычислительной среде при отсутствии ограничения на число элементов микроструктурно моделируется k-мерная вычислительная среда, где k – конечное число. (Доказательство проводится методом построения k-мерного элемента вычислительной среды в двумерной вычислительной среде).

Из приведенных теорем следует, что вычислительная среда имеет качественное отличие от автоматов Неймана-Черча.

Свойства элементов вычислительной среды – отсутствие запаздывания при передаче информации и возможность изменения коммутации и между полюсами элементов – позволяют микроструктурно моделировать в вычислительной среде алгоритм Колмогорова-Успенского и растущий автомат. Как известно, при выполнении алгоритма Колмогорова-Успенского активная часть U(S) состояния S, представляющая собой комплекс комплекса S, состоящий из вершин и отрезков, принадлежащих цепям длины j равно или меньше N, содержащим начальную вершину (N – произвольное, но для данного алгоритма фиксированное число). Отсюда видно, что при реализации алгоритма Колмогорова-Успенского необходима мгновенная передача информации через большое число элементов.

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

Теорема 5. В вычислительной среде микроструктурно моделируется алгоритм Колмогорова-Успенского.

Теорема 6. В вычислительной среде микроструктурно моделируется растущий автомат. (Доказательство этих двух теорем может быть получено построением соответствующих структур в вычислительной среде).




Содержание  Назад  Вперед