搜索结果：Computable

In this article we call a sequence $(a_n)_n$ of elements of a metric space nearly computably Cauchy if for every strictly increasing computable function $r:\mathbb{N}\to\mathbb{N}$ the sequence $(d(a_{r(n+1)},a_{r(n)}))_n$ converges computably to $0$. We show that there exists a strictly increasing sequence of rational numbers that is nearly computably Cauchy and unbounded. Then we call a real number $α$ nearly computable if there exists a computable sequence $(a_n)_n$ of rational numbers that converges to $α$ and is nearly computably Cauchy. It is clear that every computable real number is nearly computable, and it follows from a result by Downey and LaForte (2002) that there exists a nearly computable and left-computable number that is not computable. We observe that the set of nearly computable real numbers is a real closed field and closed under computable real functions with open domain, but not closed under arbitrary computable real functions. Among other things we strengthen results by Hoyrup (2017) and by Stephan and Wu (2005) by showing that any nearly computable real number that is not computable is weakly $1$-generic (and, therefore, hyperimmune and not Martin-Löf random

We propose a definition of computable manifold by introducing computability as a structure that we impose to a given topological manifold, just in the same way as differentiability or piecewise linearity are defined for smooth and PL manifolds respectively. Using the framework of computable topology and Type-2 theory of effectivity, we develop computable versions of all the basic concepts needed to define manifolds, like computable atlases and (computably) compatible computable atlases. We prove that given a computable atlas $Φ$ defined on a set $M$, we can construct a computable topological space $(M, τ_Φ, β_Φ, ν_Φ)$, where $τ_Φ$ is the topology on $M$ induced by $Φ$ and that the equivalence class of this computable space characterizes the computable structure determined by $Φ$. The concept of computable submanifold is also investigated. We show that any compact computable manifold which satisfies a computable version of the $T_2$-separation axiom, can be embedded as a computable submanifold of some euclidean space $\mathbb{R}^{q}$, with a computable embedding, where $\mathbb{R}^{q}$ is equipped with its usual topology and some canonical computable encoding of all open rational ba

We investigate different notions of "computable topological base" for represented spaces. We show that several non-equivalent notions of bases become equivalent when we consider computably enumerable bases. This indicates the existence of a robust notion of computably second countable represented space. These spaces are precisely those introduced by Grubba and Weihrauch under the name "computable topological spaces". The present work thus clarifies the articulation between Schröder's approach to computable topology based on the Sierpinski representation and other approaches based on notions of computable bases. These other approaches turn out to be compatible with the Sierpinski representation approach, but also strictly less general. We revisit Schröder's Effective Metrization Theorem, by showing that it characterizes those represented spaces that embed into computable metric spaces: those are the computably second countable strongly computably regular represented spaces. Finally, we study different forms of open choice problems. We show that having a computable open choice is equivalent to being computably separable, but that the "non-total open choice problem", i.e., open choice

Computational problems are classified into computable and uncomputable problems. If there exists an effective procedure (algorithm) to compute a problem then the problem is computable otherwise it is uncomputable. Turing machines can execute any algorithm therefore every computable problem is Turing computable. Cardinality of Turing machines and computable problems is equal-both are countably infinite. In this paper we introduce new type of problems by constructing a transform technique and applying it on some computable problems. The transformed problems can be computable of uncomputable.

We investigate conditions under which a co-computably enumerable closed set in a computable metric space is computable and prove that in each locally computable computable metric space each co-computably enumerable compact manifold with computable boundary is computable. In fact, we examine the notion of a semi-computable compact set and we prove a more general result: in any computable metric space each semi-computable compact manifold with computable boundary is computable. In particular, each semi-computable compact (boundaryless) manifold is computable.

We show that the continuous functional calculus is computable. As consequences we obtain the computable compactness of the spectrum of any computable normal element of a computably presented $\mathrm{C}^*$-algebra, the existence of effective approximate units for computably presented $\mathrm{C}^*$-algebras, and an effective version of the Spectral Theorem for compact operators on separable Hilbert spaces.

In computable analysis typically topological spaces with countable bases are considered. The Theorem of Kreitz-Weihrauch implies that the subbase representation of a second-countable $T_0$ space is admissible with respect to the topology that the subbase generates. We consider generalizations of this setting to bases that are representable, but not necessarily countable. We introduce the notions of a computable presubbase and a computable prebase. We prove a generalization of the Theorem of Kreitz-Weihrauch for the presubbase representation that shows that any such representation is admissible with respect to the topology generated by compact intersections of the presubbase elements. For computable prebases we obtain representations that are admissible with respect to the topology that they generate. These concepts provide a natural way to investigate many topological spaces that have been studied in computable analysis. The benefit of this approach is that topologies can be described by their usual subbases and standard constructions for such subbases can be applied. Finally we discuss a Galois connection between presubbases and representations of $T_0$ spaces that indicates that

We study notions of generic and coarse computability in the context of computable structure theory. Our notions are stratified by the $Σ_β$ hierarchy. We focus on linear orderings. We show that at the $Σ_1$ level all linear orderings have both generically and coarsely computable copies. This behavior changes abruptly at higher levels; we show that at the $Σ_{α+2}$ level for any $α\inω_1^{ck}$ the set of linear orderings with generically or coarsely computable copies is $\mathbfΣ_1^1$-complete and therefore maximally complicated. This development is new even in the general analysis of generic and coarse computability of countable structures. In the process of proving these results we introduce new tools for understanding generically and coarsely computable structures. We are able to give a purely structural statement that is equivalent to having a generically computable copy and show that every relational structure with only finitely many relations has coarsely and generically computable copies at the lowest level of the hierarchy.

In large-scale AI systems, allocating scarce resources such as GPU compute time and bandwidth among multiple agents is a critical challenge. Conventional policies focus on efficiency metrics, potentially leading to dominance concentration that undermines system diversity and stability. We propose Computable Fair Division (CFD), a framework that reinterprets the Boltzmann-Softmax function not as a selection tool but as a probabilistic resource allocation mechanism, redefining the inverse temperature parameter $β$ as a computable control variable governing the efficiency-fairness balance. Static analysis reveals a Pareto frontier with a near-optimal Stability Corridor where total loss remains approximately constant across policy weights. In the dynamic setting, AHC++ (Adaptive Hard-Cap Controller++) updates $β$ in real time using the error between observed dominance and a policy-specified target as feedback. Simulations show that AHC++ suppresses extreme dominance concentration under exogenous shocks while tracking fairness targets without substantial throughput degradation. Scalability analysis confirms that a 100x increase in agents yields only approximately 5.5x increase in execut

A real number is called left-computable if there exists a computable increasing sequence of rational numbers converging to it. In this article we are investigating a proper subset of the left-computable numbers. We say that a real number $x$ is reordered computable if there exist a computable function $f \colon \mathbb{N} \to \mathbb{N}$ with $\sum_{k=0}^{\infty} 2^{-f(k)} = x$ and a bijective function $σ\colon \mathbb{N} \to \mathbb{N}$ such that the rearranged series $\sum_{k=0}^{\infty} 2^{-f(σ(k))}$ converges computably. In this article we will give some examples and counterexamples for reordered computable numbers and we will show that these numbers are closed under addition, multiplication and the Solovay reduction. Finally, we will also present a density theorem for reordered computable numbers.

We initiate the effective metric structure theory of Keisler randomizations. We show that a classical countable structure $\mathcal{M}$ has a decidable presentation if and only if its Borel randomization $\mathcal{M}^{[0,1)}$ has a computable presentation for which the constant functions are uniformly computable points. We determine a sufficient condition for which the uniform computability of the constant functions can be dropped. We show that when $\mathcal{M}$ is effectively $ω$-categorical, then $\mathcal{M}^{[0,1)}$ is computably categorical, that is, has a unique computable presentation up to computable isomorphism. A special case of this result is that the unique separable atomless probability algebra is computably categorical. Finally, we show that all randomizations admit effective quantifier elimination.

We study computable topological spaces and semicomputable and computable sets in these spaces. In particular, we investigate conditions under which semicomputable sets are computable. We prove that a semicomputable compact manifold $M$ is computable if its boundary $\partial M$ is computable. We also show how this result combined with certain construction which compactifies a semicomputable set leads to the conclusion that some noncompact semicomputable manifolds in computable metric spaces are computable.

A compact set has computable type if any homeomorphic copy of the set which is semicomputable is actually computable. Miller proved that finite-dimensional spheres have computable type, Iljazović and other authors established the property for many other sets, such as manifolds. In this article we propose a theoretical study of the notion of computable type, in order to improve our general understanding of this notion and to provide tools to prove or disprove this property. We first show that the definitions of computable type that were distinguished in the literature, involving metric spaces and Hausdorff spaces respectively, are actually equivalent. We argue that the stronger, relativized version of computable type, is better behaved and prone to topological analysis. We obtain characterizations of strong computable type, related to the descriptive complexity of topological invariants, as well as purely topological criteria. We study two families of topological invariants of low descriptive complexity, expressing the extensibility and the null-homotopy of continuous functions. We apply the theory to revisit previous results and obtain new ones.

The Ordinal Folding Index (OFI) is a new, fully computable yard-stick that measures how many rounds of self-reference a statement, protocol or position must unfold before its truth or outcome stabilises. By turning this abstract 'fold-back' depth into a single ordinal number, OFI forges a direct link between areas that are usually studied in isolation: the closure stages of fixed-point logics, the time-to-win values of infinite parity games, and the ordinal progressions that calibrate the strength of formal theories. We prove that OFI refines all classical game-theoretic and logical metrics while remaining algorithmically enumerable, supply a polynomial-time approximation scheme on finite arenas, and show how the index coincides exactly with the length of the shortest winning strategy in the associated evaluation game. Alongside the theory we outline five open problems from the completeness of the computable-ordinal spectrum to the possibility of 'compressing' deep self-reference that chart a research programme at the intersection of computer-aided logic, algorithmic game theory and ordinal analysis. OFI thus invites game theorists and logicians alike to view infinite play, transfi

We establish a computable version of Gelfand Duality. Under this computable duality, computably compact presentations of metrizable spaces uniformly effectively correspond to computable presentations of unital commutative $C^*$ algebras.

This paper tackles practical challenges in governing child centered artificial intelligence: policy texts state principles and requirements but often lack reproducible evidence anchors, explicit causal pathways, executable governance toolchains, and computable audit metrics. We propose Graph-GAP, a methodology that decomposes requirements from authoritative policy texts into a four layer graph of evidence, mechanism, governance, and indicator, and that computes two metrics, GAP score and mitigation readiness, to identify governance gaps and prioritise actions. Using the UNICEF Innocenti Guidance on AI and Children 3.0 as primary material, we define reproducible extraction units, coding manuals, graph patterns, scoring scales, and consistency checks, and we demonstrate exemplar gap profiles and governance priority matrices for ten requirements. Results suggest that compared with privacy and data protection, requirements related to child well being and development, explainability and accountability, and cross agency implementation and resource allocation are more prone to indicator gaps and mechanism gaps. We recommend translating requirements into auditable closed loop governance th

When can a model of a physical system be regarded as computable? We provide the definition of a computable physical model to answer this question. The connection between our definition and Kreisel's notion of a mechanistic theory is discussed, and several examples of computable physical models are given, including models which feature discrete motion, a model which features non-discrete continuous motion, and probabilistic models such as radioactive decay. We show how computable physical models on effective topological spaces can be formulated using the theory of type-two effectivity (TTE). Various common operations on computable physical models are described, such as the operation of coarse-graining and the formation of statistical ensembles. The definition of a computable physical model also allows for a precise formalization of the computable universe hypothesis--the claim that all the laws of physics are computable.

A block in a linear order is an equivalence class when factored by the block relation B(x,y), satisfied by elements that are finitely far apart. We show that every computable linear order with dense condensation-type (i.e. a dense collection of blocks) but no infinite, strongly η-like interval (i.e. with all blocks of size less than some fixed, finite k) has a computable copy with the non-block relation eg B(x,y) computably enumerable. This implies that every computable linear order has a computable copy with a computable non-trivial self-embedding, and that the long-standing conjecture characterizing those computable linear orders every computable copy of which has a computable non-trivial self-embedding (as precisely those that contain an infinite, strongly η-like interval) holds for all linear orders with dense condensation-type.