超级递归算法：理论与实践

需积分: 0 69 浏览量更新于2024-07-18 收藏 2.13MB PDF 举报

"Super-Recursive Algorithms" 本书"Super-Recursive Algorithms"由Burgin撰写，是计算机科学领域的一部专著，深入探讨了算法设计和计算机理论中的高级主题。超级递归算法（Super-Recursive Algorithms）是计算理论的一个重要分支，它超出了传统递归算法的范畴，涉及到更复杂和更强大的计算过程。递归算法是编程中常见的方法，通过函数调用自身来解决问题。而超级递归算法则进一步扩展了这个概念，它包含了自我修改和自我引用的特性，使得算法能够动态地改变其自身的结构和行为。这种类型的算法在处理复杂的自我适应系统、无限数据结构以及某些形式的自我认知问题时特别有用。书中可能涵盖了以下关键知识点： 1. **递归理论**：深入理解递归函数的定义和分类，包括递归可计算性、递归可枚举性和超越递归的边界。 2. **自修改程序**：探讨如何编写能够修改自己代码的程序，这在超级递归算法中是核心概念。 3. **无限计算**：讨论如何在有限资源下处理无限数据结构，这对于理解和设计超级递归算法至关重要。 4. **计算复杂性**：分析超级递归算法的计算复杂度，以及它们与已知复杂性类的关系。 5. **形式化证明**：可能包括如何为超级递归算法建立形式化的正确性证明，以及如何在这些系统中进行形式推理。 6. **应用实例**：可能包含超级递归算法在实际问题中的应用，如人工智能、知识表示、自动推理和分布式系统等。 7. **相关领域**：与其他计算机科学分支的交叉，如逻辑、集合论、形式语言理论和软件工程。 8. **数学基础**：书中可能涵盖了支撑超级递归算法的数学基础，如集合论、图论和代数结构。 9. **编程和验证**：如何将超级递归算法应用于编程实践，并进行有效的验证和测试。 10. **最新研究进展**：可能还包括该领域的最新研究成果和技术趋势，对学术研究和专业开发人员都有很高的参考价值。通过阅读这本书，读者可以了解到计算机科学的前沿知识，特别是对于那些对递归理论有深厚兴趣，或者正在研究复杂算法和计算模型的学者和从业者来说，这是一个不可多得的资源。

1.1 Information processing systems (IPS) 3

processing imply a typology of IPS and explain what is possible to be done with the

information being processed or, in other words, what information operations exist.

To have an organized structure, we consider information operations on several levels.

The most basic is the microlevel. It contains the most fundamental operations that

allow one to build other operations on higher levels. Basic information operations

are determined by actions that involve information. There are three main actions:

1. Changing the place of information in the physical world.

2. Changing information itself or its representation.

3. Doing nothing with information (and protecting it from any change).

These actions correspond to three basic information micro-operations:

1. Information transition.

2. Information transformation.

3. Information preservation.

There are three main forms of each operation:

1. Information transition.

a) Transition outside from inside of a system is called emission.

b) Transition inside a system from outside is called reception.

c) Transition between two similar points/systems is called pure transition or

equitransition.

2. Information transformation.

a) Substance transformation is a change of information itself in a direct way.

b) Fo rm transformation is a change of information representation.

c) External transformation is a change of the context of information.

Deﬁnition 1.1.1. The context of information is the knowledge system to which this

information is related.

According to the general theory of information (cf. (Burgin, 1997)), changing the

context of information, we change information itself in an indirect way.

3. Information preservation.

a) Information storage.

b) Information storage with protection from change/damage.

c) Information storage with protection from change/damage and restoration of

damaged portions.

Actually storage is never pure because it always includes, at least, data transi-

tion to special storage places, which are traditionally called memory. In some cases,

storage includes information transformation. An example is the dynamic storage in

neural networks (see Section 2.4). On the macro level, we have much more informa-

tion operations. The most popular and important of them are:

♦ Computation, which includes many transformations, transitions, and preserva-

tions.

4 1 Introduction

♦ Communication, which also includes many transformations, transitions, and

preservations.

Examples of other information operations are information acquisition, informa-

tion selection, information search, information production, and information dissemi-

nation. Now computers perform all of them and computer power is usually estimated

with respect to these operations.

There are important relationships between these operations. For instance, it is

possible to compute through communication. This is the essence of the connection-

ist paradigm for which the main operation is transmission of signals, while their

