Towards a Mathematical Science of …… 翻译.doc

1、Introduction 简介In this paper I shall discuss the prospects for a mathematical science of computation . In a mathematical science ,it is possible to deduce from the basic assumptions,the important properties of the entities treated by the science. Thus，from Newtons law of gravitation and his laws of motion,one can duduce that the planetary orbits obey kerplers laws.我将在这篇文章中谈谈数学化科学计算的前景。在数学化的科学中，从一些基本的结论中可以推断：被数学科学处理地重要的实体前景。从而，从牛顿万有引力定律和他的运动定律，有人推出了行星轨道满足开普勒定理。What are the entities with which the science of computation deals? 计算科学处理的实体是什么？What kinds of facts about these entities would we like to derive? 关于这些实体我们想要的推导什么种类的事实？What are the basic assumptions from which we should start? 从我们开始什么事基本的假设？What important results have already been obtained? 已经获得什么重要的结论？How can the mathematical science help in the solution of practical problems?在实际问题上，数学化的科学怎么帮忙的？I would like to propose some partial answers to these questions. These partial answers suggest some problems for future work. First I shall give some very sketchy general answers to the questions. First ,I shall give some very sketchy general answers to the questions. Then I shall present some recent results on three specific questions. Finally, I shall try to draw some conclusions about practical applications and problems for future work.关于这些问题我想给出一些部分答案。这些部分答案对未来的工作问题有些建议。我先给出一些概要关于这些问题的答案。然后我将给出三个特殊问题一些当前的结果。最后我将试着得出一些关于实际应用和来来研究问题的结论。2. What Are The Entities With Which Computer Science Deals?什么是“计算机科学处理与实体？ These are problems, procedures, data spaces, programs representing procedures in particular programming languages, and computers.这些问题，程序，数据空间，代表在特定的编程语言程序的方案，和计算机。A problem is defined by the criterion which determines whether a proposed solution is accepted. One can understand a problem completely without having any method of solution. Procedures are usually built up from elementary procedures. What these elementary procedures may be, and how more complex procedures are constructed from them, is one of the first topics in computer science. This subject is not hard to understand since there is a precise notion of a computable function to guide us, and computability relative to a given collection of initial functions is easy to define.A problem is defined by the criterion which determines whether a proposed solution is accepted.一个问题定义的标准，决定建议的解决方案能否被接受。One can understand a problem completely without having any method of solution.人们能够理解的问题，完全没有任何解决方法。Procedures are usually built up from elementary procedures.程序通常建立了基本程序。 What these elementary procedures may be, and how more complex procedures are constructed from them, is one of the first topics in computer science.这些基本程序，以及如何从他们建造更复杂的程序，在计算机科学中的首要议题之一。This subject is not hard to understand since there is a precise notion of a computable function to guide us, and computability relative to a given collection of initial functions is easy to define.这个题目是不难理解的，因为有一个可精确计算函数的概念引导我们，很容易定义可计算相对的初始功能集合。Procedures operate on members of certain data spaces and produce members of other data spaces, using in general still other data spaces as intermediates. A number of operations are known for constructing new data spaces from simpler ones, but there is as yet no general theory of representable data spaces comparable to the theory of computable functions.程序操作上的某些数据空间成员和其他数据空间的成员，还有其他作为中间体使用的数据空间。 从简单的空间A number of operations are known for constructing new data spaces from simpler ones, but there is as yet no general theory of representable data spaces comparable to the theory of computable functions.已知的操作，为其构建新的数据，但目前还没有表示数据位的一般理论与可计算函数理论。Programs are symbolic expressions representing procedures. The same procedure may be represented by different programs in different programming languages. We shall discuss the problem of defining a programming language semantically by stating what procedures the programs represent. As for the syntax of programming languages, the rules which allow us to determine whether an expression belongs to the language have been formalized, but the parts of the syntax which relate closely to the semantics have not been so well studied. The problem of translating procedures from one programming language to another has been much studied, and we shall try to give a definition of the correctness of the translation.程序是代表程序的符号表达式。 The same procedure may be represented by different programs in different programming languages.同样的过程可能由不同的编程语言表示不同的程序。 We shall discuss the problem of defining a programming language semantically by stating what procedures the programs represent.我们将讨论说明什么程序方案代表一种编程语言的语义定义的问题。As for the syntax of programming languages, the rules which allow us to determine whether an expression belongs to the language have been formalized, but the parts of the syntax which relate closely to the semantics have not been so well studied.As for the syntax of programming languages, the rules which allow us to determine whether an expression belongs to the language have been formalized, but the parts of the syntax which relate closely to the semantics have not been so well studied.至于编程语言，语法规则，这使我们能够确定一个表达式是否属于正式语言，但密切相关的语义，语法的部分没有得到很好的研究。The problem of translating procedures from one programming language to another has been much studied, and we shall try to give a definition of the correctness of the translation.从一种编程语言的翻译程序的问题已经很多研究，我们会尽力给翻译的正确性的定义。Computers are finite automata. From our point of view, a computer is defined by the effect of executing a program with given input on the state of its memory and on its outputs. Computer science must study the various ways elements of data spaces are represented in the memory of the computer and how procedures are represented by computer programs. From this point of view, most of the current work on automata theory is beside the point.计算机是有限自动机。 From our point of view, a computer is defined by the effect of executing a program with given input on the state of its memory and on its outputs.从我们的角度来看，是指由计算机执行其内存的状态，并在其输入输出方案与效果。 Computer science must study the various ways elements of data spaces are represented in the memory of the computer and how procedures are represented by computer programs.计算机科学必须研究各种方式的数据空间的元素，在计算机的内存空间表示数据和如何由计算机程序表示程序。 From this point of view, most of the current work on automata theory is beside the point.从这个角度来看，自动机理论的大部分目前的工作是毫无意义的。3 What Kinds of Facts About Problems, Procedures, data Spaces, Programs, And Computers Would We Like to Derive?我们愿意派生出什么种类的关于问题、程序、数据空间、方案以及计算机的事实？Primarily, we would like to be able to prove that given procedures solve given problems. However, proving this may involve proving a whole host of other kinds of statement such as: 实际上，我们更愿意去证明那些给定程序的特定问题。然而，证明这类问题很可能涉及要证明整个主机其它种类的声明，例如：1. Two procedures are equivalent, i.e. compute the same function.2. A number of computable functions satisfy a certain relationship, such as an algebraic identity or a formula of the functional calculus.3. A certain procedure terminates for certain initial data, or for all initial data.4. A certain translation procedure correctly translates procedures between one programming language and another.5. One procedure is more efficient than another equivalent procedure in the sense of taking fewer steps or requiring less memory.6. A certain transformation of programs preserves the function expressed but increases the efficiency.7. A certain class of problems is unsolvable by any procedure, or requires procedures of a certain type for its solution.1、两个程序是等价的，即实现一个相同的功能。2、大量的可计算的函数可以满足某某种特定的关系，例如一个代数的特性或者一个功能演算公式。3、某个用来终止特定初始数据或所有初始数据的特定程序。4、某个特定的翻译程序正确的将程序从一种编程语言翻译为另一种程序语言。5、某个程序比另外一个更高效，例如步骤较少或者需要更少的内存。6、某个改造方案表示要保留原有的功能但是要求提高效率。7、某类问题运用任何程序都无法解决或者解决这样的问题需要某种特定的类型。4 What Are The Axioms And Rules of Inference of A Mathematical Science of Computation?什么是一个计算数学推理的公理和规则呢 ？ Ideally we would like a mathematical theory in which every true statement about procedures would have a proof, and preferably a proof that is easy to find, not too long, and easy to check. In 1931, Godel proved a result, one of whose immediate consequences is that there is no complete mathematical theory of computation. Given any mathematical theory of computation there are true statements expressible in it which do not have proofs. Nevertheless, we can hope for a theory which is adequate for practical purposes, like proving that compilers work; the unprovable statements tend to be of a rather sweeping character, such as that the system itself is consistent. 理想的情况下，我们希望有关程序的每一个真实的陈述证明，最好的证明，很容易找到，不要太长，且易于检查的一个数学理论。In 1931, Gdel proved a result, one of whose immediate consequences is that there is no complete mathematical theory of computation.1931年，哥德尔证明了一个结果，其直接后果之一是，有没有完整的数学理论计算。 Given any mathematical theory of computation there are true statements expressible in it which do not have proofs.由于任何计算数学理论有表达的，在它的真正报表没有证明的。 Nevertheless, we can hope for a theory which is adequate for practical purposes, like proving that compilers work; the unprovable statements tend to be of a rather sweeping character, such as that the system itself is consistent.尽管如此，我们希望这是出于实用的目的足够的理论，如证明编译器的工作证明的陈述往往是一个比较笼统的字符，例如，该系统本身是一致的的。 It is almost possible to take over one of the systems of elementary number theory such as that given in Mostowskis book ”Sentences Undecidable in Formalized Arithmetic” since the content of a theory of computation is quite similar. Unfortunately, this and similar systems were designed to make it easy to prove meta-theorems about the system, rather than to prove theorems in the system.As a result, the integers are given such a special role that the proofs of quite easy statements about simple procedures would be extremely long. 这几乎是可能接管如Mostowski的书“的句子形式化算术不可判定的”，因为计算理论的内容颇为相似的初等数论的系统之一。 Unfortunately, this and similar systems were designed to make it easy to prove meta-theorems about the system, rather than to prove theorems in the system.不幸的是，这和类似的系统，旨在使很容易地证明有关系统的元定理，而不是系统中的定理证明。 As a result, the integers are given such a special role that the proofs of quite easy statements about simple procedures would be extremely long.因此，整数给出了这样一个特殊的角色，简单的程序很容易报表的证明将是极其漫长。 Therefore it is necessary to construct a new, though similar, theory in which neither the integers nor any other domain, (e.g. strings of symbols) are given a special role. Some partial results in this direction are described in this paper. Namely, an integer-free formalism for describing computations has been developed and shown to be adequate in the cases where it can be compared with other formalisms. Some methods of proof have been developed, but there is still a gap when it comes to methods of proving that a procedure terminates. The theory also requires extension in order to treat the properties of data spaces. 因此，有必要构建一个新的，虽然类似，理论，这既不是整数或任何其他领域（如串符号）被赋予了特殊的的作用。 Some partial results in this direction are described in this paper.本文描述了一些局部的结果在这个方向。 Namely, an integer-free formalism for describing computations has been developed and shown to be adequate in the cases where it can be compared with other formalisms.即描述计算整数的形式主义，已被开发，并在那里它可以比其他形式主义的情况下证明是足够。 Some methods of proof have been developed, but there is still a gap when it comes to methods of proving that a procedure terminates.举证的一些方法已被开发，但仍存在一定的差距，当涉及到一个程序终止的证明方法。 The theory also requires extension in order to treat the properties of data spaces.该理论还需要为了治疗的属性数据空间的扩展。 5. What Important Results Have Been Obtained Relevant to A Mathematical Science of Computation? 5.在计算数学科学领域已经取得了哪些重要成果？In 1936 the notion of a computable function was clarified by Turing, and he showed the existence of universal computers that, with an appropriate program, could compute anything computed by any other computer. All our stored program computers, when provided with unlimited auxiliary storage, are universal in Turings sense. In some subconscious sense even the sales departments of computer manufacturers are aware of this, and they do not advertise magic instructions that cannot be simulated on competitors machines, but only that their machines are faster, cheaper, have more memory, or are easier to program. 1936年，图灵给出了可计算函数的概念，他指出通用计算机加以适当的算法可以计算出任何其他计算机能计算出的问题。图灵认为对于所有的存储程序计算机，当拥有无限的辅助存储将会被普遍接受。在潜意识上，很多计算机生产商的销售部门也意识到了这一点，他们不去给那些神奇的并且难以被竞争对手模仿的功能做广告，而只是（让他们的）机器更快，更便宜，拥有更多的内存，或更容易编程。The second major result was the existence of classes of unsolvable problems. This keeps all but the most ignorant of us out of certain Quixotic enterprises such as trying to invent a debugging procedure that can infallibly tell if a program being examined will get into a loop. Later in this paper we shall discuss the relevance of the results of mathematical logic on creative sets to the problem of whether it is possible for a machine to be as intelligent as a human. In my opinion it is very important to build a firmer bridge between logic and recursive function theory on the one side, and the practice of computation on the other. 第二个主要的结果是类存在无法解决的问题。这样可以使所有但最无知的我们一定的唐吉诃德式的企业，如试图发明一种调试的程序，可绝对无误告诉如果正在审议的程序进入一个循环将得到。在本文后面，我们将讨论相关的问题，无论是一台机器可以作为人类的智能创意集数理逻辑的结果。在我看来，它是非常重要的建设的一方，更稳固的桥梁之间的逻辑和递归函数理论和计算上的其他做法。Much of the work on the theory of finite automata has been motivated by the hope of applying it to computation. I think this hope is mostly in vain because the fact of finiteness is used to show that the automaton will eventually repeat a state. However, anyone who waits for an IBM 7090 to repeat a state, solely because it is a ?nite automaton, is in for a very long wait.有限自动机理论的大部分工作已经由希望将它应用到计算的动机。我觉得这个希望是徒劳的，主要是因为它的有限性的事实是用来显示自动机的一个国家最终会重复。然而，任何人重复的状态，仅仅因为它是一个有限自动机，为IBM7090等待的是一个非常漫长的等待。6 How Can A Mathematical Science of Computation Help in The Solution of Practical Problems?N