10510054
Words in the History of a Turing Machine with a Fixed Input
The usual decision (halting or printing) problems for Turing machines (T.M.) are relative to an infinite class of them or an infinite class of inputs or1 a single T.M. We consider now a new type of problem (the consequence problem) con-neeted with a single input on a single T.M. It is known that in a definite sense everything which an erasing T.3{. can do can also be done by a nonerasing T.M., e.g., the halting problem is undeeidable in both bases. It turns out that for the consequence problem erasing does make an essential difference: decidable without erasing, but undecidable Mth erasing. From the undeeidability of the consequence problem for a T.M., it also follows that the same problem is undeeidable for certain simple monogenie normal systems. Consider a fixed finite alphabet A including a symbol b for the blank squares on a tape. For definiteness, we may assume that A = {b, ,, a}. Assume some familiar formulation of Turing machines. Definition. The word at any moment t in the history of a T.M. is the string consisting of the contents of the squares in the minimum block on the tape at t that includes all the marked squares and the square scanned at the initial moment (the origin). THEOREM 1. For arty fixed (finite) word at the initial moment, we can find a T.M. such that the set of words in its subsequent history is not ~cursive. Ullian shows [1] that there exists some nonrecursive but recursively enumerable set S such that there is a general recursive function f such that S = {f(0), f(f(O)), f(f(f(O))),-.. }. We can now give a T.M. which first erases the finitely many marks on the initial tape and returns to the origin, then it puts down the representation of 0 on tape, calculates the value of f(0), erasing everything else except the representation of f(0), calculates f2(0). In particular, we can do it in such a way that the symbol a is used, after the initial tape content is erased, only to mark f(0), f2(0), etc; it is erased before we evaluate f(f (0)) from f(0). Moreover, the string of a followed by the representation of f(0) always begins at the origin. Clearly the set of words in the history of this T.M. cannot be recursive because otherwise the set S would be recursive, whether a 'gd(0) ' belongs to the …
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.
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.
21405683
Set-Theoretical Basis for Real Numbers
twenty axioms used by Tarski which are sufficient for the arithmetic of real numbers and are to the effect that real numbers form a complete ordered field.2 Indeed, we cannot prove in L all Tarski's twenty axioms in their full generality. One of them, stating in effect that every bounded class of real numbers possesses a least upper bound, can only be proved as a metatheorem which states that every bounded nameable class of real numbers possesses a least upper bound. However, all the other nineteen axioms can be proved in L without any modification. This result may be of some interest because the axioms of L are considerably weaker than those commonly employed for the same purpose. In L variables need to take as values only classes each of whose members has no more than two members. In other words, only classes each with no more than two members are to be elements. On the other hand, it is usual to assume for the purpose of natural arithmetic that all finite classes are elements, and, for the purpose of real arithmetic, that all enumerable classes are elements. 2. The system L. In developing L, elementary logic (viz., the theory of truth functions and quantifiers) is assumed from the beginning. The single additional primitive is the two place predicate e with which we can generate formulas of L from variables and logical operators in the usual manner. The usual definitions (e.g., D9-D35 of [21) of the theory of classes and relations are assumed. In particular, let tx denote the unit class of x, x u y denote the sum class of x and y, and V denote the class of all elements. The axioms of L are given by the following three statements: Mi. tx U by f V. M2. x = y D . x e z D y e z. M3. If q is any formula of L in which y is not free, then . (3y)(x)(x e yW
38679232
Short Definitions of the Ordinals
In this paper, a simple inductive characterization of the ordinal numbers is stated and developed. The characterization forms the basis for a set of axioms for ordinal theory and also for several short explicit definitions of the ordinals. The axioms are shown to be sufficient for ordinal theory, and, subject to suitable existence assumptions, each of the definitions is shown to imply the axioms. The present results apply to the familiar von Neumann version of the ordinals, but the methods used are easily adapted to other versions. ? 1. Axioms for ordinal theory. According to the usual interpretation, each ordinal is the set of all lesser ordinals. Thus zero is the empty set A, a successor ordinal x' is x U {x} for some ordinal x, and a limit ordinal is a set w of ordinals that is equal to its own sum set Zw. In fact, the class On of all ordinals might be characterized informally as the smallest class Z such that (1) AEZ, (2) (y) (yEZ D y'EZ), and (3) (w) (1w = w c Z D wEZ). More simply, On can be characterized as the smallest Z such that
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.
17656556
A Non-repudiable Protocol for Secure Messaging
As Oppliger stated, secure messaging refers to the ability to provide data confidentiality, data integrity, data origin authentication, and non-repudiation of origin services for email. It is very important but poorly developed and has very limited application. We propose an email protocol assures non-repudiability which means that if the email is successfully sent, the sender cannot deny she/he has actually sent the mail and the recipient cannot deny she/he has actually received it. The protocol uses an efficient RSA-based convertible signature.
17038094
On-line Algorithm for Server Selection of Video Streaming over P2P Networks
Abstract We consider a video streaming application over P2Pnetworks and introduce the P2P on-line server selection problem. This task is related to the classic K-server problem, known from the theory of online algorithms. The difference is that our problem has a dynamic cost matrix, due to network congestion which may trigger the rerouting of streaming paths. With the assumption that the number of hops of any alternative path from the server node p to the requesting node q is at most δ times the number of hops of the shortest path from p to q, our dynamic work function algorithm works for the P2P on-line server selection problem with competitive ratio δ×(2k-1). 1. Introduction In this paper we consider a video streaming application over P2Pnetworks. As we know, it isdifficult to provide large scale streaming service using traditional, centralized client-serverarchitecture, since a bottleneck occurs at the server. The network service model known as Peer-to-Peer (P2P) solves this problem, due to its distributed nature. We address the issue of optimizing the server selection for video streaming in P2P networks.Optimization tasks are classified into online and offline problems. Optimization problems in which the input is received piece by piece and the corresponding piece of output must be produced before knowing the entire input are called online problems. In some optimization tasks, such as job scheduling, both the online and offline versions of the problem are meaningful. Many other situations, such as telephone circuit switching, investment planning etc. are intrinsically online. For these problems, offline algorithms are not acceptable. Competitive algorithms were introduced by Sleator and Tarjan [1] in the context of optimization problems. They sought a worst case complexity measure for on-line algorithms that have to make decisions based on current and previous parts of the input. In the on-line problem the input is given as a sequence σ = σ
6984424
Ontology-based security assessment for software products
This paper proposes an ontology-based approach to analyzing and assessing the security posture for software products. It provides measurements of trust for a software product based on its security requirements and evidence of assurance, which are retrieved from an ontology built for vulnerability management. Our approach differentiates with the previous work in the following aspects: (1) It is a holistic approach emphasizing that the system assurance cannot be determined or explained by its component assurance alone. Instead, the software system as a whole determines its assurance level. (2) Our approach is based on widely accepted standards such as CVSS, CVE, CWE, CPE, and CAPEC. Our ontology integrated these standards seamlessly thus provides a solid foundation for security assessment. (3) Automated tools have been built to support our approach, delivering the environmental scores for software products.
7625765
Solving QoS-driven Web service dynamic composition as fuzzy constraint satisfaction
The creation of value-added composite web service raises an opportunity to the formation of online B2B collaborations. However, web services are usually overlapping in functionality. How to make a choice based on non-functional factors becomes a problem that needs to be solved. In this paper, it argues that the selection of component services should be considered in a global manner and the user's QoS preferences is more appropriate to be expressed in a fuzzy way. It advocates using fuzzy set to express the user's QoS preference on a specific QoS criteria and using fuzzy expression to express the user's trade-off among QoS criteria's. The service selection problem is formalized as a fuzzy constraint satisfaction problem and deep-first branch-and-bound method is chosen to search for a solution with some adjustments to web service composition. It also develops an uncritical fuzzy consistency checking algorithm as an aid to faster search. Experiments are conducted to prove the effectiveness of the approach.
4407504
Optimal ISP subscription for Internet multihoming: algorithm design and implication analysis
Multihoming is a popular method used by large enterprises and stub ISPs to connect to the Internet to reduce cost and improve performance. Recently researchers have studied the potential benefits of multihoming and proposed protocols and algorithms to realize these benefits. They focus on how to dynamically select which ISPs to use for forwarding and receiving packets, and assume that the set of subscribed ISPs is given a priori. In practice, a user often has the freedom to choose which subset of ISPs among all available ISPs to subscribe to. We call the problem of how to choose the optimal set of ISPs the ISP subscription problem. In this paper, We design a dynamic programming algorithm to solve the ISP subscription problem optimally. We also design a more efficient algorithm for a large class of common pricing functions. Using real traffic traces and realistic pricing data, we show that our algorithm reduces users' cost. Next we study how ISPs respond to users' optimal ISP subscription by adjusting their pricing strategies. We call this problem the ISP pricing problem. Using a realistic charging model, we formulate the problem as a non-cooperative game. We first prove that if cost is the only criterion used by a user to determine which subset of ISPs to subscribe to, at any equilibrium all ISPs receive zero revenue. We then study a more practical formulation in which different ISPs provide different levels of reliability and users choose ISPs to both improve reliability and reduce cost. We analyze this problem and show that at any equilibrium an ISP's revenue is positive and determined by its reliability.