20547783
The Formalization of Mathematics
Zest for both system and objectivity is the formal logician's original sin. He pays for it by constant frustrations and by living ofttimes the life of an intellectual outcaste. The task of squeezing a large body of stubborn facts into a more or less rigid system can be a painful one, especially since the facts of mathematics are among the most stubborn of all facts. Moreover, the more general and abstract we get, the farther removed we are from the raw mathematical experience. As intuition ceases to operate effectively, we fall into many unexpected traps. The formal logician gets little sympathy for his frustrations. He is regarded as too rigid by his philosophical colleagues and too speculative by his mathematical friends. The life of an intellectual outcaste may be a result partly of temperament and partly of the youthfulness of the logic profession. The unfortunate lack of wide appeal of logic may, however, be prolonged partly on account of the fact that very little of the well-established techniques of mathematics seems applicable to the treatment of serious problems of logic. The axiomatic method is well suited to provide results which are both exact and systematic. How attractive would it be if we could get an axiom system in which all the axioms and deductions were intuitively clear and all theorems of mathematics were provable? Such a system would undoubtedly satisfy Descartes who admits solely intuition and deduction, which are, for him, the only “mental operations by which we are able, wholly without fear of illusion, to arrive at the knowledge of things.” Indeed, according to Descartes, intuition and deduction “are the most certain routes to knowledge, and the mind should admit no others. All the rest should be rejected as suspect of error and dangerous.”
29402189
Non-Standard Models for Formal Logics
showed that there must be a model in which that portion of the model which is supposed to represent the positive integers of the formal logic is not in fact isomorphic to the positive integers; indeed it is not even well ordered by what is supposed to be the relation of <. For the purposes of the present paper, we do not need a precise definition of what is meant by a standard model of a formal logic. The non-standard models which we shall discuss will be flagrantly non-standard, as for instance a model of the sort whose existence is proved by Henkin. It will suffice if we and our readers are in agreement that a model of a formal logic is not a standard model if either: (a) The relation in the model which represents the equality relation in the formal logic is not the equality relation for objects of the model. (b) That portion of the model which is supposed to represent the positive integers of the formal logic is not well ordered by the relation <. (c) That portion of the model which is supposed to represent the ordinal numbers of the formal logic is not well ordered by the relation <. Our first result is that there is no standard model for the system known as "Quine's New Foundations" (see [2] and [3]). This is proved for the logic originally proposed by Quine (see [2]), which is a system of such apparent weakness that so far no one has succeeded in proving the axiom of infinity in the system. Clearly, if there is no standard model for this apparently weak system, there cannot be a standard model for any apparently stronger system which one might form by adding additional axioms, such as the axiom of infinity. A natural reaction to this result would be to suspect that there is no model of any sort for Quine's New Foundations; that is to suspect that it is inconsistent. An alternative (and much less likely) reaction would be to suspect that the property of not having a standard model is perhaps a not uncommon property of strong formal logics, and to suspect that perhaps several of the familiar strong formal logics have no standard model. Unlikely as this might appear at first sight, we will present considerable evidence in favor of the idea. In particular we shall show that it is a property of each of the familiar formal logics that if it is w-consistent then one cannot prove in the logic itself that if the logic is consistent it must have a standard model; in fact, one cannot prove this statement about the logic even in certain stronger logics if these stronger logics are simply consistent.
29040872
A Variant to Turing's Theory of Computing Machines
The principal purpose of this paper is to offer a theory which is closely related to Turing's [1] but is more economical in the basic operations. I t will be proved that a theoretically simple basic machine can be imagined and specified such tha t all partial recursive functions (and hence all solvable computation problems) can be computed by it and tha t only four basic types of instruction are employed for the programs: shift left one space, shift right one space, mark a blank space, conditional transfer. In particular, erasing is dispensable, one symbol for marking is sufficient, and one kind of transfer is enough. The reduction is somewhat similar to the realization of, for instance, the definability of conjunction and implication in terms of negation and disjunction, or of the definability of all these in terms of Sheffer's stroke function. As a result, i t becomes less direct to prove that certain things can be done by the machines, but a little easier to prove that certain things cannot be done. This serf-contained theory will b e presented, as far as possible, in a language which is familiar to those who are engaged in the use and construction of largescale computers. Turing's theory of computable functions antedated but has not much influenced the extensive actual construction of digital computers. These two aspects of theory and practice have been developed almost entirely independently of each other. The main reason is undoubtedly that logicians are interested in questions radically different from those with which the applied mathematicians and electrical engineers are primarily concerned. I t cannot, however, fail to strike one as rather strange that often the same concepts are expressed by very different terms in the two developments. One is even inclined to ask whether a rapprochement might not produce some good effect. This paper wiU, it is believed, be of use to those who wish to compare and connect the two approaches. Extensive use of Turing [1] and Kleene [2] (Chapter XI I I ) will be made, although the exposition is sufficient in itself.
42852449
A Formal System of Logic
The main purpose of this paper is to present a formal system P in which we enjoy a smooth-running technique and which countenances a universe of classes which is symmetrical as between large and small. More exactly, P is a system which differs from the inconsistent system of [ 1 ] only in the introduction of a rather natural new restrictive condition on the defining formulas of the elements (sets, membership-eligible classes). It will be proved that if the weaker system of [ 2 ] is consistent, then P is also consistent. After the discovery of paradoxes, it may be recalled, Russell and Zermelo in the same year proposed two different ways of safeguarding logic against contradictions (see [ 3 ], [ 4 ]). Since then various simplifications and refinements of these systems have been made. However, in the resulting systems of Zermelo set theory, generation of classes still tends to be laborious and uncertain; and in the systems of Russell's theory of types, complications in the matter of reduplication of classes and meaningfulness of formulas remain. In [ 2 ], Quine introduced a system which seems to be free from all these complications. But later it was found out that in it there appears to be an unavoidable difficulty connected with mathematical induction. Indeed, we encounter the curious situation that although we can prove in it the existence of a class V of all classes, and we can also prove particular existence theorems for each of infinitely many classes, nobody has so far contrived to prove in it that V is an infinite class or that there exists an infinite class at all.
11313688
Existence of Classes and Value Specification of Variables
In mathematics, when we want to introduce classes which fulfill certain conditions, we usually prove beforehand that classes fulfilling such conditions do exist, and that such classes are uniquely determined by the conditions. The statements which state such unicity and existence of classes are in mathematical logic consequences of the principles of extensionality and class existence. In order to illustrate how these principles enable us to introduce classes into systems of mathematical logic, let us consider the manner in which Godel introduces classes in his book on set theory. For instance, before introducing the definition of the non-ordered pair of two classes Godel puts down as its justification the following two axioms: By A4, for every two classes y and z there exists at least one non-ordered pair w of them; and by A3, w is uniquely determined in A4.
1953614
Alternative Proof of a Theorem of Kleene
11024065
An algorithm for optimal comma free codes with isomorphism rejection
A general algorithm for finding optimal comma-free codes and deriving upper bounds on the minimum redundancy of comma-free codes that implements the idea of isomorphism rejection is presented, together with tables with bounds on the minimum redundancy computed by using this algorithm.
9363924
RNA pseudoknot prediction using term rewriting
RNA plays a critical role in mediating every step of cellular information transfer from genes to functional proteins. Pseudoknots are widely occurring structural motifs found in all types of RNA and are also functionally important. Therefore predicting their structures is an important problem. In this paper, we present a new RNA pseudoknot prediction method based on term rewriting rather than on dynamic programming, comparative sequence analysis, or context-free grammars. The method we describe is implemented using the Mfold RNA/DNA folding package and the term rewriting language Maude. Our method was tested on 211 pseudoknots in PseudoBase and achieves an average accuracy of 74.085% compared to the experimentally determined structure. In fact, most pseudoknots discovered by our method achieve an accuracy of above 90%. These results indicate that term rewriting has a broad potential in RNA applications from prediction of pseudoknots to higher level RNA structures involving complex RNA tertiary interactions.
804068
Evaluation of RSVP and Mobility-Aware RSVP Using Performance Evaluation Process Algebra
As a resource reservation mechanism, the Resource ReSerVation Protocol (RSVP) faces a lot of challenges when applying it to the wireless and mobile networks. The interworking problems of RSVP and mobility management protocols have been extensively discussed over the last decade. As the solutions of this problem, mobility-aware RSVP schemes that integrate RSVP and micro-mobility management are becoming more and more popular. Therefore, the investigation on how much they improve the performance of the basic RSVP is necessary and useful. Instead of the traditional simulation based approaches, in this paper we introduce a formal performance evaluation formalism, named Performance Evaluation Process Algebra (PEPA), and employ it to investigate the performance of the basic RSVP and mobility-aware RSVP. Important performance metrics such as handover blocking probability and signalling cost are presented.
14899060
Automatic model-based service hosting environment migration
The proper operation of Service-Oriented Architecture (SOA) depends on underlying system services of operating systems, so efficient and effective migration of Service Hosting Environment is critical to cope with intrinsic-changed nature of SOA. However, due to the large amount of configuration items, complicated mapping and complex dependency relationship among system services, migrating into a new Service Hosting Environment satisfying the operation requirement of SOA becomes an error-prone and time-consuming task. The SCM project in IBM develops a novel approach to migrate Service Hosting Environment shaped in Unix-like systems. Firstly, this approach builds a set of configuration models to describe various system services. Then based on models, it presents knowledge based mapping to translate system service configurations between Service Hosting Environments. Finally, it designs a dependency hierarchy deducting algorithm to compute the dependency relationship among system services for migration traceability and error determination. A SCM prototype has performed well on largely reducing time, labor and errors in real migration cases.
18424476
Proving theorems by pattern recognition I
Certain preliminary results on doing mathematics by machines (“mechanical mathematics”) were reported in an earlier paper [20]. The writer suggested developing inferential analysis as a branch of applied logic and as a sister discipline of numerical analysis. This analogy rests on the basic distinction of pure existence proofs, elegant procedures which in theory always terminate, and efficient procedures which are more complex to describe but can more feasibly be carried out in practice. In contrast with pure logic, the chief emphasis of inferential analysis is on the efficiency of algorithms, which is usually attained by paying a great deal more attention to the detailed structures of the problems and their solutions, to take advantage of possible systematic short cuts. The possibilities of much more elaborate calculations by machines provide an incentive to studying a group of rather minute questions which were formerly regarded as of small theoretical interest. When the range of actual human computation was narrow, there seemed little point in obtaining faster procedures which were still far beyond what was feasible. Furthermore, on account of the versatility of machines, it now appears that as more progress is made, strategies in the search for proofs, or what are often called heuristic methods, will also gradually become part of the subject matter of inferential analysis. An analogous situation in numerical analysis would be, for example, to make the machine choose to apply different tricks such as taking the Fourier transform to obtain a solution of some differential equation.