... properly cited. For commercial re-use, please contact [email protected] Abstract Open sets are central to mathematics, especially analysis and topology, in ways few notions are. In most, if not all, computational approaches to mathematics, open sets are only studied indirectly via their ‘codes...

... Press, Standard Journals Publication Model ( https://dbpia.nl.go.kr/pages/standard-publication-reuse-rights ) Abstract In this paper, I argue against the thesis that the meaning of ‘computability’ is logic-dependent. I do this from a category-theoretic perspective. Applying a method due...

...-tiling problem, we prove that its admissibility problem is undecidable. Products of two modal logics admissibility of inference rules domino-tiling problems computability For all , let : . An inference rule is admissible in a modal logic if the logic is closed with respect to applications...

... Publication Model ( https://dbpia.nl.go.kr/journals/pages/open_access/funder_policies/chorus/standard_publication_model ) Definition 2.1 For , a functional of type is called normal if it computes Kleene’s following S1–S9, and non-normal otherwise. We only make use...

...Iosif Petrakis As it is remarked in [ 1 , p. 3], computability theory has ‘still not received the level of categorical attention it deserves’. It seems though that the ‘categorical spirit’ of the notions of a computability model and a simulation between them is behind the remarkable success...

...Richard Krogman; Douglas Cenzer Theorem Let be a graph relational FST injection structure. Then there is an algorithm which decides whether in time exponential in . If is a unary structure, then is decidable in linear time. The above results let us compute isomorphisms...

...Wesley Calvert; Douglas Cenzer; Valentina Harizanov Downey, Jockusch, McNicholl and Schupp [ 5 ] classified the asymptotic densities of (limit computable) sets according to their levels in the Ershov hierarchy, i.e. according to the number of changes in their computable approximations...

...Uri Andrews; Steffen Lempp; Manat Mustafa; Noah D Schweber We lift the analysis of Andrews, Schweber, and Sorbi [ 3 ] of the first-order theory of the partial order of degrees of c.e. equivalence relations (ceers) to higher computability theory. Specifically, we work in the setting...

... degrees recursively enumerable sets symmetric difference computability theory recursion theory We generally take it for granted that combinatorial set operations and Turing complexity come from different universes and have no relationship to each other. For example, for any two Turing degrees...

... of all, we have shown in [ 29 ] that Pincherle’s theorem is closely related to (open-cover) compactness but has fundamentally different logical and computational properties. Indeed, Pincherle’s theorem, called in [ 29 ], satisfies the following properties; definitions can be found...

...Diogo Poças; Jeffery Zucker Abstract Analog computation attempts to capture any type of computation, that can be realized by any type of physical system or physical process, including but not limited to computation over continuous measurable quantities. A pioneering model is the General Purpose...

... propositional fragment of computability logic (the game-semantically conceived logic of computational problems introduced in [ 2 ]) and proved its soundness and completeness. The present article takes that result to the first-order level, with the so-called choice quantifiers. The resulting system...

... also show various separation results between space complexity classes for ITTMs. This considerably expands our earlier observations on the topic in Section 7.2.2 of Carl (2019, Ordinal Computability: An Introduction to Infinitary Machines), which appear here as Lemma up to Corollary...

... and distributed under the terms of the Oxford University Press, Standard Journals Publication Model ( https://dbpia.nl.go.kr/journals/pages/open_access/funder_policies/chorus/standard_publication_model ) Abstract Feedback computability is computation with an oracle that contains the correct convergence...

... is the computability of the problem of deciding the modal definability of first-order sentences with respect to classes of frames. It gives a new proof of Chagrova's Theorem telling that, with respect to the class of all frames, the problem of deciding the modal definability of first-order sentences is undecidable...

... of computability logic by G.Japaridze, who also showed that, through cirquent calculus, one can capture, refine and generalize independence-friendly (IF) logic. Specifically, the approach allows us to account for independence from propositional connectives in the same spirit as the traditional IF logic accounts...

...Douglas Cenzer; Valentina Harizanov; Jeffrey B. Remmel 22 4 2013 References [1] Ash C. Knight J. Computable Structures and the Hyperarithmetical Hierarchy 2000 Elsevier [2] Calvert W. Cenzer D. Harizanov V. Morozov A. Effective categoricity of equivalence...

...., Queens, NY 11367, USA; and CUNY Graduate Center, 365 Fifth Avenue, New York, NY 10016, USA. E-mail: [email protected] Abstract We continue recent work on computable structure theory in the setting of ω1. We prove...

...: [email protected] Abstract This two part article consists of a brief biography of Marian Boykan Pour-El followed by a summary of her mathematical achievements. Keywords: Computability in analysis and physics, mathematical logic, Pour-El. 1 Introduction In the not too distant past, girls...

... from the timelessness of the issues he tackled, and the innovative light he shed upon them. Turing first defined the algorithmic limits of computability, when determined via effective mechanism, and showed the generality of his definition by proving its equivalence...