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

“Young Scientist”
. 
#3 (137)
. 
January 2017
1
Mathematics
М А Т Е М А Т И К А
Моделирование комбинаторных систем при помощи сводимости
Дацкевич Андрей Евгеньевич, студент
Тюменский Государственный медицинский университет
Статья посвящена моделированию систем, ее реализации в компьютере, в частности с использованием 
сводимости, в то же время рассматривается теория алгоритмов и возможность ее применения к моделиро-
ванию.
Ключевые слова
: моделирование, комбинаторные системы, сводимость, учебный процесс, теория алго-
ритмов, теория систем
П
од моделированием будем понимать реализацию функционирования объекта в компьютере. При этом целью 
обычно является оценивание средних величин. Методы моделирования изначально развивались для физики, в на-
стоящее время трудно найти отрасль, где бы они не применялись. Можно также считать, что при моделировании рас-
сматривают систему А, ее модель Б, а также вопрос, может ли Б служить адекватной моделью для А. В основании пе-
рехода часто лежит умозаключение по аналогии, которое дает вероятное знание [13].
Возьмем формальный язык L, основные символы которого будут интерпретированы так, чтобы на языке L удалось 
выразить отношения, согласно которым модель замещает объект. Можно считать L языком узкого исчисления 
предикатов, логические константы которого составляют сигнатуру 
Σ
. Через 
( )
L
T A
обозначим элементарную теорию 
объекта A, т. е. множество предложений, истинных в A [1]. Вообще нас могут интересовать не все свойства даже среди 
тех, которые выразимы на языке L. Поэтому естественно говорить о подмножестве В множества предложений языка 
L, выражающих интересующие исследователя свойства. Далее уточним форму отношения моделирования между 
объектами А и Б путем использования сведения проблемы истинности предложений для Б к проблеме истинности 
предложений из А. 
В теории алгоритмов существуют различные классы сводимостей. Принципиально они отличаются по выбору одного 
или нескольких объектов для принятия решений, а также по тому факту, что информация может быть точно получена 
или может быть когда-либо получена, но в данный момент времени это неизвестно. Главное в процессе сведения — 
эффективность, или алгоритмичность. 
Например, pm-сводимость (частичная) в применении выглядит следующим образом. Мы имеем возможность делать 
утверждения о свойствах Б на основании утверждений о свойствах А как конструктивное существование языка М и 
эффективного способа F перевода предложений P из В в предложения F(P) языка М таким образом, что 
( )
( ) ( )
P B
P T Б
F P
T A
∈ ⇒  ∈
⇔
∈



Важным здесь является не только эффективность F, но и невысокая алгоритмическая сложность F. Эта 
эквивалентность вообще говоря, может выполняться не на всех высказываниях, а на некоторой части, что 
соответствует неполному соответствию модели объекту. 
Если построенная теория Т(Б) изучаемого объекта достаточно проста и допускает непосредственное изучение, тогда 
объектом А можно считать систему, для которой Т(А)=Т(Б) и тогда проблема адекватности модели — это проблема 
адекватности теории. 
Если заданы теории объектов А и Б, то существование или несуществование сводимости является математической 
проблемой, решение которой в положительном смысле обосновывает отношение моделирования объектом А объекта 
Б в плане свойств из В, обосновывает с той достоверностью, с которой заданные теории адекватны своим объектам. 
Итак, концепция заключается в рассмотрении отношения моделирования А — модель Б как частичного отношения 
вида (*) или более общего между теориями этих объектов. 
В математической логике одной из основных проблем является массовая проблема разрешимости для формальных 
теорий, т. е. проблема существования алгоритма, позволяющего по любому предложению языка определить, является ли 
оно истинным или принадлежит ли оно теории. Работы 30-х годов двадцатого века показали, что не существует 
разрешающего алгоритма для УИП, с тех пор было доказано много теорем об алгоритмической неразрешимости, причем 
большинство — путем сведения известной проблемы к рассматриваемой. Метод сводимости стал широко 
распространенным. Это и привело к изучению сводимостей как таковых. Сводимости стали мощным средством 
классификации множеств по сложности (степеням неразрешимости). Хорошим введением в эту область служит книга [3]. 
Введем необходимые формализмы. Множества и функции заданы на 
{
}
0,1,2,
ω =
…
. Всюду определенные функции 
обозначаются через f,g,h, частичные — 
α
,
β
. 
n
D
— каноническая нумерация конечных множеств, 
x
W
— стандартная 
нумерация вычислимо перечислительных множеств (области определения частичных функций, задаваемых машиной 
Тьюринга с номером х). Среди сводимостей по разрешимости выделяютс наиболее общая тьюрингова и так называемые 
табличные сводимости. Говорят, что А tt-сводится к В, если существует алгоритм, который по любому 
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
. В связи с тем, что вычислимо перечислимые 

«Молодой учёный»

жүктеу/скачать 9,13 Mb.

Достарыңызбен бөлісу: