Cтраница 1
Системы Поста, все продукции которых имеют вид - S S образуют модели грамматик и языков. [1]
Решение системы Поста - конечная последовательность номеров, где одно и то же слово получается пригонкой начал соответствующих пар, с одной стороны, и пригонкой концов этих же пар, с другой стороны. Последовательность ( 2, 1, 2) - решение системы из примера. [2]
Более полное обсуждение системы Поста читатель найдет в превосходно написанных главах книги Минского [1967], посвященных этой теме. [3]
Как мы видели, системы Поста дают описание понят эффективно порождаемого множества. [4]
Каноническое исчисление Поста, или система Поста, состоит из алфавита, списка переменных и конечного множества правил вывода. Применение правила получается из правила путем подстановки слов вместо всех переменных, причем вместо одной и той же переменной всюду подставляется одно и то же слово. Это понятие позволяет конкретизировать смысл образцов, аксиом и правил следующим образом. [5]
Другой способ вывести понятие вычислимости из систем Поста состоит в непосредственном моделировании вычислений машины. Это можно сделать, используя множества продукций Q, такие, что к любой данной цепочке применима самое большее одна продукция из Q. Однородная система действует последовательно подобно машине. [6]
Если k нечетное, то породить систему Поста. [7]
Добавляя, например, функцию ж, легко получить систему Поста. [8]
Алгоритмы Поста сводятся к алгоритмам, реализуемым с помощью частично рекурсивных функций, и наоборот - любая частично рекурсивная функция может быть представлена алгоритмом системы Поста. [9]
На рис. 1 представлена упрощенная блок-схема функционирования системы промышленного экологического мониторинга. На первом этапе система постов загазованности измеряет концентрацию вредных веществ в атмосферном воздухе в точках их размещения. [10]
До настоящего времени этот метод определения языка исследован недостаточно глубоко. В работе Минского обсуждаются системы Поста ( Post), Шмульян ( Smullyan) дает изложение формальных математических свойств подобных систем. [11]
Множество реализуемых предикатных формул непе-речислимо, поэтому конструктивное исчисление предикатов неполно относительно реализуемости, а из его полноты относительно наивной конструктивной семантики следовала бы интуиционистская истинность принципа конструктивного подбора. Конструктивное исчисление высказываний также неполно относительно реализуемости, но полно при нек-рой интерпретации в терминах систем Поста. Для гей-гинговских систем установлены теоремы полноты относительно теоретико-модельных семантик Крипке и Бета, использующих возможные миры ( эти семантики связаны с теоретико-множественным вынужденном), а также относительно алгебраических и топологических моделей. [12]
Формальная система является неинтерпретируемым исчислением, или логистической системой, и состоит из алфавита, множества слов, называемых аксиомами и конечного набора отношений, называемых правилами вывода. Примерами формальных систем являются: теория множеств, булева алгебра, исчисление высказываний и предикатов, системы Поста, евклидова геометрия на плоскости, бэкусовская нормальная форма и арифметика Пиано. Формальная система не интерпретируема в том смысле, что символам системы формально не придается никакого значения; для каждой из упомянутых выше систем имеется стандартная неформальная интерпретация символов, однако и другие интерпретации, вообще говоря, допустимы в той мере, в какой это касается самой системы как таковой. [13]
Алгоритмы, составленные из любого конечного члсла правил, представленных приказами машины Поста; называются алгоритмами Поста. Доказано, что алгоритмы Поста сводятся к алгоритмам, реализуемым с помощью частично рекурсивных функций, и наоборот, любая частично рекурсивная функция может быть представлена алгоритмом системы Поста. [14]
ОДНИМ ИЗ центральных понятий этой книги является понятие формальной системы. Формальные системы того типа, который я использую, были изобретены американским логиком Эмилем Постом в 1920 - х годах; их часто называют системами продукции или системами Поста. [15]