Проблема слов в ассоциативном исчислении

 

Проблема слов в ассоциативном исчислении заключается в следую­щем: для любых двух слов в данном исчислении требуется узнать, экви­валентны они или нет.

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

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

Однако успешное решение ограниченной проблемы слов не прибли­жает нас к решению основной, «неограниченной» проблемы. Посколь­ку длина дедуктивной цепочки, ведущей от слова Р к слову Q, может оказаться сколь угодно большой, то неизвестно, когда следует считать законченным процесс переработки.

Возникает проблема: для произвольного ассоциативного исчисления требуется построить алгоритм, который для любой пары слов в алфавите этого исчисления позволял бы за конечное число шагов выяснить, экви­валентны ли в данном исчислении слова, составляющие эту пару, т. е. построить алгоритм в некотором алфавите А.

 

 

Алгоритм в некотором алфавите А

 

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

Уточнение понятия алгоритма в алфавите А связано с использованием аппарата подстановок, т. е. с построением ассоциативного исчисления.

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

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

 

 

Понятие нормального алгоритма

 

А. А. Марковым было дано точное математическое определение нор­мального алгоритма.

Задается алфавит А и фиксируется схема подстановок. Алгоритм предписывает, исходя из произвольного слова Р в алфавите А, просмо­треть формулы подстановок в том порядке, в каком они заданы в схеме, разыскивая формулу с левой частью, входящей в Р. Если такой формулы не найдется, то процесс обрывается. В противном случае берется первая из таких формул и делается подстановка ее правой части вместо первого вхождения ее левой части в Р, что дает новое слово в алфавите А. После выполнения первого шага приступают ко второму шагу, отличающемуся от первого только тем, что роль Р играет . Далее делают аналогичный третий шаг и т. д. до тех пор, пока не придется оборвать процесс. Оборвать­ся же он может лишь двумя способами: во-первых, когда мы получим такое слово Р_п, что ни одна из левых частей формул схемы подстановок не будет в него входить; во-вторых, когда при получении слова Р_п нам придется применить последнюю формулу. В обоих случаях мы считаем, что наш алгоритм перерабатывает слово Р в слово Р_п.

Различные нормальные алгоритмы отличаются друг от друга лишь алфавитами и системами допустимых подстановок. Чтобы задать какой-либо нормальный алгоритм достаточно задать алфавит и систему подста­новок.

Понятие алгоритма в некотором алфавите было уточнено Марковым следующим образом: всякий алгоритм в алфавите А эквивалентен нор­мальному алгоритму в этом же алфавите.

 

 

ПРИМЕРЫ РЕШЕНИЯ ТИПОВЫХ ЗАДАЧ.

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

⇐ Предыдущая12345678Следующая ⇒

Поделиться:

Популярное:

1. Authority problem. Проблема авторитета.
2. I. С учетом условия развития, особенности инфицирования и состояния иммунитета
3. II. Выберите, при каком условии верно данное утверждение.
4. III. Мягкосердечие Пророка, да благословит его Аллах и приветствует, и его плач.
5. III. По способу работы со своими проблемами среди клиентов можно выделить следующие типы
6. V . СЛОВАРЬ ВИКТИМОЛОГИЧЕСКИХ ТЕРМИНОВ
7. VIII.,ИЗМЕНЕНИЕ УСЛОВИЙ КОНТРАКТА
8. Адаптация структурной схемы к условиям, обеспечивающим достоверную симуляцию рабочих процессов
9. Адресация слов в последовательности.
10. Акт об обеспечении свободы парламентов путем дальнейшего установления условий членства для заседания в палате общин, 1710 г.
11. Аромапомощь при детских проблемах
12. Б1.Б.4 «Физическая культура. Здоровьесбережение в условиях Крайнего Севера»