transformation is an auxiliary operation. The most explicit realization of the connec-

tionist paradigm is the neural network. Any conventional computation, for example,

computation on a PC, also demands information transmission, but in this case trans-

mission is an auxiliary operation. However, the Internet has both connectionist and

transmission capabilities, and computations like grid computation will combine both

paradigms.

The storage of data has been always a basic function of conventional computers,

and hierarchical systems of memory have been developed over time. However, an IPS

can memorize data even without a separate component for this function. It is possible

to store information by computation or communication. Such dynamic storage is

described for artiﬁcial neural networks in Section 2.4.

IPS have two structures — static and dynamic. The static structure reﬂects the

mechanisms and devices that realize information processing, while the dynamic

structure shows how this processing goes on and how these mechanisms and devices

function and interact. We now discuss the static structure, which has two forms: syn-

thetic and systemic, or analytic.

1.1.1 Static synthetic structure

Any IPS, we denote it by W, consists of three components:

♦ Hardware, which consists of physical devices of the IPS.

♦ Software, which contain programs that regulate the IPS functioning.

♦ Infware, which represents information processed by the IPS.

In turn, the hardware of an IPS has its three main parts: the inputdevice(s), in-

formation processor(s), and outputdevice(s), which are presented in Figure 1.1 and

give the ﬁrst level approximation to the structure of IPS.

Figure 1.1. Triadic structure of IPS

1.1 Information processing systems (IPS) 5

The theory of algorithms has traditionally concentrated on the central component

of IPS, paying more attention to the problem of how abstract automata and algo-

rithms work rather than what is the result of this work. However, the triadic structure

of an IPS implies that all three components are important. Neglecting any one of

them may cause us to have inadequate understanding of IPS, which can hinder the

development of IPS.

To elaborate on this, consider the following. Initially, computers were able only

to print results. Contemporary computers can display their results on a printer, a

monitor, and even different audio devices. Computers and embedded devices send

their signals to control a diversity of mechanisms and machines. Contemporary ma-

chines now have not only a keyboard and a mouse but also trackballs, joysticks, light

pens, touch-sensitive screens, digitizers, scanners, and more. The theory must take

this into account.

It is interesting to remark that while information processing in quantum comput-

ers has been well elaborated, researchers have found that input and especially output

appear to be much more complicated issues. Reading the obtained result of a com-

putation is a crucial problem for building future quantum computers. This problem

remains unsolved (cf. Hogg, 1999).

Awareness of criticality of input and output components has resulted in the de-

velopment of the practical area of human-computer interaction (HCI). People began

to comprehend the interactive role of computers (in particular) and IPS (in general):

a substantial amount of computers are built for working with and for people. Interac-

tion becomes crucial not only in utilization of computers and their software, but also

for computer and software design (Vizard, 2001).

The same understanding in the theoretical area resulted in inductive, limit, and

interactive directions in the theory of algorithms. The ﬁrst two directions advanced

computational potential by developing output techniques (Burgin, 1983, 1999, 2001;

Gasarch and Smith, 1997; Hintikka and Mutanen, 1998), while the latter approach

achieved similar results by making the principal emphasis on input and output com-

ponents as the basis for interaction between IPS (Hoare, 1984; Goldin and Wegner,

1988; Milner, 1989; Wegner, 1998; van Leeuwen and Wiedermann, 2001). This ex-

tends computing power of algorithms and provides mathematical models, which are

more adequate for representing modern computers than classical models such as Tur-

ing machines or cellular automata.

We have been discussing the input and output components of an IPS. We now

turn to the processor component. The processor component is itself traditionally par-

titioned into three components: control device(s), operational device(s), and memory.

On the one hand, there are IPS in which all three devices are separate and connected

by information channels. Abstract devices of this type are Turing machines, push-

down automata, and random access machines. In many cases, this involves a so-

phisticated architecture. On the other hand, it is possible that two or even all three

components coincide. Abstract devices of this type are neural networks, ﬁnite au-

tomata, and formal grammars. The latter possess only an operating mechanism in

the form of transformation rules.

6 1 Introduction

The structure of an IPS allows us to classify three main types of IPS according to

their computer architecture: the centralized computer architecture (CCA), controlled

distributed computer architecture (CDCA), and autonomous distributed computer

architecture (ADCA).

Remark 1.1.1. There is a distinction between computer architecture and computing

