Conference Proceedings
The CIE2016 Conference proceedings are now avaible online. You can get access to the proceedings via SpringerLink.
Abstract Booklet
You may find the downloadable Abtstract Booklet here.
Contibuted Papers
Barnaby Martin, Christian Glaßer and Peter Jonsson.
Title: Circuit Satisfiability and Constraint Satisfaction around Skolem Arithmetic
Abstract: We study interactions between Skolem Arithmetic and certain classes of Circuit Satisfiability and Constraint Satisfaction Problems (CSPs). We revisit results of Glaßer et al. [23] in the context of CSPs and settle the major open question from that paper, finding a certain satisfiability problem on circuits—involving complement, intersection, union and multiplication—to be decidable. This we prove using the decidability of Skolem Arithmetic. Then we solve a second question left open in [23] by proving a tight upper bound for the similar circuit satisfiability problem involving just intersection, union and multiplication. We continue by studying first-order expansions of Skolem Arithmetic without constants, (N; ×), as CSPs. We find already here a rich landscape of problems with non-trivial instances that are in P as well as those that are NP-complete.
Anton Konovalov and Victor Selivanov.
Title: The Boolean Algebra of Piecewise Testable Languages
Abstract: We characterize up to isomorphism the Boolean algebra of regular piecewise- testable languages and show the decidability of classes of regular languages related to this characterization. This BA turns out to be isomorphic to several other natural BAs of regular languages, in particular to the BA of regular aperiodic languages.
Barnaby Martin, Andras Pongracz and Michal Wrona.
Title: The complexity of counting quantifiers on equality languages
Abstract: An equality language is a relational structure with infinite domain whose relations are first-order definable in equality. We classify the extensions of the quantified constraint satisfaction problem over equality languages in which the native existential and universal quantifiers are augmented by some subset of counting quantifiers. In doing this, we find ourselves in various worlds in which dichotomies or trichotomies subsist.
Russell Miller.
Title:Baire category theory and Hilbert's Tenth Problem inside Q
Abstract: For a ring R, Hilbert’s Tenth Problem HTP(R) is the set of polynomial equations over R, in several variables, with solutions in R. We consider computability of this set for subrings R of the rationals. Applying Baire category theory to these subrings, which naturally form a topological space, relates their sets HTP(R) to the set HTP(Q), whose decidability remains an open question. The main result is that, for an arbitrary set C, HTP(Q) computes C if and only if the subrings R for which HTP(R) computes C form a nonmeager class. Similar results hold for 1-reducibility, for admitting a Diophantine model of Z, and for existential definability of Z.
Riccardo Dondi and Florian Sikora.
Title: Parameterized Complexity and Approximation Issues for the Colorful Components Problems
Abstract: The quest for colorful components (connected components where each color is associated with at most one vertex) inside a vertex- colored graph has been widely considered in the last ten years. Here we consider two variants, Minimum Colorful Components (MCC) and Maximum Edges in transitive Closure (MEC), introduced in the context of orthology gene identification in bioinformatics. The input of both MCC and MEC is a vertex-colored graph. MCC asks for the removal of a subset of edges, so that the resulting graph is partitioned in the minimum number of colorful connected components; MEC asks for the removal of a subset of edges, so that the resulting graph is partitioned in colorful connected components and the number of edges in the transitive closure of such a graph is maximized. We study the parameterized and approximation complexity of MCC and MEC, for general and restricted instances.
Gemma Carotenuto and Andre Nies.
Title: Lightface $\Pi^0_3$-completeness of density sets under effective Wadge reducibility
Abstract: Let A ⊆ ω2 be measurable. The density set DA is the set of Z ∈ ω2 such that the local measure of A along Z tends to 1. Suppose that A is a Π10 set with empty interior and the uniform measure of A is a positive computable real. We show that DA is lightface Π30 complete for effective Wadge reductions. This is an algorithmic version of a result in descriptive set theory by Andretta and Camerlo [1]. They show a completeness result for boldface Π30 sets under plain Wadge reductions.
Olivier Bournez, Nachum Dershowitz and Pierre Neron.
Title: An Axiomatization of Analog Algorithms
Abstract: We propose a formalization of generic algorithms that includes analog algorithms. This is achieved by reformulating and extending the framework of abstract state machines to include continuous-time models of computation. We prove that every hybrid algorithm satisfying some reasonable postulates may be expressed precisely by a program in a simple and expressive language.
Oleg Kudinov and Victor Selivanov.
Title: On the Lattices of Effectively Open Sets
Abstract: We show that for many natural computable metric spaces and computable domains the first order theory of the lattice of effectively open sets is hereditarily undecidable. Moreover, for several important spaces (e.g., finite-dimensional Euclidean spaces and the domain P!) this theory is m-equivalent to the first-order arithmetic.
Iosif Petrakis.
Title: A direct constructive proof of a Stone-Weierstrass theorem for metric spaces
Abstract: We present a constructive proof of a Stone-Weierstrass theorem for totally bounded metric spaces (SWtbms) which implies Bishop’s Stone-Weierstrass theorem for compact metric spaces (BSWcms) found in [3]. Our proof has a clear computational content, in contrast to Bishop’s highly technical proof of BSWcms and his hard to motivate concept of a (Bishop-)separating set of uniformly continuous functions. All corollaries of BSWcms in [3] are proved directly by SWtbms. We work within Bishop’s informal system of constructive mathematics BISH.
Sebastián Barbieri and Mathieu Sablik.
Title: The domino problem for self-similar subsets of Z^d
Abstract: We define the domino problem for tilings over self-similar structures of Zd given by forbidden patterns. In this setting we exhibit non-trivial families of subsets with decidable and undecidable domino problem.
Bas Luttik and Fei Yang.
Title: On the Executability of Interactive Computation
Abstract: The model of interactive Turing machines (ITMs) has been proposed to characterise which stream translations are interactively computable; the model of reactive Turing machines (RTMs) has been proposed to characterise which behaviours are reactively executable. In this article we provide a comparison of the two models. We show, on the one hand, that the behaviour exhibited by ITMs is reactively executable, and, on the other hand, that the stream translations naturally associated with RTMs are interactively computable. We conclude from these results that the theory of reactive executability subsumes the theory of interactive computability. Inspired by the existing model of ITMs with advice, which provides a model of evolving computation, we also consider RTMs with advice and we establish that a facility of advice considerably upgrades the behavioural expressiveness of RTMs: every countable transition system can be simulated by some RTM with advice up to a fine notion of behavioural equivalence.
John Case and James Royer.
Title: Program Size Complexity of Correction Grammars in the Ershov Hierarchy
Abstract: A general correction grammar for a language L is a program
g that, for each (x,t) ∈ N2, issues a yes or no (where for t = 0, the
answer is no) which is g’s t-th approximation in answering “x∈L?”;
moreover, g’s sequence of approximations for a given x is required to
converge after finitely many mind-changes. The correction grammars
can be transfinitely stratified based on O, Kleene’s system of notation
for constructive ordinals: for u ∈ O, a u-correction grammar’s mind
changes have to fit a count-down process from ordinal notation u; these u-
correction grammars capture precisely the Σ−1 sets in Ershov’s hierarchy u
of sets for ∆02. Herein we study the relative succinctness between these classes of correction grammars; e.g., given u and v, transfinite elements of O with u H(iv). We also exhibit relative succinctness progressions in these systems of grammars and study the “information-theoretic” underpinnings of relative succinctness. Along the way, we verify a 1972 conjecture of Meyer and Bagchi.
Merlin Carl.
Title: Generalized Effective Reducibility
Abstract: We introduce two notions of effective reducibility for set-theoretical statements, based on computability with Ordinal Turing Machines (OTMs), one of which resembles Turing reducibility while the other is modelled after Weihrauch reducibility. We give sample applications by showing that certain (algebraic) constructions are not effective in the OTM-sense and considerung the effective equivalence of various versions of the axiom of choice.
Sanjay Jain, Bakhadyr Khoussainov and Frank Stephan.
Title: Finitely generated semiautomatic groups
Abstract: The present work shows that Cayley automatic groups are semiautomatic and exhibits some further constructions of semiautomatic groups and in particular shows that every finitely generated group of nilpotency class 3 is semiautomatic.
Rumen Dimitrov, Valentina Harizanov and Andrei Morozov.
Title: Automorphism Groups of Substructure Lattices of Vector Spaces in Computable Algebra
Abstract: The lattice of computably enumerable (c.e.) vector spaces and its automorphisms have been extensively studied. For a Turing degree x, we investigate the automorphisms of the lattice of x-c.e. spaces. We establish the equivalence of the embedding relation for these automorphism groups with the order relation on the corresponding Turing degrees. Following a proof by Guichard, we show that the automorphisms of x-c.e. vector spaces are induced by x-computable invertible semilinear transformations, GSLx. We prove that the Turing degree spectrum of the group GSLx is the upper cone of Turing degrees ≥ x′′.
Lorenzo Galeotti.
Title: A Candidate for the Generalised Real Line
Abstract: Let κ be an uncountable cardinal with κ<κ = κ. In this paper we introduce Rκ, a Cauchy-complete real closed field of cardinality 2κ. We will prove that Rκ shares many features with R which have a key role in real analysis and computable analysis. In particular, we will prove that the Intermediate Value Theorem holds for a non-trivial subclass of continuous functions over Rκ. We propose Rκ as a candidate for extending computable analysis to generalised Baire spaces.
Ludovic Patey.
Title: Partial Orders and Immunity in Reverse Mathematics
Abstract: We identify computability-theoretic properties enabling us to separate various statements about partial orders in reverse mathematics. We obtain simpler proofs of existing separations, and deduce new compound ones. This work is part of a larger program of unification of the separation proofs of various Ramsey-type theorems in reverse mathematics in order to obtain a better understanding of the combinatorics of Ramsey’s theorem and its consequences. We also answer a question of Murakami, Yamazaki and Yokoyama about pseudo Ramsey’s theorem for pairs.
Mikhail Andreev.
Title: Busy beavers and Kolmogorov complexity
Abstract: The idea to find the “maximal number that can be named” can be traced back to Archimedes (see his Psammit [1]). From the viewpoint of computation theory the natural question is “which number can be described by at most n bits”? This question led to the definition of the so-called “busy beaver” numbers (introduced by T. Rado). In this note we consider different versions of the busy beaver-like notions defined in terms of Kolmogorov complexity. We show that these versions differ depending on the version of complexity used (plain, prefix, or a priori complexities) and find out how these notions are related, providing matching lower and upper bounds.
Informal Presentations
Ivan Georgiev.
Title: One-point Extensions of Uniformly and Conditionally Computable Real Functions
Abstract: We consider two notions for relative computability of real functions. The first notion is uniform computability, which is a relativized version of a notion of Grzegorczyk from [1]. The second notion is conditional computability, which extends the uniform computability by allowing the approximation process to depend on an additional natural parameter. The elementary functions of calculus turn out to be conditionally computable with respect to a small subrecursive class of operators and also uniformly computable with respect to the same class of operators, when restricted to compact subsets of their domains. The aim of this talk is to show that under some natural assumptions, the uniform computability is preserved after one-point extensions. We also show by a counterexample that a similar result for the conditional computability does not hold.
Olivier Finkel.
Title: Independence Results in Automata Theory
Abstract: We prove many independence results in Automata Theory, showing that Incompleteness is a very general phenomenon for automata over infinite words, and even for automata over finite words.
For instance, we proved in [Fin15] that there exist some 1-counter Bu ̈chi automata An for which some elementary properties are independent from strong set theories like Tn =: ZFC + “There exist (at least) n inaccessible cardinals”, for integers n ≥ 1. We first prove that “L(An) is Borel”, “L(An) is arithmetical”, “L(An) is ω-regular”, “L(An) is deterministic”, and “L(An) is unambiguous” are equivalent to the consistency of the theory Tn. This implies that, if Tn is consistent, all these statements are provable from ZFC + “There exist (at least) n + 1 inaccessible cardinals” but not from ZFC + “There exist (at least) n inaccessible cardinals”. Notice that the same results can be proved for other large cardinals like hyperinaccessible or Mahlo cardinals.
Danko Ilik and Taus Brock-Nannestad.
Title: An Intuitionistic Formula Hierarchy Based on High-School Identities
Abstract: We revisit intuitionistic proof theory from the point of view of the formula isomorphisms arising from high-school identities.
We first show how any sequent calculus for intuitionistic proposition logic, and in particular the G4ip calculus of Vorob’ev, Hudelmaier, and Dyckhoff, can be represented as a complete proof calculus that nevertheless contains no invertible proof rules, called their high-school (HS) variant.
We then show that all the rules of G4ip and HS admit an arithmetical interpretation, namely each such proof rule can be reduced to an inequality between exponential polynomials.
Finally, we extend the exponential polynomial analogy to the first-order quantifiers, showing that it gives rise to a simple intuitionistic hierarchy of formulas, the first one that classifies formulas up to isomorphism, and proceeds along the same equivalences that lead to the classical arithmetical hierarchy.
Lars Kristiansen.
Title: Subrecursive Sum Approximations of Irrational Numbers
Abstract:
We consider various ways to represent irrational numbers by subrecursive functions: via Cauchy sequences, Dedekind cuts, trace functions, several variants of sum approximations and continued fractions. Let S be a class of subrecursive functions. The set of irrational numbers that can be obtained with functions from S depends on the representation. We compare the sets obtained by the different representations. In this talk we will focus on sum approximations.
A function C : N → Q is a Cauchy sequence for the real number α when |α−C(n)| < 1/2n. A function D : Q → {0,1} is a Dedekind cut of the real numberαwhenD(q)=0iffq<α.AfunctionT :Q→Qisatracefunctionfor the irrational number α when |α − q| > |α − T (q)|. An irrational number α can also be represented by a function f : N → Z where f(n) yields the nth element of the continued fraction [a0;a1,a2 ...] of α.
Anyirrationalnumberαcanbewrittenoftheformα=a+ 1 + 1 + 1 +... 2k0 2k1 2k2
where k0, k1, k2, . . . is a strictly monotone increasing sequence of natural numbers and a is an integer. Let A: N → N be a strictly monotone function. We will say that A is a sum approximation from below of the the real number α if there exists a ∈ Z such that α = a + ∞i=0 1/2A(i)+1. Any real number can also be written as a difference between an integer and an infinite sum, and we will say that A is a sum approximation from above of the the real number α if there exists a ∈ Z such that α = a − ∞i=0 1/2A(i)+1.
The sum approximations defined above are sum approximations in base 2. We will also consider general sum approximations (from above and below). A general sum approximations of α is a function that yields the sum approximation of α in any base.
Let PC , PD and P[ ] denote the sets of irrationals that are representable, receptively, by primitive recursive Cauchy sequences, primitive recursive Dedekind cuts and primitive recursive continued fractions. Specker [3] proved PD ⊂ PC, and Lehman [2] proved P[ ] ⊂ PD (strict inclusions). Let PT denote the sets of irrationals that are representable by primitive recursive Trace functions. It is proved in [1] that PT = P[]. We will present some theorems on how (general) sum approximation (from above and below) relate to the other representations. These theorems are extensions and refinements of theorems found in [1].
Benoit Monin.
Title: When error-correcting codes meet computability theory
Abstract:
Generic-case complexity is a subfield of computational complexity. It started with the observation that some problems that are difficult to solve in full are easy to solve on “most inputs”, namely on a set of inputs of asymptotic lower density 1. This notion was introduced by Kapovich, Myasnikov, Schupp and Shpilrain. They showed among other things that for a large class of finitely generated groups, the generic case complexity of the word problem is linear.
This notion has recently been extended by Jockusch and Schupp. The authors identified two notions that can be proved to be incomparable. The first is generic computability, where one must always give the right answer, without having to provide an answer for a small set of input. The second is coarse computability, for which one always have to provide an answer, with the right of being wrong on a small set of inputs. In both cases, a set of inputs is considered small if it is of asymptotic upper density 0.
Then Andrews, Cai, Diamondstone, Jockusch and Lempp assigned in “Asymptotic density, computable traceability and 1-randomness” a value gamma (with lower case ‘g’) to each set of natural numbers, which indicates how far the set is from being coarse-computable. They used this to assign a value Gamma (with upper case ‘G’) to each Turing degree, which indicates how far the degree is from being coarse-computable. They proved that the Gamma values of 0, 1/2 and 1 can be realized. They also proved that if a Turing degree has a Gamma value strictly larger than 1/2, then it is the computable degree and its Gamma value in fact equals 1. They asked whether a Turing degree can have a Gamma value strictly in between 0 and 1/2.
Using notions from computability theory, developped by Monin and Nies, together with some techniques from the field of error-correcting codes, we are able to give a negative answer to this question: The only Gamma values that can be realized by a Turing degrees are 0, 1/2 and 1.
Paul-Elliot Anglès D'Auriac and Benoît Monin.
Title: Higher Randomness and hK-trivials
Abstract: Computability gives us tools to define randomness on subsets of natural numbers. We consider a set random if it does not have any typical property, on a given class of properties given by computability theory.
Here, we focus on another notion of computability, which definitions are given by descriptive set theory, but that we can see as computation over ordinal time. These new definitions give rise to similar definitions of randomness, called Higher Randomness.
Some theorems on classical randomness have their counterpart on higher randomness, and some not. The fact that Weak-2-Randoms equals the ML⟨0′⟩ does not hold in the higher settings. We show that the sets which fix this fact, by continuous relativizations, are exactly the hK-trivials.
Sabrina Ouazzani.
Title: Gaps distribution in the infinite time Turing machines clockable ordinals
Abstract: Infinite time Turing machines (ITTM) are a computational model introduced in 2000 by Hamkins and Lewis in [HL00]. This model generalises the computation process of Turing machines to ordinal time: computation steps are indexed by ordinals. Configurations at successor steps are obtained in the classical way, while configurations at limit steps are obtained by specific operations (namely a lim sup on the cells and a rewind of the head which is put in a special lim state).
ITTM work on infinite binary strings. We can encode a countable ordinal on an infinite binary string by encoding a well-founded order of same order type on N. Therefore, inputs and outputs of ITTM can be (countable) ordinals.
Two notions appear naturally. An ordinal α is clockable if there exists an ITTM which halts on input “000...” in α steps of computation. It is writable if there exists an ITTM which outputs a code for α on input “000...” and halts. Welch has shown in [Wel09] that these two kinds of ordinals have the same supremum, called λ, which is a countable ordinal.
All ordinals below λ are writable. But there exist times at which no ITTM halt. Indeed, Hamkins and Lewis have shown in [HL00] that there are gaps in the clockable ordinals. The begining and the end of these gaps are limit ordinals. The goal of this work is to give a more precise description of their size distribution.
Welch proved that gaps begin by admissible ordinals. Moreover, λ can be caracterised in terms of admissibiliy [HL00]. In the same paper, the authors also proved that there are gaps of arbitrary large sizes. Another important result of the litterature is that the size of the first gap above any clockable ordinal is ω.
In this talk, we prove the existence of gaps with specific properties. In particular, we prove that for all writable limit ordinal α, there exist gaps of size exactly α (i.e. there are gaps of all “possible” size). We also prove that there exists an ordinal β such that β starts a gap of size β. We explicitely provide the ITTM algorithms which prove the existence of such gaps.
This is a joint work with Bruno Durand and Gregory Lafitte.
Kelsey Horan.
Title: Homomorphic Encryption Schemes
Abstract: In this talk I will present two methods of obtaining a Fully Homomorphic Encryption scheme. These methods deviate from the prior known bootstrapping method given by C Gentry in ”Fully homomorphic encryption using ideal lattices.” These schemes are relatively computationally efficient and conceptually simpler than previous schemes and rely on the General Learning with Errors assumption for security. The talk is based on a work by Z Brakerski, C Gentry, V Vaikuntanathan, ”(Leveled) fully homomorphic encryption without bootstrapping” as well as another work by C Gentry, A Sahai, B Waters, ”Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically faster, attribute-based”.
Paul Shafer.
Title: Honest elementary degrees without the cupping property
Abstract: An element a of a lattice cups to an elemen b>a if there is a c < b such that a ∪ c = b. An element of a lattice has the cupping property if it cups to every element above it. We study cupping in the lattice of honest elementary degrees, in which functions with elementary recursive graphs are compared via the ‘elementary recursive in’ relation. Kristiansen [2] showed that every sufficiently large honest elementary degree has the cupping property. This result prompted Kristiansen, Schlage-Puchta, and Weiermann [3] to ask if every non-zero honest elementary degree has the cupping property. We answer their question negatively by showing that if b is a sufficiently large honest elementary degree, then there is a non-zero honest elementary degree a < b that does not cup to b. We also compare cupping in the honest elementary degrees to recent work of Cai [1] on cupping in the degrees of relative provability.
1. Cai, M.: Higher unprovability (2015), preprint.
2. Kristiansen, L.: Subrecursive degrees and fragments of Peano arithmetic. Archive for Mathematical Logic 40(5), 365–397 (2001).
3. Kristiansen, L., Schlage-Puchta, J.C., Weiermann, A.: Streamlined subrecursive degree theory. Annals of Pure and Applied Logic 163(6), 698–716 (2012).
Mitko Yanchev.
Title: Rational Grading and Transitivity in Description Logics
Abstract: Counting (or grading with natural numbers) has been naturally extended to grading with rationals (and even with real coefficients) to enrich the expressive power of modal and description languages. We consider several different approaches known for realizing rational grading, and compare them in their expressivity and reasoning complexity. We focus on the rational grading realized independently from counting through the modal operators for rational grading and their analogues in Description Logics (DLs)—the concept constructors, called part restrictions [2], both capable of distinguishing a rational part of a set of successors. The presence of separate rational grading constructors in DLs proved beneficial. Together with the use of indices technique [2], designed for exploring the rational grading, they allow following a common way for obtaining decidability and complexity results as in less, so in more expressive languages with rational grading.
Next we look at the ways of embedding the notion of transitivity in DLs. These logics are widely used in knowledge-based systems, and the presence of transitive roles in a description language permits complex objects to be described by referring to their components without specifying a particular level of decomposition. Role hierarchies bring additional expressive power. In DL ALCQIHR+ [1], with both transitive roles and role hierarchies, the syntax is enriched also with inverse roles and the counting qualifying number restrictions. It is given a sound and complete decision procedure for that logic.
Now we consider DL ALCQPIHR+ , an extension of ALCQIHR+ with part restrictions, where the transitive roles are allowed only outside the qualifying number restrictions and part restrictions. We use the tableaux technique with pair-wise blocking combined with indices technique to prove that the reasoning in the extended logic is decidable. Disallowing the role hierarchies, what usually results in relaxing the reasoning complexity (with the trade-off in expressivity of the language), we obtain DL ALCQPIR+ , having only independent (transitive and non-transitive) roles. We give a PSPACE decision procedure for that logic.
Rose Weisshaar.
Title: Comparing Notions of Effective Genericity
Abstract: In recent work, Cholak, Dzhafarov, Hirst and Slaman showed that for n ≥ 3, every Mathias n-generic computes a Cohen n-generic. It is natural to wonder how other types of generic objects compare to one another. We consider generics for an effective version of a notion of forcing introduced by Slaman and Groszek in their proof that every set with a modulus has a uniform modulus. We call these generics domination generics (or D-generics). Adapting a method developed by Cholak, Dzhafarov, and Soskova, we show that for n ≥ 3, every Mathias n-generic computes a D-n-generic, and every D-n-generic computes a Mathias n-generic. Finally, we explore the (open) question of whether, for n ≥ 3, the Mathias n-generics and the D-n-generics occupy exactly the same Turing degrees.
Matthew Harrison-Trainor, Russell Miller and Antonio Montalban.
Title: Borel Functors and Interpretations
Abstract: Given an interpretation of a structure A in a structure B, we get a functor from copies of B to copies of A. If the interpretation uses only computable Σ10 formulas, then the functor will be computable; in general, the functor will be Borel. We show that there is actually a correspondence between functors and interpretations: each Borel functor arises from an interpretation (which may use infinitary formulas).
Similarly, an interpretation of A in B induces a continuous homomorphism from the automorphism group of B to that of A. The reversal is also true.
Rutger Kuyper.
Title: Connecting Weihrauch reducibility and intuitionistic reverse mathematics
Abstract: In this talk we will present a contribution to the recent interest in the intuitive similarity between reverse mathematics and Weihrauch reducibility. There are currently two main approaches to formalising this connection. The first of these proceeds by formalising Weihrauch reducibility within reverse mathematics, an approach which was pioneered by Dorais et al. and Dzhafarov.
The other approach is to connect Weihrauch reducibility to intuitionistic reverse mathematics, building on the long-standing intuition that there is a tight connection between intuitionistic logic and computability. One of the fields studying this connection goes under the name of realisability. Techniques from realisability have first been brought into the setting of reverse mathematics by Hirst and Mummert, whose work was continued by Dorais, and by Fujiwara, in their work on the reverse mathematical strength of sequential versions of theorems.
We present a precise connection between Weihrauch reducibility and provability in intuitionistic reverse mathematics, building on the work of the authors mentioned in the previous paragraph. Roughly speaking, we show that a Π21-statement α implies a second Π21-statement β over EL0, the intuitionistic version of RCA0, plus Markov’s principle, if and only if β Weihrauch-reduces to α. Of course, one quickly realises the theorem cannot be true as stated, but we give a precise way to state the theorem using the notion of composition in the Weihrauch degrees, and we also show that the statement just given holds if we restrict our intuitionistic calculus to an affine variant (i.e. a version which excludes some of the contraction rules in its sequent calculus).
Luca San Mauro.
Title: Complexity of Relations via Computable Reducibility
Computable reducibility provides a natural way of ranking binary relations on ω according to their complexity. Such reducibility is defined as follows: let R and S be two binary relations, we say that R is computably reducible to S iff there is a computable function f such that, for all x, y ∈ ω, the following holds:
xRy ⇔ f(x)Sf(y).
Computable reducibility has been object of study for decades, being mostly applied to the case of equivalence relations. In particular, a prominent problem in the area has been that of characterizing universal equivalence relations, i.e. relations to which all others relations, of a given complexity, can be computably reduced.
In this talk, we address the problem of universality for a more general context than that of equivalence relations. First, we prove that, contrary to the case of equivalence relations and preorders, for each level of the arithmetical hierarchy there is a universal binary relation. Then, we define natural examples of universal Σn0 binary relations and of universal Πn0 binary relations, obtained by fairly simple manipolations of the two most fundamental set-theoretic relations. More precisely, let Un∈ be the following Σn0 binary relation,
xU∈y ⇔ x ∈ W∅(n−1),
and, for n > 2, let Un⊆ be the following binary relation xU⊆y⇔W ⊆W(n−2).
. We show that:
1. For all n, Un∈ is a universal Σn0 binary relation;
2. For n > 2, Un⊆ is a universal Πn0 binary relation.
Edwin Beggs, Pedro Cortez, José Félix Costa and John Tucker.
Title: Classifying the computational power of stochastic physical oracles
Abstract: Consider an algorithm requesting information from an external source – an oracle – the terminology originates with Alan Turing [7]. Emil Post [6] used oracles to study computability.
However, suppose the external source is not a pure mathematical entity but a physical device or environment. Suppose the requests are for measurements of physical quantities. We call this external source a physical oracle. Algorithms with physical oracles may be found in measurement experiments, and in controlling machines. We ask: What is the computational power of adding a physical oracle? How does the computational theory depend upon the physical theories and models?
In [2,3] we developed a computability and complexity theory for physical oracles. The computational classification needed non-uniform complexity classes [1], especially P/log⋆ and BPP//log⋆ [5]. Using case studies, we formulated axioms expressing properties common to wide classes of physical systems [4].
Here we review physical oracles and report new results broadening their scope by using non-deterministic physical systems. Physical oracles with probabilistic theories we call stochastic physical oracles. We examine examples of three types of non-deterministic systems, those that that are physically nondeterministic, as in quantum phenomena; physically deterministic but whose physical theory is non-deterministic, as in statistical mechanics; and physically deterministic but whose computational theory is non-deterministic caused by error margins. We prove:
Theorem 1. Let SPO be the axioms for stochastic physical oracles. Let P be a physical system whose behaviour depends upon a physical quantity or parameter σ. Suppose P satisfies the axioms of SP O. Then: a set A ⊂ {0, 1}⋆ is decidable in polynomial time by a Turing machine with physical oracle P and unknown parameter σ if, and only if, A ∈ BPP // log⋆.
Rakhshan Harifi and Sama Goliaei.
Title: Nondeterministic Abstract Geometrical Computation Model
Abstract: A signal machine is an abstract geometrical model for computation, proposed as an extension to the one-dimensional cellular automata, in which discrete time and space of cellular automata is replaced with continuous time and space in signal machine. A signal machine is defined as a set of meta-signals and a set of rules. Computation in a signal machine starts from an initial configuration which is a set of signals and their initial positions. Signals are moving in space freely until a collision occurs. Rules of signal machine specify what happens after a collision, or in other words, specify out-coming signals for each set of colliding signals. Originally signal machine is defined by it’s deterministic rules as a deterministic machine.
In this paper, we introduce the concept of non-deterministic signal machine, which may contain more than one defined rule for a set of colliding signals. We define k-restricted nondeterministic signal machine (k-RNSM) as a nondeterministic signal machine which has at most two defined rules for each collision and accepts an input if an accept signal is produced in at most k collisions. We show that for each k-RNSM, there is an equivalent deterministic signal machine computing the same result, for any given initial configuration.
The idea of the proof is to produce all possible paths of nondeterministic computations in k-RNSM on the top of the fractal cloud [2], and test if one of them leads to an accept signal or not. Since for each k-RNSM there are at most k collisions before production of accept signal, and there are at most two alternative rules for each collision point, we have to check at most 2k paths of computation. First we produce 2k k-bit binary numbers using a beam of k signals and combinatorial comb structure [1], and generate a copy of the initial configuration in each branch of the comb. Then, we follow computation in each branch of the comb according to the corresponding binary number, where each bit of the binary number specifies the applicable rule in the corresponding collision.
Benjamin Rin and Benedikt Loewe.
Title: Computational Complexity on Ordinal Turing Machines
Abstract: In our talk, we shall explore the subject of computational complexity theory within the generalized setting of transfinite computability.
Previously, work in this area has focused on the infinite time Turing machine (ITTM) model of Hamkins and Lewis, which generalizes Turing machines to allow for transfinite computational run time. E.g., Schindler (2003) proved that P ̸= NP for such machines (a result later strengthened by Deolalikar, Hamkins, and Welch, 2005, to P \subsetneq NP ∩ co-NP). However, in finitary complexity theory, the time used by a computation, the length of the input, and the space used by a machine are natural numbers, i.e., measured on a comparable scale. This breaks down for ITTMs since the tape length is ω, but the computations in general take a transfinite amount of time. L ̈owe (2006) and Winter (2007, 2009) defined notions of space complexity for ITTMs in terms of the complexity rather than the length of the input.
The symmetry between time and space is restored in Koepke’s Ordinal Turing Machines (OTMs) which have both ordinal-length time and space. In this talk, we define notions of P, NP, PSPACE, and other complexity classes for OTMs, generalizing some definitions due to Winter (2007, 2009).
Thus we can say, e.g., that an OTM runs in polynomial time if there is an ordinal β such that for every input of length ν, the machine halts in fewer than νβ steps (where νβ denotes ordinal exponentiation). Based on this, we define the class of polynomial time decision problems as those that are decided by a polynomial time OTM, and likewise for OTM analogues of NP, polynomial space, exponential time and space, and other complexity classes.
We can now formulate ordinal versions of problems such as clique, subsetsum, traveling salesman, sat, 3-sat, and so on, and explore their properties with respect to the mentioned OTM complexity classes. Naturally, we may then consider whether classical results such the Cook-Levin theorem, the Baker- Gill-Solovay theorem, Ladner’s theorem, and others generalize to the transfinite setting. This talk will present definitions and initial results.
Anargyros Sarafopoulos.
Title: Is the Inverse Problem for Iterated Function Systems Undecidable?
Abstract: Iterated function systems (IFS) have been studied extensively and have many applications in image and signal compression as well as computer graphics; see for example Barnsley’s textbook [1]. Nevertheless the IFS inverse problem (as stated originally by Barnsley in [1]) remains open; there is no known algorithm to solve the inverse IFS problem optimally or decide whether exact solutions exists.
We define the optimal inverse IFS problem using notation and ideas from Computable Analysis [2]. It is worth noting that an optimal IFS I in this context is very different from the optimal encoding of IFS I using a Turing Machine (TM) or other equivalent computer programs or functions. This is because IFS are not equivalent to computer programs; an IFS can’t simulate a Turing Machine (TM). The problem of minimum length IFS codes is therefore different to the general minimum description length problem of equivalent TMs which is known to be undecidable.
Although IFS are not computer programs we still believe that the optimal inverse problem for IFS can be shown to be undicatable using a reduction to the halting problem or the equivalent notion of the halting problem in Computable Analysis, which is; non continuous functions are not computable, or there is no computable function which can compare two real values for equality.
Richard Moot and Christian Retoré.
Title: Natural language semantics and computability
Abstract:
We present an overview of known results about the computability of natural language semantics. We do no discuss new models or new results in the formal semantics of natural language, but rather analyse, from the point of view of computability and computational complexity, the logical models and algorithms currently used in natural language semantics.
We are interested, following [1], in formal semantics as a mapping from a natural language sentence to a (set of) logical formulas corresponding to its meanings (there can be multiple formulas because a natural language statement can be ambiguous). Such computational systems of formal semantics are useful as components for many tasks requiring natural language understanding, such as question-answering and automated translation. We argue that as long as possible world semantics is left out, one can compute the semantic representation(s) of a given statement, including aspects of lexical meaning. We also discuss the known results about the algorithmic complexity of the processes involved. In the context of categorial grammar in the logical tradition — such as the Lambek calculus and related systems — this involves studying 1) the complexity of parsing/theorem proving for such systems and 2) the complexity of computing the meaning given such a parse/proof. More details can be found in the report [2].
