Issn 2072-0297 Молодой учёный Международный научный журнал Выходит еженедельно №3 (137) / 2017 р е д а к ц и о н н а я к о л л е г и я : Главный редактор



Pdf көрінісі
бет9/129
Дата23.11.2022
өлшемі9,13 Mb.
#159594
1   ...   5   6   7   8   9   10   11   12   ...   129
Байланысты:
moluch 137 ch1

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
иначе













=








Система 


Достарыңызбен бөлісу:
1   ...   5   6   7   8   9   10   11   12   ...   129




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет