非常规计算理论探索：Advances in Unconventional Computing Vol. 1

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

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

"《Advances in Unconventional Computing_ Volume 1》是关于非常规计算领域的一本电子书，内容高清且为最新版本，由Andrew Adamatzky编辑，是经典著作系列之一，英文出版。该书关注的是计算的新兴、复杂性和计算理论，可能涵盖了非传统计算模型、自组织系统、复杂网络以及混沌理论等多个方面。" 非常规计算是指那些超越传统计算机科学范畴的计算方法，它探索新的计算范式和物理机制，试图解决传统计算面临的局限性。《Advances in Unconventional Computing》可能深入探讨了以下几个关键知识点： 1. **涌现（Emergence）**: 涌现是复杂系统中的一个核心概念，指在简单个体之间相互作用下产生的全局复杂行为或模式。在非常规计算中，涌现可能被用来描述计算过程中的自组织现象，比如细胞自动机和人工生命的研究。 2. **复杂性（Complexity）**: 这涉及到理解和模拟复杂系统的行为，如生物系统、社会网络或经济系统。非常规计算试图找到处理复杂性问题的新途径，可能包括使用模糊逻辑、神经网络或量子计算等方法。 3. **计算理论（Computational Theory）**: 书中可能详细阐述了非常规计算模型的基础理论，如非图灵可计算性、物理计算、生物计算等，这些理论扩展了我们对计算可能性的认识。 4. **非传统计算模型（Non-Traditional Computing Models）**: 包括生物启发的计算，如DNA计算、神经网络、群体智能、量子计算和光子计算等，这些模型利用自然界的物理和生物过程进行信息处理。 5. **自组织系统（Self-Organizing Systems）**: 自组织系统能够在没有外部控制的情况下改变其结构和行为。书中可能讨论了如何利用这种特性进行计算，例如通过模拟自然界中的生态交互来设计高效的算法。 6. **复杂网络（Complex Networks）**: 研究复杂网络的结构、动力学和功能，如互联网、社交网络和生物网络，这些网络的特性在非常规计算中可能被用来改进数据处理和信息传播。 7. **混沌理论（Chaos Theory）**: 混沌理论研究看似随机但实际上有确定性的动态系统，可能在书中被用作探索不可预测性和计算效率的新视角。 8. **编辑和编委会：** Andrew Adamatzky与其他专家共同编辑这本书，他们来自世界各地的知名大学和研究机构，确保了内容的专业性和权威性。《Advances in Unconventional Computing_ Volume 1》提供了对非常规计算领域的深度洞察，对于理解并开发新的计算方法和技术具有重要的学术价值和实践意义。通过阅读此书，读者可以拓宽对计算边界的认知，并可能发现新的解决问题的方法。

资源详情

资源推荐

6 S.G. Akl

2. The requirement that this number be ﬁxed once and for all is necessary for any

model of computation that purports to be “universal”; see, for example, [25], p.

210.

Without these two requirements, the theory of computation in general, and the theory

of algorithms, in particular, would be totally irrelevant.

The consequences to theoretical and practical computing are signiﬁcant. Thus

the conjectured “Church–Turing Thesis” is false. It is no longer true that, given

enough time and space, any single general-purpose computer, deﬁned a priori, can

perform all computations that are possible on all other computers. Not the Turing

Machine, not a personal computer, not the most powerful of supercomputers. In view

of the computational problems mentioned in Sect.1.1.1 and presented more fully in

Sect.1.3 (for details, see [4–15, 18–20, 29, 45–50]), the only possible universal

computer would be one capable of an inﬁnite number of operations per time unit.

In fact, this work has led to the discovery of computations that can be performed

on a quantum computer but not on any classical machine (even one with inﬁnite

resources), thus showing for the ﬁrst time that the class of problems solvable by

classical means is a true subset of the class of problems solvable by quantum means

[47]. Consequently, the only possible universal computer would have to be quantum

(as well as being capable of an inﬁnite number of operations per time unit).

1.1.4 Motivation

The results described in the previous paragraphs were obtained and published

between 2005 and 2015. They appeared in technical reports, were presented at con-

ferences, and published as journal papers and book chapters, as documented in the

bibliography section. Yet, ten years after they were ﬁrst announced, they remain

generally misunderstood, and consequently controversial. This is not surprising: Old

habits die hard. It is difﬁcult to abandon ideas that one has believed all of one’s

life. This applies to inherited scientiﬁc ideas, that people persist in defending, even

if these ideas are demonstrably wrong. Disruptive innovations usually disturb and

destabilize. To announce that the long-held belief in universality in computation is,

in fact, in error was met with great skepticism, to say the least. Most of the animosity

towards the author came from scientists who had not bothered to read his work. The

title of a paper alone was sufﬁcient to ignite their anger.

It started with hostile email. Then came the uninspired referee reports. And ﬁnally

Wikipediaremovedtheentryon NonuniversalityinComputation, created by a student

of the author, after one reader objected. It was clear that these people had not read

any of my work on the subject. This is when I decided to write this chapter, based

on a web page [16] I had created to reply to unfounded criticisms.

