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