Search

Abstract With the current COVID‐19 pandemic, sophisticated epidemiological surveillance systems are more important than ever because conventional approaches have not been able to handle the scope and complexity of this global emergency. In response to this challenge, the authors present the state‐of‐the‐art SEIR‐Driven Semantic Integration Framework (SDSIF), which leverages the Internet of Things (IoT) to handle a variety of data sources. The primary innovation of SDSIF is the development of an extensive COVID‐19 ontology, which makes unmatched data interoperability and semantic inference possible. The framework facilitates not only real‐time data integration but also advanced analytics, anomaly detection, and predictive modelling through the use of Recurrent Neural Networks (RNNs). By being scalable and flexible enough to fit into different healthcare environments and geographical areas, SDSIF is revolutionising epidemiological surveillance for COVID‐19 outbreak management. Metrics such as Mean Absolute Error (MAE) and Mean sqḋ Error (MSE) are used in a rigorous evaluation. The evaluation also includes an exceptional R‐squared score, which attests to the effectiveness and ingenuity of SDSIF. Notably, a modest RMSE value of 8.70 highlights its accuracy, while a low MSE of 3.03 highlights its high predictive precision. The framework's remarkable R‐squared score of 0.99 emphasises its resilience in explaining variations in disease data even more.

In a recent article, the class of functions from the integers to the integers computable in polynomial time has been characterized using discrete ordinary differential equations (ODE), also known as finite differences. Doing so, the authors pointed out the fundamental role of linear (discrete) ODEs and classical ODE tools such as changes of variables to capture computability and complexity measures, or as a tool for programming.In this article, we extend the approach to a characterization of functions from the integers to the reals computable in polynomial time in the sense of computable analysis. In particular, we provide a characterization of such functions in terms of the smallest class of functions that contains some basic functions, and that is closed by composition, linear length ODEs, and a natural effective limit schema. [ABSTRACT FROM AUTHOR]

This work introduces the new class of pure reaction automata, as well as a new update manner, called maximal reactive manner, that can also be applied to standard reaction automata. Pure reaction automata differ from the standard model in that they don't have permanence: the entities that are not consumed by the reactions happening at a certain state are not conserved in the result states. We prove that the set of languages accepted by the new class under the maximal reactive manner contains the set of languages accepted by standard reaction automata under the same manner or under the maximal parallel manner. We also prove that a strict subclass of pure reaction automata can compute any partial recursive function. [ABSTRACT FROM AUTHOR]

AbstractThe “somewhat vague, intuitive” notion from computability theory of an effective procedure (method) or algorithm can be fairly precisely defined even if it is not sufficiently formal and precise to belong to mathematics proper (in a narrow sense)—and even if (as many have asserted) for that reason the Church–Turing thesis is unprovable. It is proved logically that the class of effective procedures is not decidable, i.e., that there is no effective procedure for ascertaining whether a given procedure is effective. This result is proved directly from the notion itself of an effective procedure, without reliance on any (partly) mathematical lemma, conjecture, or thesis invoking recursiveness or Turing-computability. In fact, there is no reliance on anything very mathematical. The proof does not even appeal to a precise definition of ‘effective procedure’. Instead, it relies solely and entirely on a basic grasp of the intuitive notion of an effective procedure. Though the result that effectiveness is undecidable is not surprising, it is also not without significance. It has the consequence, for example, that the solution to a decision problem, if it is to be complete, must be accompanied by a separate argument that the proposed ascertainment procedure invariably terminates with the correct verdict.

The “somewhat vague, intuitive” notion from computability theory of an effective procedure (method) or algorithm can be fairly precisely defined, even if it does not have a purely mathematical definition—and even if (as many have asserted) for that reason, the Church–Turing thesis (that the effectively calculable functions on natural numbers are exactly the general recursive functions), cannot be proved. However, it is logically provable from the notion of an effective procedure, without reliance on any (partially) mathematical thesis or conjecture concerning effective procedures, such as the Church–Turing thesis, that the class of effective procedures is undecidable, i.e., that there is no effective procedure for ascertaining whether a given procedure is effective. The proof does not even appeal to a precise definition of ‘effective procedure’. Instead, it relies solely and entirely on a basic grasp of the intuitive notion of such a procedure. Though the result itself is not surprising, it is also not without significance. It has the consequence, for example, that the solution to a decision problem, if it is to be complete, must be accompanied by a separate argument that the proposed ascertainment procedure is, in fact, a decision procedure, i.e., effective—for example, that it invariably terminates with the correct verdict.

