The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
J. Raymundo Marcial–Romero and M. H. Escardó described a functional programming language with an abstract data type Real for the real numbers and a non-deterministic operator . We show that this language is universal at first order, as conjectured by these authors: all computable, first-order total functions on the real numbers are definable. To be precise, we show that each computable function...
The problem of whether a certain set of number-theoretic functions – defined via tetration (i.e. iterated exponentiation) – is well-ordered by the majorisation relation, was posed by Skolem in 1956. We prove here that indeed it is a computable well-order, and give a lower boundτ0 on its ordinal.
Recent developments in computability theory have given rise to new tools, among them the ibT and cl reducibilities, which, applications aside, are somewhat mysterious and deserve to be studied per se. This paper aims to throw some light on the little-explored degree structures induced by these new reducibilities.
Let Γ be a (not necessarily finite) structure with a finite relational signature. We prove that deciding whether a given existential positive sentence holds in Γ is in LOGSPACE or complete for the class CSP(Γ)NP under deterministic polynomial-time many-one reductions. Here, CSP(Γ)NP is the class of problems that can be reduced to the constraint satisfaction problem of Γ under non-deterministic polynomial-time...
We present a technique to associate to stochastic programs written in stochastic Concurrent Constraint Programming a semantics in terms of a lattice of hybrid automata. The aim of this construction is to provide a framework to approximate the stochastic behavior by a mixed discrete/continuous dynamics with a variable degree of discreteness.
We prove various results on effective numberings and Friedberg numberings of families related to algorithmic randomness. The family of all Martin-Löf random left-computably enumerable reals has a Friedberg numbering, as does the family of all classes of positive measure. On the other hand, the classes contained in the Martin-Löf random reals do not even have an effective...
The Grätzer-Schmidt theorem of lattice theory states that each algebraic lattice is isomorphic to the congruence lattice of an algebra. A lattice is algebraic if it is complete and generated by its compact elements. We show that the set of indices of computable lattices that are complete is -complete; the set of indices of computable lattices that are algebraic is -complete;...
This paper develops my (forthcoming) criticisms of the philosophical significance of a certain sort of infinitary computational process, a hyperloop. I start by considering whether hyperloops suggest that “effectively computable” is vague (in some sense). I then consider and criticise two arguments by Hogarth, who maintains that hyperloops undermine the very idea of effective computability. I conclude...
We survey recent results on combinatorial optimization problems in which the objective function is the entropy of a discrete distribution. These include the minimum entropy set cover, minimum entropy orientation, and minimum entropy coloring problems.
Intuitively, a recursion theorem asserts the existence of self-referential programs. Two well-known recursion theorems are Kleene’s Recursion Theorem (krt) and Rogers’ Fixpoint Recursion Theorem (fprt). Does one of these two theorems better capture the notion of program self-reference than the other? In the context of the partial computable functions over the natural numbers ( ), fprt is strictly...
We study computability theoretic properties of and equivalence structures and how they differ from computable equivalence structures or equivalence structures that belong to the Ershov difference hierarchy. Our investigation includes the complexity of isomorphisms between equivalence structures and between equivalence structures.
The notion of immune sets is extended to closed sets and classes in particular. We construct a class with no computable member which is not immune. We show that for any computably inseparable sets A and B, the class S(A,B) of separating sets for A and B is immune. We show that every perfect thin class is immune. We define the stronger notion of prompt immunity...
We first present a method to rule out the existence of strong polynomial kernelizations of parameterized problems under the hypothesis P NP. This method is applicable, for example, to the problem Sat parameterized by the number of variables of the input formula. Then we obtain improvements of related results in [1,6] by refining the central lemma of their proof method, a lemma due to Fortnow...
In this document I will outline a couple of recent developments, due to Joel Hamkins, Philip Welch and myself, in the theory of infinite-time Turing machines. These results were obtained with the idea of extending the scope of the study of Borel equivalence relations, an area of descriptive set theory. I will introduce the most basic aspects of Borel equivalence relations, and show how infinite-time...
We introduce the parameter cutwidth for the Cutting Planes (CP) system of Gomory and Chvátal. We provide linear lower bounds on cutwidth for two simple polytopes. Considering CP as a propositional refutation system, one can see that the cutwidth of a CNF contradiction F is always bound above by the Resolution width of F. We provide an example proving that the converse fails: there is an F which has...
The members of Martin-Löf random closed sets under a distribution studied by Barmpalias et al. are exactly the infinite paths through Martin-Löf random Galton-Watson trees with survival parameter . To be such a member, a sufficient condition is to have effective Hausdorff dimension strictly greater than , and a necessary condition is to have effective...
Coecke and Duncan recently introduced a categorical formalisation of the interaction of complementary quantum observables. In this paper we use their diagrammatic language to study graph states, a computationally interesting class of quantum states. We give a graphical proof of the fixpoint property of graph states. We then introduce a new equation, for the Euler decomposition of the Hadamard gate,...
We investigate the computing power of stateless multi-counter machines with reversal-bounded counters. Such a machine has m-counters and it operates on a one-way input delimited by left and right end markers. The move of the machine depends only on the symbol under the input head and the signs of the counters (zero or positive). At each step, every counter can be incremented by 1, decremented by 1...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.