x
∈ω
дает набор
чисел
( )
1
, ,
x
x
n x
t
t
…
и
( )
n x
-местную булеву функцию
x
β
, зависящие от х такие, что
( )
( )
( )
(
)
1
, ,
1
x
x
x
n x
x A
B t
B t
∈ ⇔β
…
=
Сводимости, промежуточные по силе между m-сводимостью и tt-сводимостью, называются табличными или
сходимостями табличного типа. Имеется естественный путь получения таких сводимостей. Для этого надо
зафиксировать замкнутый класс булевых функций и в определении tt-сводимости добавить слова функция из такого-то
класса. Оказалось, что основных табличных сводимостей существует всего лишь семь: кроме m- и tt-, еще линейная,
конъюнктивная, дизъюнктивная, позитивная и табличная с нормой 1 [4,11]. Поскольку класс
{
}
1
, , , , ,
,
tt p c d l btt m
оказался четко очерчен, удалось поставить и решить вопросы о различии элементарных теорий, классов вычислимо
перечислимых полных множеств [1,2].
Сводимости по перечислимости отличаются от сводимостей по разрешимости тем, что информацию про множество
А рано или поздно можно будет получить, но про
А
не обязательно. Говорят, что множество А е-сводится к В, если
существует е-оператор Ф такой, что А=Ф(В). При этом е-оператор Ф переводит множество Х в
( )
( )
(
)
{
}
¦
:
,
&
y
Х
x
y x y W
D
X
=
∃
∈
⊆
[2, 3, 5]
Сводимости, промежуточные по силе между е- и m-, образуют класс сводимостей по перечислимости. Основными
сводимостями по перечислимости являются
{
}
, , , , , ,
,
e s p c pc d pm m
. В связи с тем, что вычислимо перечислимые
множества образуют наименьшую e-степень, вопрос о полных множествах не стоит, зато с элементарными теориями
удалось разобраться — они все попарно различаются [6–10].
Как уже отмечено, если
e
A
B
≤
и имеется способ перечислять B, то по нему можно получить и эффективное
перечисление А. Это позволяет, например, по множеству свойств В моделирующей системы перечислять свойства из
А моделируемой системы, если для множеств этих свойств установлено е-сведение. Но если на самом деле
a A
∉
, то
перечисляя А, мы просто не получим элемент
a
, и вообще ни в какой момент времени нет оснований полагать, что
a A
∉
. Этим отличаются сводимости по перечислимости.
Приведем пример.
Рассмотрим модель
рюкзак
. У нее входом
X
является пятерка
, , , ,
R s v B K
. Здесь
R
— некоторое конечное
множество,
,
s v
— функции, отображающие
R
в положительные целые числа
Z
+
, выход
{ }
0,1
Y
=
. Система
функционирует посредством функции
(
)
( )
( )
'
1,
'
&
&
, , , ,
0,
x R
x R
K
если R R
R
s x
B
v x
K
f R s v B K
иначе
∈
∈
′
∃
⊆
≤
≥
=
′
∑
∑
Система
Достарыңызбен бөлісу: |