A novel regression method is introduced and studied. The procedure weights squared residuals based on their magnitude. Unlike the classic least squares which treats every squared residual as equally important, the new procedure exponentially down-weights squared residuals that lie far away from the cloud of all residuals and assigns a constant weight (one) to squared residuals that lie close to the center of the squared-residual cloud. The new procedure can keep a good balance between robustness and efficiency; it possesses the highest breakdown point robustness for any regression equivariant procedure, being much more robust than the classic least squares, yet much more efficient than the benchmark robust method, the least trimmed squares (LTS) of Rousseeuw. With a smooth weight function, the new procedure could be computed very fast by the first-order (first-derivative) method and the second-order (second-derivative) method. Assertions and other theoretical findings are verified in simulated and real data examples. [ABSTRACT FROM AUTHOR]

Much of the formal study of algorithmic concerns with respect to semantics for abstract argumentation frameworks has focused on the issue of computational complexity. In contrast matters regarding computability have been largely neglected. Recent trends in semantics have, however, started to concentrate not so much on the formulation of novel semantics but more on identifying common properties: for example, from basic ideas such as conflict-freeness through to quite sophisticated ideas such as serializability. The aim of this paper is to look at the implications these more recent studies have for computability rather than computational complexity. [ABSTRACT FROM AUTHOR]

We answer a question of Slaman and Steel by showing that a version of Martin’s conjecture holds for all regressive functions on the hyperarithmetic degrees. A key step in our proof, which may have applications to other cases of Martin’s conjecture, consists of showing that we can always reduce to the case of a continuous function. [ABSTRACT FROM AUTHOR]

In the game of Matching Pennies, Alice and Bob each hold a penny, and at every tick of the clock they simultaneously display the head or the tail sides of their coins. If they both display the same side, then Alice wins Bob's penny; if they display different sides, then Bob wins Alice's penny. To avoid giving the opponent a chance to win, both players seem to have nothing else to do but to randomly play heads and tails with equal frequencies. However, while not losing in this game is easy, not missing an opportunity to win is not. Randomizing your own moves can be made easy. Recognizing when the opponent's moves are not random can be arbitrarily hard. The notion of randomness is central in game theory, but it is usually taken for granted. The notion of outsmarting is not central in game theory, but it is central in the practice of gaming. We pursue the idea that these two notions can be usefully viewed as two sides of the same coin. The resulting analysis suggests that the methods for strategizing in gaming and security, and for randomizing in computation, can be leveraged against each other. [ABSTRACT FROM AUTHOR]

This article compares two methods of algorithmically processing bandlimited time-continuous signals in light of the general problem of finding "suitable" representations of analog information on digital hardware. Albeit abstract, we argue that this problem is fundamental in digital twinning, a signal-processing paradigm the upcoming 6G communication-technology standard relies on heavily. Using computable analysis, we formalize a general framework of machine-readable descriptions for representing analytic objects on Turing machines. Subsequently, we apply this framework to sampling and interpolation theory, providing a thoroughly formalized method for digitally processing the information carried by bandlimited analog signals. We investigate discrete-time descriptions, which form the implicit quasi-standard in digital signal processing, and establish continuous-time descriptions that take the signal's continuous-time behavior into account. Motivated by an exemplary application of digital twinning, we analyze a textbook model of digital communication systems accordingly. We show that technologically fundamental properties, such as a signal's (Banach-space) norm, can be computed from continuous-time, but not from discrete-time descriptions of the signal. Given the high trustworthiness requirements within 6G, e.g., employed software must satisfy assessment criteria in a provable manner, we conclude that the problem of "trustworthy" digital representations of analog information is indeed essential to near-future information technology. [ABSTRACT FROM AUTHOR]

