Построение схемы, моделирующей автомат

Двоичное слово b1b2 … bn согласовано со свободной интерпретацией базиса B, если для любого i, 1 i n, I(p) (‘f ia’) = bi, где p - единственный предикатный символ базиса B.

Пример 1.3. Слово 101010100 согласовано с любой свободной интерпретацией I такой, что для всех i 9I(p) (‘f ia’) = 1 если i нечетно и меньше 9, и I(p)(‘f ia’) = 0, если i четно или равно 9. Свободная интерпретация I такая, что для всех iI(p) (‘f ia’) = 0, согласована с любым словом, не содержащим 1.

Для того чтобы свести проблему пустоты ДДКА к проблеме пустоты стандартных схем покажем, что для любого двоичного автомата А можно построить схему S, которая моделирует автомат А в следующем смысле. Если на ленту автомата А подано произвольное двоичное слово а, то программа(S, I), где I — любая свободная интерпретация базиса В, согласованная с а, останавливается в том и только в том случае, когда автомат допускает слово а.

Лемма. ДДКА пуст в том и только в том случае, если пуста моделирующая его стандартная схема.

Лемма. Для любого ДДКА можно построить моделирующую его стандартную схему.

Теорема (Лакхэм - Парк - Патерсон). Проблема пустоты стандартных схем не является частично разрешимой.

Теорема (Лакхэм - Парк - Патерсон, Летичевский). Проблема функциональной эквивалентности стандартных схем не является частично разрешимой.

Теорема (Лакхэм - Парк - Патерсон). Проблема тотальности стандартных схем частично разрешима.

Теорема (Патерсон). Проблема свободы стандартных схем не является частично разрешимой.








Дата добавления: 2015-07-18; просмотров: 713;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.003 сек.