Автоматы «без входа», проблема полноты и выразимости для них. - презентация

1 Автоматы «без входа», проблема полноты и выразимости для них.

2 2

3 Нетрудно убедиться, что I является оператором замыкания на множестве B(M), образованном всеми подмножествами множества M. 3

4 Для двух множеств M 1 и M 2 решение задачи выразимости с оператором замыкания I состоит в проверке включения: I(M 1 ) I(M 2 ). 4

5 5

6 6

7 7

8 8

9 Предложение 1.2. Если универтсальная алгебра M является конечно порождённой, то Σ π (M) образует k-систему. Отметим, что в общем случае это утверждение не является обратимым. 9

10 Универтсальная алгебра М – функциональная система Унарные операции: (ηf)(x 1, x 2,...,x n ) = f(x 2, x 3,...,x n, x 1 ), (τf)(x 1, x 2,...,x n ) = f(x 2, x 1, x 3,...,x n ), (f)(x 1, x 2,...,x n ) = f(x 1, x 1, x 2,...,x n1 ), если n > 1, (ηf)=(τf) = (f) = f, если n = 1, ( f)(x 1, x 2,...,x n, x n+1 ) = f(x 2, x 3,...,x n+1 ). 10

11 Описанные операции называются соответственно сдвигом, транспозицией, отождествлением, расширением и подстановкой, а в совокупности операциями суперпозиции. 11

12 Множество этих операций обозначим через с. Пусть M P E и I с (M) = M, тогда функциональная система M = (M, с ) называется итеративной функциональной системой Поста. 12

13 Бесконечность полных относительно суперпозиции систем автоматов. 13

14 Условия полноты для автоматных функций Автоматные функции f и g τ - эквивалентны, если они совпадают на всех входных словах длины τ (обозначение: f τ g), и A-эквивалентны, если f τ g для любого τ из N. 14

15 На множестве B(P a,l ) введём отношение τ, полагая, что для M, M P * a,l выполнено M τ M, если для всякой функции f из M найдётся g из M, такое что f τ g. 15

16 На B(P a,l ) введём ещё одно отношение, полагая, что для M,M P a,l выполнено M A M, если для всякого τ из N справедливо M τ M. Теорема 1. Для любых M P a,l и τ N справедливо: J ртс (M) τ J ртс,О (M), J ртс (M) A J ртс,О (M). 16

17 Теорема 2. Для эффективно задаваемых конечных множеств M,M P a,l отношение M τ J ртс (M) алгоритмически разрешимо для любого τ из N. 17

18 Теорема 3. Для конечных множеств M,M P a,l,k отношение M A J ртс (M) алгоритмически неразрешимо. Пусть M P a,l и M A J ртс (M). Назовём множество M M τ –полным в M, если J ртс (M) τ M, и A-полным, если J ртс (M) A M. 18

19 Теорема 4. Если M P a,l, M A J ртс (M), M разрешимо, в M есть конечное A-полное подмножество и τ N, то существует алгоритм, устанавливающий по любому конечному разрешимому подмножеству M M, является ли оно τ -полным в M. 19

20 Теорема 5. Условия τ -полноты и A-полноты совпадают для всех основных итеративных функциональных систем автоматных функций. Следующее утверждение отмечает существенное отличие понятий τ -полноты и A-полноты. 20

21 Теорема 6. В каждой из основных итеративных функциональных систем автоматных функций существуют конечные A-полные системы, а также счётные A-полные системы, не содержащие конечных A-полных подсистем. Следующее утверждение отмечает отличие понятий τ -полноты и A-полноты. 21

22 Теорема 7. Если M P a,l,k и множество M конечно, то не существует алгоритма, устанавливающего по M, является ли оно A-полным в P a,l,k. В то же время имеется определённое сходство понятий τ - и A-полноты, и оно проявляется прежде всего в подходе к решению задач о τ - и A-полноте в терминах предполных классов. 22

23 23

24 24

25 25 Это утверждение с учётом теорем 5 и 8 сводит решение задач о τ - и A-полноте в основных итеративных функциональных системах автоматных функций к описанию множества Σ π,τ (P a,l ).

26 26 Полугруппа автомата, связь операций над автоматами с операциями над их полугруппами

27 27 Если выход автомата A 1 = (A 1, Q 1, B, ϕ 1, ψ 1 ) соединить с входом автомата A 2 = (B, Q 2, C, ϕ 2, ψ 2 ), то полугруппа полученного автомата- суперпозиции является подполугруппой сплетения полугруппы автомата A 1 и полугруппы автомата A 2.

28 28 Зафиксируем конечный алфавит A = (a 1... a m ) и рассмотрим множество PA всех автоматных отображений множества A всех слов в алфавите A в себя. Каждое такое отображение реализуется некоторым конечным инициальным автоматом A = (A, Q, A, ϕ, ψ, q 0 ).

29 29 Автомат A реализует суперпозицию F функций F1 и F2: F(x) = F2(F1(x)).

30 30 Полнота относительно суперпозиции множества автоматных функций двух переменных опирается на: а) для любого n симметрическая группа Sn имеет 2 образующих (и потому реализуется автоматом с 1 бинарным входом),

31 31 б)если автоматная функция реализуется автоматом с внутренней группой, то имеется входное слово, равное единице в этой группе, которое попарно отличает все состояния автомата.

32 32 Список использованных источников 1. Кудрявцев В.Б., Алгебры автоматов. Фундаментальная и прикладная математика/Московский государтственный универтситет им. М.В. Ломоносова. – Изд. «Открытые системы», 2009, том 15, 4 с Ожиганов А.А., Теория автоматов. Учебное пособие. – СПб: НИУ ИТМО, – 84 с.