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

Двоичное слово b₁b₂ … b_n согласовано со свободной интерпретацией базиса B, если для любого i, 1 i n, I(p) (‘f ⁱa’) = b_i, где p - единственный предикатный символ базиса B.

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

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

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

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

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

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

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

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