Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Проблема эквивалентности слов для ассоциативных исчислений.↑ ⇐ ПредыдущаяСтр 4 из 4 Содержание книги
Поиск на нашем сайте
Первые результаты об алгоритмической неразрешимости были установлены для проблем, возникающих в самой математической логике и в теории алгоритмов. Сюда относятся и рассмотренные проблемы «Проблема выводимости» и «Проблема самоприменимости». Но позже выяснилось, что аналогичные проблемы возникают в самых различных специальных разделах математики. Сюда относятся, в первую очередь, алгебраические проблемы, приводящие к различным вариантам проблемы слов. Рассмотрим некоторый алфавит А = {а,b,с,...} и множество слов в этом алфавите. Если слово L является частью слова М, то говорят, что слово L входит в слово М. Так, слово аса входит в слово bсаcаb, начиная с буквы а. Будем рассматривать преобразование одних слов в другие с помощью некоторых допустимых подстановок вида P — Q или P ®Q, где Р и Q два слова в том же алфавите А. Применение ориентированной подстановки Р ® Q к слову R возможно в том случае, когда в нем имеется хотя бы одно вхождение левой части Р; оно заключается в замене любого одного такого вхождения соответствую щей правой частью Q. Применение неориентированной подстановки Р — Q допускает как замену вхождения левой части правой, так и замену вхождения правой части левой. Будем рассматривать, в основном, неориентированные подстановки. Пример. Подстановка ас - аса применима к слову bсасаb двумя способами; замена вхождения аса в это слово дает слово bcacab, а замена вхождения ас дает слово bсасааb, К слову аbсаb эта подстановка не применима. Определение. Ассоциативным исчислением называется совокупность всех слов в некотором алфавите вместе с какой-нибудь конечной системой допустимых подстановок. Дли задания ассоциативного исчисления достаточно указать соответствующие алфавит и систему подстановок. Если слово R может быть преобразовано в слово S посредством однократного применения допустимой подстановки, той S может быть преобразовано в R таким же путем. В таком случае R и S называют смежными словами. Последовательность слов таких, что каждая пара слов и (i = l,2,...,n-l) являются смежными, называют дедуктивной цепочкой, ведущей от слова R к слову S. Если существует дедуктивная цепочка, ведущая от слова R к слову S, то, очевидно, существует и дедуктивная цепочка, ведущая от слова S к слову Д, в этом случае слова R и S называют эквивалентными и обозначают: R ~ S. Для каждого ассоциативного исчисления возникает своя специальная проблема эквивалентности слов: Для любых двух слов в данном исчислении требуется узнать, эквивалентны они или нет. Проблема эквивалентности слов для ассоциативных исчислений была сформулирована в 1911 году. Тогда же был предложен алгоритм для распознания эквивалентности слов в некоторых ассоциативных исчислениях специального вида. Естественно возникла задача об отыскании такого общего алгоритма, который был бы применим к любому ассоциативному исчислению. В 1946 и 1947 годах российский математик А. А. Марков и американский математик Э. Пост, независимо один от другого, построили конкретные примеры ассоциативных исчислений, для каждого из которых проблема эквивалентности слов алгоритмически не разрешима, и, следовательно, не существует алгоритма для распознания эквивалентности слов в любом исчислении. В1955 году российский математик П. С. Новиков доказал алгоритмическую неразрешимость проблемы тождества групп, формально эта проблема представляет собой частный случай проблемы эквивалентности слов в ассоциативном исчислении. Примеры, построенные А. А. Марковым и П. С. Новиковым для опровержения алгоритмической разрешимости исследуемых проблем были громоздкими и насчитывали сотни допустимых подстановок. Петербургскому математику Г. С. Цейтину удалось построить пример алгоритмически неразрешимого исчисления, в котором используется лишь семь допустимых подстановок.
|
||||
Последнее изменение этой страницы: 2016-12-13; просмотров: 241; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.116.24.238 (0.005 с.) |