Cognitive scientists treat verification as a computation in which descriptions that match the relevant situation are true, but otherwise false. The claim is controversial: The logician Gödel and the physicist Penrose have argued that human verifications are not computable. In contrast, the theory of mental models treats verification as computable, but the two truth values of standard logics, true and false, as insufficient. Three online experiments (n = 208) examined participants' verifications of disjunctive assertions about a location of an individual or a journey, such as: 'You arrived at Exeter or Perth'. The results showed that their verifications depended on observation of a match with one of the locations but also on the status of other locations (Experiment 1). Likewise, when they reached one destination and the alternative one was impossible, their use of the truth value: could be true and could be false increased (Experiment 2). And, when they reached one destination and the only alternative one was possible, they used the truth value, true and it couldn't have been false, and when the alternative one was impossible, they used the truth value: true but it could have been false (Experiment 3). These truth values and those for falsity embody counterfactuals. We implemented a computer program that constructs models of disjunctions, represents possible destinations, and verifies the disjunctions using the truth values in our experiments. Whether an awareness of a verification's outcome is computable remains an open question. [ABSTRACT FROM AUTHOR]

We consider a wide series of classes of algorithmic complexity. We fix such a class and investigate the complexity of the inversion operation in classical algebraic structures, like groups or fields. In addition, we analyze the properties of quotient structures. [ABSTRACT FROM AUTHOR]

Given a simplicial pair (X, A), a simplicial complex Y, and a map f : A → Y , does f have an extension to X? We show that for a fixed Y, this question is algorithmically decidable for all X, A, and f if Y has the rational homotopy type of an H-space. As a corollary, many questions related to bundle structures over a finite complex are likely decidable. Conversely, for all other Y, the question is at least as hard as certain special cases of Hilbert's tenth problem which are known or suspected to be undecidable. [ABSTRACT FROM AUTHOR]

Robust estimation of a mean vector, a topic regarded as obsolete in the traditional robust statistics community, has recently surged in machine learning literature in the last decade. The latest focus is on the sub-Gaussian performance and computability of the estimators in a non-asymptotic setting. Numerous traditional robust estimators are computationally intractable, which partly contributes to the renewal of the interest in the robust mean estimation. Robust centrality estimators, however, include the trimmed mean and the sample median. The latter has the best robustness but suffers a low efficiency drawback. Trimmed mean and median of means, achieving sub-Gaussian performance have been proposed and studied in the literature. This article investigates the robustness of leading sub-Gaussian estimators of mean and reveals that none of them can resist greater than 25 % contamination in data and consequently introduces an outlyingness induced winsorized mean which has the best possible robustness (can resist up to 50 % contamination without breakdown) meanwhile achieving high efficiency. Furthermore, it has a sub-Gaussian performance for uncontaminated samples and a bounded estimation error for contaminated samples at a given confidence level in a finite sample setting. It can be computed in linear time. [ABSTRACT FROM AUTHOR]

A novel regression method is introduced and studied. The procedure weights squared residuals based on their magnitude. Unlike the classic least squares which treats every squared residual as equally important, the new procedure exponentially down-weights squared residuals that lie far away from the cloud of all residuals and assigns a constant weight (one) to squared residuals that lie close to the center of the squared-residual cloud. The new procedure can keep a good balance between robustness and efficiency; it possesses the highest breakdown point robustness for any regression equivariant procedure, being much more robust than the classic least squares, yet much more efficient than the benchmark robust method, the least trimmed squares (LTS) of Rousseeuw. With a smooth weight function, the new procedure could be computed very fast by the first-order (first-derivative) method and the second-order (second-derivative) method. Assertions and other theoretical findings are verified in simulated and real data examples.

