Студопедия — Доказательство окончено. Вспомогательные символы R и Q использованы для того, чтобы продукция, получаемая из продукции одной из систем описанным в доказательстве преобразованием
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Доказательство окончено. Вспомогательные символы R и Q использованы для того, чтобы продукция, получаемая из продукции одной из систем описанным в доказательстве преобразованием






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

Если, например, при построении системы PU в качестве множества продукций для PU взять объединение множеств неизмененных продукций систем P 1 и P 2, то можно получить систему, в которой выводятся слова, не входящие в W 1 W 2.

В качестве примера рассмотрим системы P 1 и P 2 со следующими совокупностями продукций:

p1,1: 1, p1,2: ; (1)

 

p2,1: 0, p2,2: . (2)

 

Тогда с помощью продукций (1) системы P 1 можно выводить слова, составленные только из единиц, а при помощи множества (2) системы P 2 - слова, которые имеют конечное число нулей.

Однако продукции p1,1, p1,2, p2,1, p2,2, используемые совместно, позволяют выводить любые слова, состоящие из нулей и единиц.

Семейство классов слов, выводимых в системах Поста, не замкнуто относительно операции взятия дополнений таких множеств.

Это означает, что существует такая система P = (A, B, V, P), для которой множество A * \ WP не выводится ни в одной системе Поста. Доказательство этого факта будем приведено ниже после изучения связи множеств слов, выводимых в системах Поста и множества частично-рекурсивных функций.

 

Всякое множества W - таких слов в некотором основном алфавите A, что W и его дополнение до A * выводимы в некоторых системах Поста, является разрешимым.

Справедливость последнего свойства вытекает из следующей теоремы.







Дата добавления: 2015-09-18; просмотров: 273. Нарушение авторских прав; Мы поможем в написании вашей работы!



Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

Важнейшие способы обработки и анализа рядов динамики Не во всех случаях эмпирические данные рядов динамики позволяют определить тенденцию изменения явления во времени...

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Потенциометрия. Потенциометрическое определение рН растворов Потенциометрия - это электрохимический метод иссле­дования и анализа веществ, основанный на зависимости равновесного электродного потенциала Е от активности (концентрации) определяемого вещества в исследуемом рас­творе...

Гальванического элемента При контакте двух любых фаз на границе их раздела возникает двойной электрический слой (ДЭС), состоящий из равных по величине, но противоположных по знаку электрических зарядов...

Сущность, виды и функции маркетинга персонала Перснал-маркетинг является новым понятием. В мировой практике маркетинга и управления персоналом он выделился в отдельное направление лишь в начале 90-х гг.XX века...

Тема 5. Анализ количественного и качественного состава персонала Персонал является одним из важнейших факторов в организации. Его состояние и эффективное использование прямо влияет на конечные результаты хозяйственной деятельности организации.

Билет №7 (1 вопрос) Язык как средство общения и форма существования национальной культуры. Русский литературный язык как нормированная и обработанная форма общенародного языка Важнейшая функция языка - коммуникативная функция, т.е. функция общения Язык представлен в двух своих разновидностях...

Патристика и схоластика как этап в средневековой философии Основной задачей теологии является толкование Священного писания, доказательство существования Бога и формулировка догматов Церкви...

Studopedia.info - Студопедия - 2014-2024 год . (0.011 сек.) русская версия | украинская версия