ВУЗ:
Составители:
Рис. 1.3.
Таким образом, мы показали, что для любой полутуэвской системы
можно построить нормальную систему, в классах эквивалентности которой
содержатся все формулы исходной полутуэвской системы. Легко показать,
что можно установить соответствие между полутуэвской и туэвской,
нормальной и постовской, а следовательно, между туэвской и постовской
системами. Поэтому результаты, полученные в
какой-либо одной системе,
можно распространять на любую другую комбинаторную систему.
Легко понять, что множество всех ***** слов в комбинаторной системе
порождает ассоциативное исчисление в некотором алфавите А, а ее
подстановки задают алфавитный оператор y, отображающий слова из
множества А* в слова из А*. Алфавитный оператор еще не является
алгоритмом, поскольку
в ассоциативном исчислении не определен порядок
применения подстановок. Существует несколько способов задания
однозначного порядка их применения: нормальные алгоритмы Маркова,
вычислимые функции и машины Тьюринга.
1.4. Нормальные алгоритмы Маркова
Пусть задана полутуэвская система с алфавитом
},,{ свaА = и системой
подстановок:
аcв → ; вав → ; ссасва → ; ваасса → ; сваваа → . Порядок их
применения следующий. Исходя из произвольного слова Р, система
подстановок, просматривается в естественном порядке. Отыскивается первая
подстановка, левая часть которой входит в Р. Если таковой не известен, то
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
1
1
1
2
2
2
3
3
3
4
4
4
5
5
5
6
6
6
7
7
8
8
9
9
10
10 11
12
13
14
15
асв
аасвв ааасввв
и так далее
Страницы
- « первая
- ‹ предыдущая
- …
- 19
- 20
- 21
- 22
- 23
- …
- следующая ›
- последняя »