This article will focus on the mechanistic origins of the computer metaphor, which forms the conceptual framework for the methodology of the cognitive sciences, some areas of artificial intelligence and the philosophy of mind. The connection between the history of computing technology, epistemology and the philosophy of mind is expressed through the metaphorical dictionaries of the philosophical discourse of a particular era. The conceptual clarification of this connection and the substantiation of the mechanistic components of the computer metaphor is the main goal of this article. The statement is substantiated that the invention of mechanical computing devices, having a long history in the European engineering tradition, formed the prerequisites for the emergence of machine functionalism in the modern philosophy of mind. The idea of multiple implementation stems from the principle that a formal symbol system prescribes rules for the use of rational abstractions through the physical architecture of a computational engine. The article considers the reasons for the conceptual shift and reveals the semantic foundations for the metaphorical transfer of the properties of abstract objects from the theory of automata to the field of modern philosophy of mind. The criticism and ways of protecting the philosophical program of machine functionalism are analyzed by changing the content of the metaphor “Mind as machine”. The reasons for the stability of the information-computer approach in cognitive sciences are also disclosed and explained.

Is ethics a computable function? Can machines learn ethics like humans do? If teaching consists in no more than programming, training, indoctrinating… and if ethics is merely following a code of conduct, then yes, we can teach ethics to algorithmic machines. But if ethics is not merely about following a code of conduct or about imitating the behavior of others, then an approach based on computing outcomes, and on the reduction of ethics to the compilation and application of a set of rules, either a priori or learned, misses the point. Our intention is not to solve the technical problem of machine ethics, but to learn something about human ethics, and its rationality, by reflecting on the ethics that can and should be implemented in machines. Any machine ethics implementation will have to face a number of fundamental or conceptual problems, which in the end refer to philosophical questions, such as: what is a human being (or more generally, what is a worthy being); what is human intentional acting; and how are intentional actions and their consequences morally evaluated. We are convinced that a proper understanding of ethical issues in AI can teach us something valuable about ourselves, and what it means to lead a free and responsible ethical life, that is, being good people beyond merely “following a moral code”. In the end we believe that rationality must be seen to involve more than just computing, and that value rationality is beyond numbers. Such an understanding is a required step to recovering a renewed rationality of ethics, one that is urgently needed in our highly technified society. [ABSTRACT FROM AUTHOR]

This paper introduces a category theory-based framework to redefine physical computing in light of advancements in quantum computing and non-standard computing systems. By integrating classical definitions within this broader perspective, the paper rigorously recontextualizes what constitutes physical computing devices and processes. It demonstrates how the compositional nature and relational structures of physical computing systems can be coherently formalized using category theory. This approach not only encapsulates recent formalisms in physical computing but also offers a structured method to explore the dynamic interactions within these systems.

It is established that the computable representability of the model is equivalent to the finite universal definability of some of its finite enrichment. [ABSTRACT FROM AUTHOR]

1936 was a watershed year for computability. Debates among Gödel, Church and others over the correct analysis of the intuitive concept "human effectively computable", an analysis at the heart of the Incompleteness Theorems, the Entscheidungsproblem, the question of what a finite computation is, and most urgently—for Gödel—the generality of the Incompleteness Theorems, were definitively set to rest with the appearance, in that year, of the Turing Machine. The question I explore here is, do the mathematical facts exhaust what is to be said about the thinking behind the "confluence of ideas in 1936"? I will argue for a cultural role in Gödel's, and, by extension, the larger logical community's absorption of Turing's 1936 model. As scaffolding I employ a conceptual framework due to the critic Leo Marx of the technological sublime; I also make use of the distinction within the technological sublime due to Caroline Jones, between its iconic and performative modes—a distinction operating within the conceptual art of the 1960s, but serving the history of computability equally well. [ABSTRACT FROM AUTHOR]

