Математическая логика и теория алгоритмов. Галуев Г.А. - 44 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 44 из 64
© 2003 Галуев Геннадий Анатольевич
значать знаком ≈. Легко видеть, что для любых слов X и Y из А≈В следует
XAY≈XBY.
А. Туэ ещё в 1914 году сформулировал следующую проблему, известную под
названием ''проблемы тождества для полугрупп'', которая (для 5конечной опреде-
ленной полугруппы, допускающей простую и естественную конструктивизацию в виде
понятия ассоциативного исчисления) трансформируется в ''проблему эквивалентно-
сти'': для любой пары слов в некотором алфавите установить, являются они эквива-
лентными или нет. Рассмотрим более подробно этот вопрос. Введем ряд определений.
О
О
п
п
р
р
е
е
д
д
е
е
л
л
е
е
н
н
и
и
е
е
.
. Слово
1−
A называется обращением (инверсией) слова А, если оно
образовано в точности из тех же вхождений, что и А, но взятых в обратном порядке.
Слово А называется симметричным, если оно совпадает со своей инверсией.
Рассмотрим некоторое ассоциативное исчисление в алфавите А={a,b}, опреде-
ляемое соотношениями aa~E, bb~E. Сократить слово А в этом исчислении, значит об-
разовать новое слово В, смежное с А (то есть В получаем из А однократным примене-
нием соотношения ТУЭ), которое короче А. Взяв некоторое слово за исходное, мы
можем путем последовательных сокращений, образовать ряд слов, который приведет
к несократимому слову(возможно пустому).
Например: Пусть A=aabbaaabbbabbb, B=abab, C=aaabbabbbaab. Покажем один из
вариантов сокращения слова А
:
aa~E bb~E
Тогда ⎣aa⎦bbaaabbbabbb≈⎣bb⎦aaabbb a bbb≈⎣aa⎦abbbabbb≈a⎣bb⎦babbb≈aba⎣bb⎦b≈abab. В
результате получаем, что А эквивалентно В, а В является несократимым в этом ис-
числении. Для слова С существует несколько вариантов сокращения, один из кото-
рых имеет вид
⎣aa⎦abbabbbaab≈abbabbbaab≈aa⎣bb⎦baab≈⎣bb⎦
baab≈b⎣aa⎦b≈⎣bb⎦≈0=E. Поэтому C≈E.
Легко проверить, что результат не зависит от того, в каком порядке выполняются
сокращения. В каждом классе эквивалентности существует ровно одно несократимое
слово, которое называется каноническим представителем этого класса.
Для данного ассоциативного исчисления проблема эквивалентности разрешима, так
как любые два слова эквивалентны тогда и только тогда, когда они обладают одним и
тем же каноническим представителем, который легко найти путем реализации проце-
дуры последовательных сокращений.
Однако существуют примеры ассоциативных исчислений, для которых проблема эк-
вивалентности неразрешима.
Например, A={a,b} aaa~aa, aba~aa, bab~bb, bbb~bb.
Из слова ababa можно
получить ⎣aba⎦ba≈a⎣aba⎦≈⎣aaa⎦≈aa или a⎣bab⎦a≈abba.
Слова aa и abba несократимы, эквивалентны, но различны.
Первые примеры ассоциативных исчислений, для которых проблема эквивалент-
ности неразрешима, были получены А. А. Марковым и Э. Л. Постом в 1947 году. В
связи с этим возникает вопрос: существует ли универсальный метод, позволяющий
решать
проблему эквивалентности. Путем введения уточненного понятия алгоритма –
нормального алгоритма Марков А. А. Показал, что в общем случае эта проблема не-
разрешима. Об этом мы будем говорить позже.
Комбинаторные системы.
Комбинаторные системы это частный случай формальных (алгоритмических)
систем. Они используются для исследования задач комбинаторного характера, свя-
занных с преобразованием слов.
Для определения комбинаторной системы необходимо задать:
1. Конечный алфавит А, называемый основным, и , возможно, вспомогательный
алфавит В. Из А
U В образуется множество
*
A слов (формул);
2. Выделенное непустое слово S(аксиому) S
∈
A U B.

Страницы