Cтраница 3
Итак, ограничение каноническими исчислениями не приводит к сужению понятия К-системы. [31]
Из доказанной теоремы следует, что принятое определение истинности в К-системе действительно обеспечило выход за пределы финитных формальных систем. Поскольку класс рекурсивно перечислимых множеств не замкнут относительно операции дополнения, финитные формальные системы образуют лишь сравнительно узкий собственный подкласс класса полных К-систем. В частности, любой алгоритм является К-функцией, но обратное неверно - К-функция в общем случае непредставима в виде алгоритма. [32]
Пусть преобразованы Х Ш) у приводит систему х Аа) х к-системе у By с постоянной матрицей В. [33]
Первое утверждение следует из того, что всякое каноническое исчисление является и К-системой. [34]
Рассмотрим, в каком смысле можно говорить об аппроксимации продукционной программы ( или К-системы) с помощью интерпретатора. [35]
Главными действующими лицамии книги являются понятие исключение из правила и основанная на немм концепция К-системы. [36]
Рассмотрим теперь, какой вид имеет отношение исключения на множестве выводов в построенном варианте К-систем. [37]
К-система полна, если Е U Е совпадает со множеством всех слов в алфавите К-системы. Напомним, что К-множество полно, если оно представимо в полной К-системе. [38]
Как уже отмечалось, И-выводы используются для вывода истинности слов: слово истинно в К-системе, если существует его И-вывод. Множество слов в данном алфавите, истинных в некоторой К-системе ( возможно и расширение алфавита), называется К-множеством. К-множество К-разре-шимо, если его дополнение до множества всех слов в данном алфавите является К-множеством. [39]
Наконец, приписывая друг к другу коды продукций, разделенные знаком, получим код всей К-системы - базис рассматриваемой К-системы. [40]
Математический анализ проблемы позволил выявить фундаментальную роль исключений из правил - оказалось, что семантика К-систем трансфинитна, а сами К-системы представляют собой нетривиальное обобщение финитных, в том числе, алгоритмических систем. [41]
Согласно определению из А ЕЕ К / 95 вытекает, что А есть - подсистема подходящей К-системы. Ввиду наследственности К это дает А ЕЕ К и потому К / 95 cr К. [42]
Поскольку различные классы финитных формальных систем эквивалентны между собой, можно без ограничения общности при построении К-систем ограничиться каким-либо конкретным представителем, например, классом канонических исчислений - они достаточны для представления выводимости в любых финитных формальных системах. [43]
Из только что доказанной теоремы как раз и следует, что при разработке практических интерпретаторов для К-систем речь может идти только об аппроксимации идеального интерпретатора. Наилучшего алгоритма интерпретатора, таким образом, не существует. [44]
Наконец, приписывая друг к другу коды продукций, разделенные знаком, получим код всей К-системы - базис рассматриваемой К-системы. [45]