Примитивно-рекурсивные предикаты

Наряду с примитивно-рекурсивными функциями в рассмотрение вводятся примитивно-рекурсивные предикаты.

Предикаты в математической логике вводятся там, где необходимо символически отобразить соотношение между несколькими предметами. В общем случае предикат определен на некотором множестве предметов и может принимать два значения: истинно или ложно (1 или 0).

Мы будем рассматривать арифметические предикаты, определенные на множестве натуральных чисел {0} = {0, 1, 2,... }.

Определение. Пусть Р( ) — n-местный предикат (зависит от nпеременных) на множестве натуральных чисел . Функция называется характеристической функцией для предиката Р, если эта функция удовлетворяет условию

Таким образом, характеристическая функция, или еще ее называют представляющей функцией предиката P( ), ( ), обращается в нуль лишь для тех и только для тех , для которых Р( ) истинно. Тогда истинность Р( ) соответствует равенству ( ) = 0.

Очевидно, что один и тот же предикат может иметь несколько характеристических функций, нули которых должны совпадать.

Определение. Предикат называется примитивно-рекурсивным, если существует примитивно-рекурсивная функция, представляющая этот предикат, т. е. его характеристическая функция примитивно-рекурсивна.

Если предикаты примитивно-рекурсивны, то и любой предикат, полученный из них с помощью логических операций, примитивно-рекурсивен. Операции исчисления высказываний (отрицание, конъюнкция, дизъюнкция, импликация) сохраняют примитивную рекурсивность предикатов.

Определение. Предикат Р( ) разрешим, если характеристическая функция ( вычислима; предикат Р( )неразрешим, если функция ( невычислима.

4.11. Нормальный алгоритм Маркова: основные понятия

Наряду с рекурсивными функциями нормальный алгоритм Маркова получил известность в качестве одного из уточнений общего интуитивного представления об алгоритме. Исходными данными и возможными результатами применения нормального алгоритма являются конструктивные объекты, достаточно общего типа — слова, и это обстоятельство определяет его роль как алгоритма в алфавите в математике.

Определение. Алфавитом называется любая конечная система различных символов.

Определение. Буквами называются символы, составляющие алфавит.

Определение. Словом в алфавите называется любая конечная последовательность букв в этом алфавите.

Определение. Пустым словом называется слово, не содержащее ни одной буквы и обозначаемое символом ∧.

Примеры.

1){а, ъ, ?, 7, *} — алфавит; а, ъ, ?, 7, * — буквы.

2) {а, b, с} — алфавит; ас, a, abbca_y bbbbb, bbacab — слова этого алфавита.

3) Алфавит исчисления высказываний состоит из букв А, В, Q, R, Р и других, возможно с индексами, логических связок — ∧, ∨, →, а также вспомогательных символов (, ).

Основная операция на словах — операция приписывания слова к слову: если дано слово, имеющее вид , и слово вида , то можно образовать новое слово , полученное приписыванием или соединением слов.

Если ∧ — пустое слово, а a — слово, то ∧ а = а∧ = а.

Определение. Два конкретных слова и и в алфавите А равны, т. е. , если n= т и . Все пустые слова считаются равными.

Определение. Если — слово, состоящее из nбукв, где , то nназывается длиной этого слова. Длиной пустого слова будет число 0.

Определение. Ассоциативным исчислением называется совокупность всех слов в данном алфавите А вместе с конечной системой допустимых подставок, т. е. чтобы задать ассоциативное исчисление достаточно задать алфавит и систему подстановок.

Опишем процесс преобразования слов, позволяющий из заданного слова получить новые слова. Зададим в некотором алфавите А конечную систему допустимых подстановок, т. е. пар слов в этом алфавите: Р — Q; L-M; ..., S- Т.

Любую подстановку L — М можно применять к некоторому слову R этого алфавита следующим способом: если в слове R имеется одно или несколько включений слова L, то любое из этих включений может быть заменено словом М и наоборот, если имеется включение слова М, то его можно заменить словом L.

К полученным с помощью допустимых подставок словам можно снова применить допустимые подстановки: так будут получены новые слова.

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

Определение. Последовательность слов называется дедуктивной цепочкой, ведущей от слова Р к слову Q, если каждые из двух рядом стоящих слов этой цепочки являются смежными.

Определение. Два слова Р и Q называются эквивалентными, если существует дедуктивная цепочка, ведущая от слова Р к слову Q. Отношение эквивалентности обозначается Р ↔ Q. Очевидно, что если Р ↔ Q, то, поскольку допустимые подстановки можно применять в обе стороны, Q ↔ Р.

Иногда рассматривается специальный вид ассоциативного исчисления, которое задается алфавитом и системой ориентированных подстановок вида Р → Q. Это означает, что подстановку разрешается проводить лишь слева направо, т. е. заменять вхождение слова Р на слово Q, но не наоборот.

Ясно, что в таком ассоциативном исчислении из эквивалентности Р ↔ Q не следует, что Q ↔ Р.

⇐ Предыдущая 1 2 3 4 567 8 Следующая ⇒