Information Technology Reference
In-Depth Information
Stafford Beer, a former president of the Operations Research Society of Amer-
ica, viewed complexity as an inherent property of our world. He pointed out:
“There exist the real world, which can be observed and measured, and a reality,
in which a dead man is a dead human being rather than an object of statistics. There
also exists a reality that we encounter every day. It is not arranged in orderly
pigeonholes and is not provided with labels for the corresponding bureaucrats who
make decisions. The essence of such reality is complexity.”
Among the many aspects of the complexity of the world around us, there are
three basic concepts that are fundamental to the concept of complexity. By defining
them, the famous American mathematician John Casti believed that:
“Static complexity describes the formation of the system from its component
subsystems, dynamic complexity is based on computing the length which is
required to describe the behavior of the system, the complexity of governance is
a measure of computational resources required for detailed calculation of the
dynamics of the system.”
Preserving the essence of these definitions, in what follows we will introduce a
somewhat different terminology more widely adopted today to describe physical,
chemical, and biological systems. We will use the terms:
Structural complexity of the system (static)
Behavioral complexity (dynamic), which determines the spatiotemporal evolu-
tion of the system which carries out information processing operations
Computational complexity of the algorithm (control complexity), which
describes the information processing operations being performed
A great contribution to the concept of complexity was made by Academician
A. N. Kolmogorov, who created the foundations for its quantitative description. His
concept of algorithmic complexity is arguably the most adequate description of the
evolution of dynamic systems.
Let there be a system that converts information at system's input
x
X
into
∈
information at its
y
Y
output according to a certain program
p
. Here
X
and
Y
are
sets of values
x
and
y
. The structure of the system is defined as a description of its
hardware characteristics, i.e., some function
φ
(
p
/
x
) ¼
∈
y
which can be used by the
program
p
. Importantly,
this description does not depend on the choice of
input data.
The algorithmic complexity of the process which takes place in the system with
structure
y
, i.e., behavioral complexity of the system, is defined as the
minimum length of the program
l
(
p
) out of many programs
S
which adequately
describe the process:
φ
(
p
/
x
)
¼
min
lp
ðÞ
:
φ
ðÞ
¼
p
=
x
y
,
K
φ
ðÞ
¼
y
=
x
1
:
8
p
S
φ
ðÞ6
¼
p
=
x
y
:
∈
Based on the definition of the system's structure, one can introduce the definition
of its structural complexity
K
(
x
/
y
), as complexity with fixed values
x
¼
x
0
:
