The synthesis problem asks to automatically generate, if it exists, an algorithm from a specification of correct input-output pairs. In this paper, we consider the synthesis of computable functions of infinite words, ...
详细信息
The synthesis problem asks to automatically generate, if it exists, an algorithm from a specification of correct input-output pairs. In this paper, we consider the synthesis of computable functions of infinite words, for a classical Turing computability notion over infinite inputs. We consider specifications which are rational relations of infinite words, i.e., specifications defined by non-deterministic parity transducers. We prove that the synthesis problem of computable functions from rational specifications is undecidable. We provide an incomplete but sound reduction to some parity game, such that if Eve wins the game, then the rational specification is realizable by a computable function. We prove that this function is even computable by a deterministic two-way transducer. We provide a sufficient condition under which the latter game reduction is complete. This entails the decidability of the synthesis problem of computable functions, which we proved to be EXPTIME-complete, for a large subclass of rational specifications, namely deterministic rational specifications. This subclass contains the class of automatic relations over infinite words, a yardstick in reactive synthesis.
Formally defining how outputs of nondeterministic computations may be combined, we propose a nondeterministic Turing machine variant to compute functions. First, we describe our inspiration, the association of a compu...
详细信息
Formally defining how outputs of nondeterministic computations may be combined, we propose a nondeterministic Turing machine variant to compute functions. First, we describe our inspiration, the association of a computation tree with the divide and conquer strategy. Next, we define the variant and prove its equivalence with the deterministic Turing machine model. Then, we give some examples and relate the variant to alternating, counting and metric Turing machines. After, we define the variant's time complexity classes and compare them to deterministic space, giving a new characterization of the PSPACE and EXPSPACE classes. Finally, we outline future work. (C) 2021 Elsevier B.V. All rights reserved.
We discuss various ways of representing natural numbers in computations. We are primarily concerned with their computational properties, i.e. which functions each of these representations allows us to compute. We show...
详细信息
ISBN:
(纸本)9783030229962;9783030229955
We discuss various ways of representing natural numbers in computations. We are primarily concerned with their computational properties, i.e. which functions each of these representations allows us to compute. We show that basic functions, such as successor, addition, multiplication and exponentiation are largely computationally independent from each other, which means that in most cases computability of one of them in a certain representation does not imply that others will be computable in it as well. We also examine what difference can be made if we restrict our attention only to those representations in which it is decidable whether two numerals represent the same number. It turns out that the impact of such restriction is huge and that it allows us to rule out representations with certain unusual properties.
Two of the central concepts for the study of degree structures in computability theory are computably enumerable degrees and minimal degrees. For strong notions of reducibility, such as \(m\)-deducibility or truth tab...
详细信息
ISBN:
(数字)9781470461379
ISBN:
(纸本)9781470441623
Two of the central concepts for the study of degree structures in computability theory are computably enumerable degrees and minimal degrees. For strong notions of reducibility, such as \(m\)-deducibility or truth table reducibility, it is possible for computably enumerable degrees to be minimal. For weaker notions of reducibility, such as weak truth table reducibility or Turing reducibility, it is not possible to combine these properties in a single degree. We consider how minimal weak truth table degrees interact with computably enumerable Turing degrees and obtain three main results. First, there are sets with minimal weak truth table degree which bound noncomputable computably enumerable sets under Turing reducibility. Second, no set with computable enumerable Turing degree can have minimal weak truth table degree. Third, no \(\Delta^0_2\) set which Turing bounds a promptly simple set can have minimal weak truth table degree.
I develop a theory of counterfactuals about relative computability, i.e. counterfactuals such as If the validity problem were algorithmically decidable, then the halting problem would also be algorithmically decidable...
详细信息
I develop a theory of counterfactuals about relative computability, i.e. counterfactuals such as If the validity problem were algorithmically decidable, then the halting problem would also be algorithmically decidable, which is true, and If the validity problem were algorithmically decidable, then arithmetical truth would also be algorithmically decidable, which is false. These counterfactuals are counterpossibles, i.e. they have metaphysically impossible antecedents. They thus pose a challenge to the orthodoxy about counterfactuals, which would treat them as uniformly true. What's more, I argue that these counterpossibles don't just appear in the periphery of relative computability theory but instead they play an ineliminable role in the development of the theory. Finally, I present and discuss a model theory for these counterfactuals that is a straightforward extension of the familiar comparative similarity models.
The purpose of this paper is to consider the question of how we can represent numbers (especially natural numbers) and how our choice of a representation affects our ability to compute various functions. In particular...
详细信息
The purpose of this paper is to consider the question of how we can represent numbers (especially natural numbers) and how our choice of a representation affects our ability to compute various functions. In particular, we show the importance of computability of the characteristic function of identity in a representation of numbers. It turns out that it is a very strong assumption that significantly increases the scope of our knowledge about a given representation, including our ability to tell which functions are computable in this representation.
This paper focuses on optimizing probabilities of events of interest defined over general controlled discrete-time Markov processes. It is shown that the optimization over a wide class of omega-regular properties can ...
详细信息
This paper focuses on optimizing probabilities of events of interest defined over general controlled discrete-time Markov processes. It is shown that the optimization over a wide class of omega-regular properties can be reduced to the solution of one of two fundamental problems: reachability and repeated reachability. We provide a comprehensive study of the former problem and an initial characterization of the (much more involved) latter problem. A case study elucidates concepts and techniques. (C) 2016 Elsevier Inc. All rights reserved.
Since 1970, reversible finite automata have generated interest among researcher;but till now, we have not come across a model of reversible read only one-way finite automata which accept all regular languages, In this...
详细信息
Since 1970, reversible finite automata have generated interest among researcher;but till now, we have not come across a model of reversible read only one-way finite automata which accept all regular languages, In this paper, we introduce a new model of one-way reversible finite automata inspired by the Watson-Crick complementarity relation and show that our model can accept all regular languages. We further show that our model accepts a language which is not accepted by any multi-head deterministic finite automaton.
We answer a question posed by Hirschfeldt and Jockusch by showing that whenever k > l, Ramsey's theorem for singletons and k-colorings, RTkl, is not strongly computably reducible to the stable Ramsey's theo...
详细信息
We answer a question posed by Hirschfeldt and Jockusch by showing that whenever k > l, Ramsey's theorem for singletons and k-colorings, RTkl, is not strongly computably reducible to the stable Ramsey's theorem for l-colorings, SRTl2. Our proof actually establishes the following considerably stronger fact: given k > l there is a coloring, c : omega -> k such that for every stable coloring d : [omega]2 -> l (computable from c or not), there is an infinite homogeneous set H for d that computes no infinite homogeneous set for c. This also answers a separate question of Dzhafarov, as it follows that the cohesive principle, COH, is not strongly computably reducible to the stable Ramsey's theorem for all colorings, SRT
暂无评论