We construct a finite-range potential on a bidimensional full shift on a finite alphabet that exhibits a zero-temperature chaotic behavior as introduced by van Enter and Ruszel. This is the phenomenon where there exists a sequence of temperatures that converges to zero for which the whole set of equilibrium measures at these given temperatures oscillates between two sets of ground states. Brémont's work shows that the phenomenon of non-convergence does not exist for finite-range potentials in dimension one for finite alphabets; Leplaideur obtained a different proof for the same fact. Chazottes and Hochman provided the first example of non-convergence in higher dimensions d ≥ 3 ; we extend their result for d = 2 and highlight the importance of two estimates of recursive nature that are crucial for this proof: the relative complexity and the reconstruction function of an extension. We note that a different proof of this result was found by Chazottes and Shinoda, at around the same time that this article was initially submitted and that a strong generalization has been found by Gayral, Sablik and Taati. [ABSTRACT FROM AUTHOR]

Hybrid Systems are systems having a mixed discrete and continuous behaviour that cannot be characterised faithfully using either discrete or continuous models only. Due to the intrinsic complexity of hybrid systems, it is highly desirable to describe them compositionally, where large systems are seen as the composition of several simpler subparts that are studied independently. Furthermore, since several problems, including reachability, are undecidable for hybrid systems, the availability of approximate decision procedures is another important feature. In this paper, we propose a purely behavioural formalism for hybrid systems that is compositional and supports approximate decision procedures. The formalism is abstract and sufficiently general to subsume or be a semantic framework for most of the concrete formalisms or languages proposed in the literature. [ABSTRACT FROM AUTHOR]

Descriptive set theory and computability theory are closely-related fields of logic; both are oriented around a notion of descriptive complexity. However, the two fields typically consider objects of very different sizes; computability theory is principally concerned with subsets of the naturals, while descriptive set theory is interested primarily in subsets of the reals. In this paper, we apply a generalization of computability theory, admissible recursion theory, to consider the relative complexity of notions that are of interest in descriptive set theory. In particular, we examine the perfect set property, determinacy, the Baire property, and Lebesgue measurability. We demonstrate that there is a separation of descriptive complexity between the perfect set property and determinacy for analytic sets of reals; we also show that the Baire property and Lebesgue measurability are both equivalent in complexity to the property of simply being a Borel set, for $\boldsymbol {\Sigma ^{1}_{2}}$ sets of reals. [ABSTRACT FROM AUTHOR]

We improve on and generalize a 1960 result of Maltsev. For a field F, we denote by $H(F)$ the Heisenberg group with entries in F. Maltsev showed that there is a copy of F defined in $H(F)$ , using existential formulas with an arbitrary non-commuting pair of elements as parameters. We show that F is interpreted in $H(F)$ using computable $\Sigma _1$ formulas with no parameters. We give two proofs. The first is an existence proof, relying on a result of Harrison-Trainor, Melnikov, R. Miller, and Montalbán. This proof allows the possibility that the elements of F are represented by tuples in $H(F)$ of no fixed arity. The second proof is direct, giving explicit finitary existential formulas that define the interpretation, with elements of F represented by triples in $H(F)$. Looking at what was used to arrive at this parameter-free interpretation of F in $H(F)$ , we give general conditions sufficient to eliminate parameters from interpretations. [ABSTRACT FROM AUTHOR]

This paper reviews some fundamental results in prediction theory, spectral factorization and Wiener filtering with a particular focus on questions of computability. Since the mathematical theory of prediction and estimation of stationary time series was established by Kolmogorov, Paley, Szegö, Wiener, and many others, it seems to be an open question whether it is possible to effectively compute optimal filter coefficients and important performance measures on digital computers, i.e. on Turing machines. In this paper, we show that the optimum mean squared error (MSE) for predicting a stationary time series from its past observations is generally not Turing computable. However, under an additional condition on the stochastic process, namely, for strictly positive spectral densities, Turing computability of the corresponding optimal MSE can be guaranteed. Nevertheless, even if the MSE is Turing computable, there always exist spectral densities that are polynomial-time computable on a Turing machine, but such that the corresponding optimal MSE is not polynomial-time computable. This observation proves a complexity blowup for the computation of the MSE on digital computers. Finally, we show that the spectral factorization and the calculation of the optimal prediction filter are generally not Turing computable even under additional strong assumptions on the smoothness of the spectral density. [ABSTRACT FROM AUTHOR]