The remainder of this chapter is organized as follows. Section1.2 provides def-

initions for many of the terms used in the discussion to follow (some of the more

common of these terms were already introduced in this section without deﬁnition, in

1 Nonuniversality in Computation … 7

order not to interrupt the ﬂow of the opening paragraphs). Section1.3 summarizes

the work in my previous papers, culminating in the fundamental result that the ‘Uni-

versal Computer’ is a myth. Section1.4 is a dialog with an imaginary debater who

embodies all of my critics and voices all their misconceptions. Section 1.5 offers a

computational challenge to the readers.

1.2 Preliminaries

A time unit is the length of time required by a processor to perform a step of its

computation, consisting of three elementary operations: a read operation in which it

receives a constant number of ﬁxed-size data as input, a calculate operation i n which

it performs a ﬁxed number of constant-time arithmetic and logical calculations (such

as adding two numbers, comparing two numbers, and so on), and a write operation

in which it returns a constant number of ﬁxed-size data as output.

A sequential computer, consists of a single processor. A parallel computer has

n processors, numbered 1 to n, where n ≥ 2. Both computers use the same type of

processor and that processor is the fastest possible [2]. The assumption that the com-

puters on hand, whether sequential or parallel, use the fastest conceivable processor

is an important one. This is because the speed of the processor used is what speci-

ﬁes the duration of a time unit, as deﬁned in the previous paragraph; the faster the

processor, the smaller the time unit. In the time-varying variables computation of

Sect.1.1.2, for example, the value of each input variable X

(t) changes at the same

speed as the processor in charge of evaluating F

(t)).

The concept of computational universality is one of the dogmas in Computer

Science, stated as follows: Given enough time and space, any general-purpose com-

puter can, through simulation, perform any computation that is possible on any other

general-purpose computer. Statements such as this are commonplace in the computer

science literature, and are served as standard fare in undergraduate and graduate

courses alike. Sometimes the statement is restricted to the Turing Machine (TM),

and is referred to as the “Church–Turing Thesis” (CTT), which stipulates that there

exists a Universal Computer, namely, the TM; thus, the following quote is typical:

A Turing Machine can do everything that a real computer can do [56], p. 125.

Other times, the statement is made more generally about a Universal Computer,

that is, a computer capable of executing any computation that can be performed by

any other computer; thus, we are told:

It is possible to build a universal computer: a machine that can be programmed to perform

any computation that any other physical object can perform [25], p. 134.

As its name indicates, the CTT is a conjecture, whose proof has remained elusive

due to the difﬁculty in deﬁning what it means to compute. A few points are worth

making in this regard:

8 S.G. Akl

1. The Universal Turing Machine (UTM) deﬁned by Alan Turing, is ‘universal’

in the sense of being able to simulate any computation performed by any other

special-purpose TM. In other words, the UTM can be programmed to execute

any TM computation. This is a provable property, and is not in question here or

elsewhere.

2. However, the UTM is not known to be ‘universal’ in the more general sense of

being able to simulate by its own means any computation performed by means

of any other computational device (not necessarily a TM). It is this universality

of the UTM, in the more general sense, that is expressed by the CTT.

3. My work has shown the CTT, and more generally computational universality, to

be false. Speciﬁcally, I proved the stronger result that no ‘Universal Computer’

is possible, thus eliminating, not only the UTM, but also all other models of

computation as contenders for the title.

1.3 Inherently Parallel Computations

The term inherently parallel computation refers to a computation that can be per-

formed successfully only on a parallel computer with an appropriate number of

processors. Examples are computations that involve: time-varying variables, time-

varying computational complexity, rank-varying computational complexity, inter-

acting variables, uncertain time constraints, and variables obeying mathematical

constraints. These computations also provide counterexamples to the existence of

a universal computer [4–15, 18–20, 29, 45–50].

1.3.1 Time-Varying Variables

This computation was described in Sect.1.1.2. It is reproduced brieﬂy here for com-

pleteness in the context of inherently parallel computations. For a positive integer n

larger than 1, we are given n functions, each of one variable, namely, f

, f

,..., f

operating on the n physical variables x

, x

,...,x

, respectively. Speciﬁcally, it is

required to compute f

),fori = 1, 2, ..., n. For example, f

) may be equal to x

What is unconventional about this computation, is the fact that the x

are themselves

(unknown) functions x

(t), x

(t),...,x

(t), of the time variable t . It takes one time

unit to evaluate f

(t)). The problem calls for computing f

(t)),1≤ i ≤ n,at

time t = t

. Because the function x

(t) is unknown, i t cannot be inverted, and for

k > 0, x

) cannot be recovered from x

+ k).

A sequential computer fails to compute all the f

as desired. Indeed, suppose that

) is initially operated upon. By the time f

)) is computed, one time unit

would have passed. At this point, the values of the n − 1 remaining variables would

have changed. The same problem occurs if the sequential computer attempts to ﬁrst

read all the x

, one by one, and store them before calculating the f

1 Nonuniversality in Computation … 9

By contrast, a parallel computer consisting of n independent processors may

perform all the computations at once: For 1 ≤ i ≤ n, and all processors working at