architecture. The computer architecture of an IPS (computer) reﬂects organization

of the IPS devices and their functioning. The computing architecture of informa-

tion processing represents the organization of processes in the IPS. One computer

architecture allows one to realize, as a rule, several computing architectures.

Deﬁnition 1.1.2. The CCA is a structure of an IPS with one control and one opera-

tional device.

The classical Turing machine with one tape and one head embodies the central-

ized computer architecture and realizes the sequential paradigm of computation.

Remark 1.1.2. Usage of a single operational device implies that operations are per-

formed sequentially. However, this does not preclude parallel processing. Indeed, it

is possible that a single portion of data consists of many parts. For example, it may be

a vector, matrix, or multidimensional array. Vector and array machines (Pratt, Rabin,

and Stockmeyer, 1974; Leeuwen and Wiedermann, 1985) are mathematical models

for such parallel information processing by an IPS with CAA. Computation of such

machines is explicitly sequential and implicitly parallel.

A complement for centralized computation is distributed computation, which

is substantiated by distributed computer architecture. It has two types: CDCA and

ADCA.

Deﬁnition 1.1.3. The CDCA is an IPS structure with one control and many opera-

tional devices.

The Turing machine with many heads is an example of a controlled distributed

computing architecture, and realizes the parallel paradigm of computation.

Remark 1.1.3. The control device in an IPS with CDCA organizes the work of all op-

erational devices. It can work in two modes. In one, called SIMD (single instr

uction

multiple data), the control device gives one and the same instruction to all opera-

tional devices. In the other mode, called MIMD (multiple instruction multiple data),

the control device processes separate control information for each operational device

or their clusters.

Deﬁnition 1.1.4. The ADCA is an IPS structure with many control and many opera-

tional devices.

The neural network demonstrates the autonomous distributed computing archi-

tecture and realizes the concurrent paradigm of computation.

1.1 Information processing systems (IPS) 7

Remark 1.1.4. There are different ways for an IPS with ADCA to organize relations

between control and operational devices. The simplest way is when one control de-

vice and one operational device are combined into a single block. In a more elabo-

rated IPS, one control device is connected to a cluster of operational devices. Another

case exists for when there are no restrictions on connections. Moreover, the system

of connections between control and operational devices may be hierarchical with a

sophisticated structure.

1.1.2 Static systemic structure

The system approach (Bertalanffy, 1976) explains that a system consists of elements

and connections between the elements. Taking into account that any system is con-

nected to other systems, we come to the structural classiﬁcation, suggested by Bell

and Gray (1997) for cyberspace. Accordingly, any IPS W consists of three parts:

♦ Autonomous IPS that belong to W (such as computers, local networks, etc.).

♦ Networking technology of W, which connects autonomous IPS from W and al-

lows them to communicate with each another.

♦ Interface (transducer) technology of W, which connects W to people and other

systems from the environment of W.

In turn, each of these parts has hardware, software, and infware. All of them

give speciﬁc directions of the IPS development. For example, we may discuss the

progress of computer (IPS) hardware or innovations for interface software.

The dynamic structure of an IPS also has two forms: hierarchical and temporal.

1.1.3 Hierarchical dynamic structure

The static structure of IPS inﬂuences their dynamic structure. Consequently, we have

the following hierarchical structure:

♦ Processes in autonomous IPS.

♦ Processes of interaction of autonomous IPS.

♦ Interface processes with external systems.

We make a distinction between computational or information processing archi-

tecture and computer or IPS architecture. The former represents organization of a

computational process. The latter deﬁnes computer/IPS components and the connec-

tions between them. The same computer architecture may be used for organization

and realization of different computational architectures. For example, a computer

with the parallel architecture can realize sequential computation. At the same time,

some types of computational architectures can be realized only by a speciﬁc kind of

computer architecture. For example, we need a computer with the parallel architec-

ture for performing parallel computation.

剩余313页未读，继续阅读

mproxy

粉丝: 0
资源: 7

超级递归算法：理论与实践

Super-Recursive Algorithms.pdf

Super-Recursive Algorithms_C++_algorithms_

pixel-recursive-super-resolution-master.zip_Super-Resolution_bre

git clone --recursive 如何使用

git submodule update --init --recursive --remote

git clone --recursive用法

git clone xxx.git --recursive

golang 命令行参数，形式 -R, --recursive=false

git --recursive

git clone --recursive

最新资源