the same time, processor i computes f

)), leading to a successful computation.

1.3.2 Time-Varying Computational Complexity

Here, the computational complexity of the problems at hand depends on time (rather

than being, as usual, a function of the problem size). Thus, for example, tracking a

moving object (such as a spaceship racing towards Mars) becomes harder as it travels

away from the observer.

Suppose that a certain computation requires that n independent functions, each of

one variable, namely, f

), f

),..., f

), be computed. Computing f

)

at time t requires C(t) = 2

operations, for t ≥ 0 and 1 ≤ i ≤ n. Further, there is

a strict deadline for reporting the results of the computations: All n values f

),..., f

) must be returned by the end of the third time unit, that is, when

t = 3.

It should be easy to verify that no sequential computer, capable of exactly one

constant-time operation per step (that is, per time unit), can perform this computa-

tion for n ≥ 3. Indeed, f

) takes C(0) = 2

= 1 time unit, f

) takes another

C(1) = 2

= 2 time units, by which time three time units would have elapsed. At

this point none of f

), . . . , f

) would have been computed. By contrast, an

n-processor parallel computer solves the problem handily. With all processors oper-

ating simultaneously, processor i computes f

) at time t = 0, for 1 ≤ i ≤ n.This

consumes one time unit, and the deadline is met.

1.3.3 Rank-Varying Computational Complexity

Suppose that a computation consists of n stages. There may be a certain precedence

among these stages, or the n stages may be totally independent, in which case the

order of execution is of no consequence to the correctness of the computation. Let

the rank of a stage be the order of execution of that stage. Thus, stage i is the i th stage

to be executed. Here we focus on computations with the property that the number of

operations required to execute stage i is C(i), that is, a function of i only.

When does rank-varying computational complexity arise? Clearly, if the compu-

tational requirements grow with the rank, this type of complexity manifests itself in

those circumstances where it is a disadvantage, whether avoidable or unavoidable,

to being ith, for i ≥ 2. For example, the precision and/or ease of measurement of

variables involved in the computation in a stage s may decrease with each stage

executed before s.

The same analysis as in the previous section applies by substituting the rank for

the time.

10 S.G. Akl

1.3.4 Interacting Variables

A physical system has n variables, x

, x

, ..., x

, each of which is to be measured or

set to a given value at regular intervals. One property of this system is that measuring

or setting one of its variables modiﬁes the values of any number of the system

variables unpredictably.

A sequential computer measures one of the values (x

, for example) and by so

doing it disturbs the equilibrium, thus losing all hope of recording the state of the

system within the given time interval. Similarly, the sequential approach cannot

update the variables of the system properly: Once x

has received its new value,

setting x

disturbs x

unpredictably.

A parallel computer with n processors, by contrast, will measure all the variables

, x

, ..., x

simultaneously (one value per processor), and therefore obtain an

accurate reading of the state of the system within the given time frame. Consequently,

new values x

, x

,...,x

can be computed in parallel and applied to the system

simultaneously (one value per processor).

1.3.5 Uncertain Time Constraints

In this paradigm, we are given a computation each of whose components, namely, the

input phase, the calculation phase, and the output phase, needs to be computed by a

certain deadline. However, unlike the standard situation in conventional computation,

the deadlines here are not known at the outset. In fact, and this is what makes this

paradigm truly unconventional, we do not know at the moment the computation is

set to start, what needs to be done, and when it should be done. Certain physical

parameters, from the external environment surrounding the computation, become

spontaneously available. The values of these parameters, once received from the

outside world, are then used to evaluate two functions, call them f

and f

, that tell

us precisely what to do and when to do it, respectively.

The difﬁculty posed by this paradigm is that the evaluation of the two functions f

and f

is itself quite demanding computationally. Speciﬁcally, for a positive integer

n, the two functions operate on n variables (the physical parameters). Only a parallel

computer equipped with n processors can succeed in evaluating the two functions

on time t o meet the deadlines.

1.3.6 Computations Obeying Mathematical Constraints

There exists a family of computational problems where, given a mathematical object

satisfying a certain property, we are asked to transform this object into another

which also satisﬁes the same property. Furthermore, the property is to be maintained

剩余867页未读，继续阅读

J-10

粉丝: 18
资源: 483

非常规计算理论探索：Advances in Unconventional Computing Vol. 1

advances in financial machine learning

advances in financial machine learning pdf

advances in neural information processing systems

recent advances in deep learning for object detection

advances in microstrip and printed antennas.pdf

ieee icassp recent advances in nonnegative matrix factorization

用python 编写程序计算股票的Trin 指标

详细介绍下大模型的发展历程

灰狼优化算法原文引用

找几个关于基于Android的图书馆座位预约系统外文文献

给我一篇介绍Floquet Theory的文章

ElGamal短签名的相关文献

How transferable are features in deep neural networks?怎么引用

Which industries will see big growth in the next 10 years

用python编写程序计算上证50成分股的Trin指标

量子图像处理技术及其应用的参考文献10篇

advances and open problems in federated learning

最先进的svd算法的相关参考文献有哪些

最新资源