A new approach for a uniform classification of the computably approximable real numbers is introduced. This is an important class of reals, consisting of the limits of computable sequences of rationals, and it coincides with the 0'-computable reals. Unlike some of the existing approaches, this applies uniformly to all reals in this class: to each computably approximable real x we assign a degree structure, the structure of all possible ways available to approximate x. (...) So the main criterion for such classification is the variety of the effective ways we have to approximate a real number. We exhibit extreme cases of such approximation structures and prove a number of related results. (shrink)

Given a class ℱ oft otal functions in the set oft he natural numbers, one could study the real numbers that have arbitrarily close rational approximations explicitly expressible by means of functions from ℱ. We do this for classes ℱsatisfying certain closedness conditions. The conditions in question are satisfied for example by the class of all recursive functions, by the class of the primitive recursive ones, by any of the Grzegorczyk classes ℰnwith n ≥ 2, by the class of all (...) functions recursive in a given function and by the class of the functions primitive recursive in it, as well as by the class of all total functions in the set of the natural numbers. (shrink)

A real number is recursively approximable if there is a computable sequence of rational numbers converging to it. If some extra condition to the convergence is added, then the limit real number might have more effectivity. In this note we summarize some recent attempts to classify the recursively approximable real numbers by the convergence rates of the corresponding computable sequences ofr ational numbers.

We study the approximation properties of computably enumerable reals. We deal with a natural notion of approximation representation and study their wtt-degrees. Also, we show that a single representation may correspond to a quite diverse variety of reals.

One recursively enumerable real α dominates another one β if there are nondecreasing recursive sequences of rational numbers (a[n] : n ∈ ω) approximating α and (b[n] : n ∈ ω) approximating β and a positive constant C such that for all n, C(α − a[n]) ≥ (β − b[n]). See [R. M. Solovay, Draft of a Paper (or Series of Papers) on Chaitin’s Work, manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1974, p. 215] and [G. J. (...) Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350–359]. We show that every recursively enumerable random real dominates all other recursively enumerable reals. We conclude that the recursively enumerable random reals are exactly the Ω-numbers [G. J. Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350–359]. Second, we show that the sets in a universal Martin-Lof test for randomness have random measure, and every recursively enumerable random number is the sum of the measures represented in a universal Martin-Lof test. (shrink)

We study Δ2 reals x in terms of how they can be approximated symmetrically by a computable sequence of rationals. We deal with a natural notion of ‘approximation representation’ and study how these are related computationally for a fixed x. This is a continuation of earlier work; it aims at a classification of Δ2 reals based on approximation and it turns out to be quite different than the existing ones (based on information content etc.).

A theory of approximation to measurable sets and measurable functions based on the concepts of recursion theory and discrete complexity theory is developed. The approximation method uses a model of oracle Turing machines, and so the computational complexity may be defined in a natural way. This complexity measure may be viewed as a formulation of the average-case complexity of real functions—in contrast to the more restrictive worst-case complexity. The relationship between these two complexity measures is further studied and compared with (...) the notion of the distribution-free probabilistic computation. The computational complexity of the Lebesgue integral of polynomial-time approximable functions is studied and related to the question “FP = ♯P?”. (shrink)

We show that for any real number, the class of real numbers less random than it, in the sense of rK-reducibility, forms a countable real closed subfield of the real ordered field. This generalizes the well-known fact that the computable reals form a real closed field. With the same technique we show that the class of differences of computably enumerable reals (d.c.e. reals) and the class of computably approximable reals (c.a. reals) form (...) real closed fields. The d.c.e. result was also proved nearly simultaneously and independently by Ng (Keng Meng Ng. Master's Thesis. National University of Singapore, in preparation). Lastly, we show that the class of d.c.e. reals is properly contained in the class or reals less random than Ω (the halting probability), which in turn is properly contained in the class of c.a. reals, and that neither the first nor last class is a randomness class (as captured by rK-reducibility). (shrink)

A real number x is computable iff it is the limit of an effectively converging computable sequence of rational numbers, and x is left computable iff it is the supremum of a computable sequence of rational numbers. By applying the operations “sup” and “inf” alternately n times to computable sequences of rational numbers we introduce a non-collapsing hierarchy {Σn, Πn, Δn : n ∈ ℕ} of real numbers. We characterize the classes Σ2, Π2 and Δ2 in various ways and give (...) several interesting examples. (shrink)

1. One theory or many? In 2004 a very interesting and readable article by Lenore Blum, entitled “Computing over the reals: Where Turing meets Newton,” appeared in the Notices of the American Mathematical Society. It explained a basic model of computation over the reals due to Blum, Michael Shub and Steve Smale (1989), subsequently exposited at length in their influential book, Complexity and Real Computation (1997), coauthored with Felipe Cucker. The ‘Turing’ in the title of Blum’s article refers (...) of course to Alan Turing, famous for his explication of the notion of mechanical computation on discrete data such as the integers. The ‘Newton’ there has to do to with the well known numerical method due to Isaac Newton for approximating the zeros of continuous functions under suitable conditions that is taken to be a paradigm of scientific computing. Finally, the meaning of “Turing meets Newton” in the title of Blum’s article has another, more particular aspect: in connection with the problem of controlling errors in the numerical solution of linear equations and inversion of matrices,Turing (1948) defined a notion of condition for the relation of changes in the output of a computation due to small changes in the input that is analogous to Newton’s definition of the derivative. The thrust of Blum’s 2004 article was that the BSS model of computation on the reals is the appropriate foundation for scientific computing in general. By way of response, two years later another very interesting and equally readable article appeared in the Notices, this time by Mark Braverman and Stephen Cook (2006) entitled “Computing over the reals: Foundations for scientific computing,” in which the authors argued that the requisite foundation is provided by a quite different “bit computation” model, that is in fact prima facie incompatible with the BSS model. The bit computation model goes back to ideas due to Stefan Banach and Stanislaw Mazur in the latter part of the 1930s, but the first publication was not made until Mazur (1963).. (shrink)

Virtual reality constitutes an alternative, effective, and increasingly utilized treatment option for people suffering from psychiatric and neurological illnesses. However, the currently available VR simulations provide a predetermined simulative framework that does not take into account the unique personality traits of each individual; this could result in inaccurate, extreme, or unpredictable responses driven by patients who may be overly exposed and in an abrupt manner to the predetermined stimuli, or result in indifferent, almost non-existing, reactions when the stimuli do not (...) affect the patients adequately and thus stronger stimuli are recommended. In this study, we present a VR system that can recognize the individual differences and readjust the VR scenarios during the simulation according to the treatment aims. To investigate and present this dynamically adaptive VR system we employ an Anxiety Disorder condition as a case study, namely arachnophobia. This system consists of distinct anxiety states, aiming to dynamically modify the VR environment in such a way that it can keep the individual within a controlled, and appropriate for the therapy needs, anxiety state, which will be called “desired states” for the study. This happens by adjusting the VR stimulus, in real-time, according to the electrophysiological responses of each individual. These electrophysiological responses are collected by an external electrodermal activity biosensor that serves as a tracker of physiological changes. Thirty-six diagnosed arachnophobic individuals participated in a one-session trial. Participants were divided into two groups, the Experimental Group which was exposed to the proposed real-time adaptive virtual simulation, and the Control Group which was exposed to a pre-recorded static virtual simulation as proposed in the literature. These results demonstrate the proposed system’s ability to continuously construct an updated and adapted virtual environment that keeps the users within the appropriately chosen state for approximately twice the time compared to the pre-recorded static virtual simulation. Thus, such a system can increase the efficiency of VR stimulations for the treatment of central nervous system dysfunctions, as it provides numerically more controlled sessions without unexpected variations. (shrink)

We call an $\alpha \in \mathbb {R}$ regainingly approximable if there exists a computable nondecreasing sequence $(a_n)_n$ of rational numbers converging to $\alpha $ with $\alpha - a_n n}$ for infinitely many n. Similarly, there exist regainingly approximable sets whose initial segment complexity infinitely often reaches the maximum possible for c.e. sets. Finally, there is a uniform algorithm splitting regular real numbers into two regainingly approximable numbers that are still regular.

The basic motivation behind this work is to tie together various computational complexity classes, whether over different domains such as the naturals or the reals, or whether defined in different manners, via function algebras (Real Recursive Functions) or via Turing Machines (Computable Analysis). We provide general tools for investigating these issues, using two techniques we call approximation and lifting. We use these methods to obtain two main theorems. First, we provide an alternative proof of the result from Campagnolo et (...) al. (J Complex 18:977–1000, 2002), which precisely relates the Kalmar elementary computable functions to a function algebra over the reals. Second, we build on that result to extend a result of Bournez and Hainry (Theor Comput Sci 348(2–3):130–147, 2005), which provided a function algebra for the ${\mathcal{C}}^2$ real elementary computable functions; our result does not require the restriction to ${\mathcal{C}}^2$ functions. In addition to the extension, we provide an alternative approach to the proof. Their proof involves simulating the operation of a Turing Machine using a function algebra. We avoid this simulation, using a technique we call lifting, which allows us to lift the classic result regarding the elementary computable functions to a result on the reals. The two new techniques bring a different perspective to these problems, and furthermore appear more easily applicable to other problems of this sort. (shrink)

The technical results presented here on continuity and approximate implication are obviously incomplete. In particular, a syntactic characterization of approximate implication is highly desirable. Nevertheless, I believe the results above do show that the theory has considerable promise for application to the areas mentioned at the top of the paper.Formulation and defense of realist interpretations of science, for example, require approximate truth because we hardly ever have evidence that a particular scientific theory corresponds perfectly with a portion of the real (...) world. Realists need to assert, then, that evidence for a theory is evidence for its approximate truth, not its truth (see [3] and [18]). Approximate truth is, however, a vague notion, and specification of quantity terms and of a sense of approximation are needed to make precise applications of it. Suitability of both vocabulary and sense of approximation depend on the subject matter, and their selection is a partly empirical matter that raises complex issues. In light of the number of common inferences which are not continuous, realists also need to be concerned about indiscriminate use of deductive logic to derive consequences from approximately true theories. These issues will be considered further in a future paper.Approximate truth also has potential application in areas of artificial intelligence that require inference from inaccurate data. In the ‘qualitative’ physical theories of de Kleer and Brown [6], for example, ‘qualitative’ values are derived by partitioning the real numbers into regions. Inferences leading from inside to outside a region must be identified and avoided, and approximate implication and continuity may prove useful in doing this. More generally, growing use of predicate logic as a programming language invites application of the theory of approximate truth as a symbolic substitute for numerical evaluation of computation errors. This too will be the subject of a future paper. (shrink)

In many areas of scientific inquiry, the phenomena under investigation are viewed as functions on the real numbers. Since observational precision is limited, it makes sense to view these phenomena as bounded functions on the rationals. One may translate the basic notions of recursion theory into this framework by first interpreting a partial recursive function as a function on Q. The standard notions of inductive inference carry over as well, with no change in the theory. When considering the class of (...) computable functions on Q, there are a number of natural ways in which to define the distance between two functions. We utilize standard metrics to explore notions of approximate inference — our inference machines will attempt to guess values which converge to the correct answer in these metrics. We show that the new inference notions, NV∞, EX∞, and BC∞, infer more classes of functions than their standard counterparts, NV, EX, and BC. Furthermore, we give precise inclusions between the new inference notions and those in the standard inference hierarchy. We also explore weaker notions of approximate inference, leading to inference hierarchies analogous to the EXn and BCn hierarchies. Oracle inductive inference is also considered, and we give sufficient conditions under which approximate inference from a generic oracle G is equivalent to approximate inference with only finitely many queries to G. (shrink)

We devise imperative programming languages for verified real number computation where real numbers are provided as abstract data types such that the users of the languages can express real number computation by considering real numbers as abstract mathematical entities. Unlike other common approaches toward real number computation, based on an algebraic model that lacks implementability or transcendental computation, or finite-precision approximation such as using double precision computation that lacks a formal foundation, our languages are devised based on computable analysis, a (...) foundation of rigorous computation over continuous data. Consequently, the users of the language can easily program real number computation and reason about the behaviours of their programs, relying on their mathematical knowledge of real numbers without worrying about artificial roundoff errors. As the languages are imperative, we adopt precondition–postcondition-style program specification and Hoare-style program verification methodologies. Consequently, the users of the language can easily program a computation over real numbers, specify the expected behaviour of the program, including termination, and prove the correctness of the specification. Furthermore, we suggest extending the languages with other interesting continuous data, such as matrices, continuous real functions, et cetera.Abstract taken directly from the thesis.E-mail: [email protected]: https://sewonpark.com/thesis. (shrink)

Clarke and Beck use behavioural evidence to argue that approximate ratio computations are sufficient for claiming that the approximate number system represents the rationals, and the ANS does not represent the reals. We argue that pure behaviour is a poor litmus test for this problem, and that we should trust the psychophysical models that place ANS representations within the reals.

The demand of many scientific areas for the usage of fractional partial differential equations to explain their real-world systems has been broadly identified. The solutions may portray dynamical behaviors of various particles such as chemicals and cells. The desire of obtaining approximate solutions to treat these equations aims to overcome the mathematical complexity of modeling the relevant phenomena in nature. This research proposes a promising approximate-analytical scheme that is an accurate technique for solving a variety of noninteger partial differential equations. (...) The proposed strategy is based on approximating the derivative of fractional-order and reducing the problem to the corresponding partial differential equation. Afterwards, the approximating PDE is solved by using a separation-variables technique. The method can be simply applied to nonhomogeneous problems and is proficient to diminish the span of computational cost as well as achieving an approximate-analytical solution that is in excellent concurrence with the exact solution of the original problem. In addition and to demonstrate the efficiency of the method, it compares with two finite difference methods including a nonstandard finite difference method and standard finite difference technique, which are popular in the literature for solving engineering problems. (shrink)

Exact solutions of epidemic models are critical for identifying the severity and mitigation possibility for epidemics. However, solving complex models can be difficult when interfering conditions from the real-world are incorporated into the models. In this paper, we focus on the generally unsolvable adaptive susceptible-infected-susceptible epidemic model, a typical example of a class of epidemic models that characterize the complex interplays between the virus spread and network structural evolution. We propose two methods based on mean-field approximation, i.e., the first-order mean-field (...) approximation and higher-order mean-field approximation, to derive the exact solutions to ASIS models. Both methods demonstrate the capability of accurately approximating the metastable-state statistics of the model, such as the infection fraction and network density, with low computational cost. These methods are potentially powerful tools in understanding, mitigating, and controlling disease outbreaks and infodemics. (shrink)

We introduce and discuss a concept of approximation of a topological algebraic system A by finite algebraic systems from a given class K. If A is discrete, this concept agrees with the familiar notion of a local embedding of A in a class K of algebraic systems. One characterization of this concept states that A is locally embedded in K iff it is a subsystem of an ultraproduct of systems from K. In this paper we obtain a similar characterization of (...) approximability of a locally compact system A by systems from K using the language of nonstandard analysis. In the signature of A we introduce positive bounded formulas and their approximations; these are similar to those introduced by Henson [14] for Banach space structures (see also [15, 16]). We prove that a positive bounded formula φ holds in A if and only if all precise enough approximations of φ hold in all precise enough approximations of A. We also prove that a locally compact field cannot be approximated arbitrarily closely by finite (associative) rings (even if the rings are allowed to be non-commutative). Finite approximations of the field R can be considered as possible computer systems for real arithmetic. Thus, our results show that there do not exist arbitrarily accurate computer arithmetics for the reals that are associative rings. (shrink)

This paper presents a refinement of a result by Conidis, who proved that there is a real $X$ of effective packing dimension $0\lt \alpha\lt 1$ which cannot compute any real of effective packing dimension $1$. The original construction was carried out below $\emptyset''$, and this paper’s result is an improvement in the effectiveness of the argument, constructing such an $X$ by a limit-computable approximation to get $X\leq_{T}\emptyset'$.

Labels provide a quick and effective solution to obtain people interesting content from large-scale social network information. The current interest label extraction method based on the subgraph stream proves the feasibility of the subgraph stream for user label extraction. However, it is extremely time-consuming for constructing subgraphs. As an effective mathematical method to deal with fuzzy and uncertain information, rough set-based representations for subgraph stream construction are capable of capturing the uncertainties of the social network. Therefore, we propose an effective (...) approach called RS_UNITE_SS, which is suitable for large-scale social network user interest label extraction. Specifically, we first propose the subgraph division algorithm to construct a subgraph stream by incorporating a rough set. Then, the algorithm for user real-time interest label extraction based on upper approximation is proposed by using sequentially characteristics of the subgraph. Empirically, we evaluate RS_UNITE_SS over real-world datasets, and experimental results demonstrate that our proposed approach is more computationally efficient than existing methods while achieving higher precision value and MRR value. (shrink)

We study connections between classical asymptotic density, computability and computable enumerability. In an earlier paper, the second two authors proved that there is a computably enumerable set A of density 1 with no computable subset of density 1. In the current paper, we extend this result in three different ways: The degrees of such sets A are precisely the nonlow c.e. degrees. There is a c.e. set A of density 1 with no computable subset of nonzero density. There is (...) a c.e. set A of density 1 such that every subset of A of density 1 is of high degree. We also study the extent to which c.e. sets A can be approximated by their computable subsets B in the sense that A\B has small density. There is a very close connection between the computational complexity of a set and the arithmetical complexity of its density and we characterize the lower densities, upper densities and densities of both computable and computably enumerable sets. We also study the notion of "computable at density r" where r is a real in the unit interval. Finally, we study connections between density and classical smallness notions such as immunity, hyperimmunity, and cohesiveness. (shrink)

The International Competition on Computational Models of Argumentation (ICCMA) focuses on reasoning tasks in abstract argumentation frameworks. Submitted solvers are tested on a selected collection of benchmark instances, including artificially generated argumentation frameworks and some frameworks formalizing real-world problems. This paper presents the novelties introduced in the organization of the Third (2019) and Fourth (2021) editions of the competition. In particular, we proposed new tracks to competitors, one dedicated to dynamic solvers (i.e., solvers that incrementally compute solutions of frameworks obtained (...) by incrementally modifying original ones) in ICCMA’19 and one dedicated to approximate algorithms in ICCMA’21. From the analysis of the results, we noticed that i) dynamic recomputation of solutions leads to significant performance improvements, ii) approximation provides much faster results with satisfactory accuracy, and iii) classical solvers improved with respect to previous editions, thus revealing advancement in state of the art. (shrink)

It is shown that there exist subsets A and B of the real line which are recursively constructible such that A has a nonrecursive Hausdorff dimension and B has a recursive Hausdorff dimension but has a finite, nonrecursive Hausdorff measure. It is also shown that there exists a polynomial-time computable curve on the two-dimensional plane that has a nonrecursive Hausdorff dimension between 1 and 2. Computability of Julia sets of computable functions on the real line is investigated. It is shown (...) that there exists a polynomial-time computable function f on the real line whose Julia set is not recurisvely approximable. (shrink)

Margaret Morrison, (2015) Reconstructing Reality: Models, Mathematics, and Simulations. Oxford University Press, New York. -/- Scientific models, mathematical equations, and computer simulations are indispensable to scientific practice. Through the use of models, scientists are able to effectively learn about how the world works, and to discover new information. However, there is a challenge in understanding how scientists can generate knowledge from their use, stemming from the fact that models and computer simulations are necessarily incomplete representations, and partial descriptions, of their (...) target systems. In order to construct a model, one must make idealizations, approximations, and abstractions. Given these constraints in constructing models, there is a question of whether they can provide new insight into how real systems actually work. So, how is it that highly abstract models inform us about the nature of the world, and more specifically, how do they provide explanatory knowledge? In Reconstructing Reality: Models, Mathematics, and Simulations, philosopher Margaret Morrison undertakes this task of ... (shrink)

Kolmogorov complexity was originally defined for finitely-representable objects. Later, the definition was extended to real numbers based on the asymptotic behaviour of the sequence of the Kolmogorov complexities of the finitely-representable objects—such as rational numbers—used to approximate them.This idea will be taken further here by extending the definition to continuous functions over real numbers, based on the fact that every continuous real function can be represented as the limit of a sequence of finitely-representable enclosures, such as polynomials with rational coefficients.Based (...) on this definition, we will prove that for any growth rate imaginable, there are real functions whose Kolmogorov complexities have higher growth rates. In fact, using the concept of prevalence, we will prove that ‘almost every’ continuous real function has such a high-growth Kolmogorov complexity. An asymptotic bound on the Kolmogorov complexities of total single-valued computable real functions will be presented as well. (shrink)

We study the relationship between a computably enumerable real and its presentations. A set A presents a computably enumerable real α if A is a computably enumerable prefix-free set of strings such that equation image. Note that equation image is precisely the measure of the set of reals that have a string in A as an initial segment. So we will simply abbreviate equation image by μ. It is known that whenever A so presents α then (...) A ≤wttα, where ≤wtt denotes weak truth table reducibility, and that the wtt-degrees of presentations form an ideal ℐ in the computably enumerable wtt-degrees. We prove that any such ideal is equation image, and conversely that if ℐ is any nonempty equation image ideal in the computably enumerable wtt-degrees then there is a computable enumerable real α such that ℐ = ℐ. We also prove a kind of Rice Theorem for these ideals, namely that if the index set of such a equation image ideal is not empty or equal to ω then it is equation image-complete. (shrink)

It is known that a semicomputable continuum S in a computable topological space can be approximated by a computable subcontinuum by any given precision under condition that S is chainable and decomposable. In this paper we show that decomposability can be replaced by the assumption that S is chainable from a to b, where a is a computable point.

A computer can come to understand natural language the same way Helen Keller did: by using “syntactic semantics”—a theory of how syntax can suffice for semantics, i.e., how semantics for natural language can be provided by means of computational symbol manipulation. This essay considers real-life approximations of Chinese Rooms, focusing on Helen Keller’s experiences growing up deaf and blind, locked in a sort of Chinese Room yet learning how to communicate with the outside world. Using the SNePS computational knowledge-representation system, (...) the essay analyzes Keller’s belief that learning that “everything has a name” was the key to her success, enabling her to “partition” her mental concepts into mental representations of: words, objects, and the naming relations between them. It next looks at Herbert Terrace’s theory of naming, which is akin to Keller’s, and which only humans are supposed to be capable of. The essay suggests that computers at least, and perhaps non-human primates, are also capable of this kind of naming. (shrink)

Makkai [10] produced an arithmetical structure of Scott rank $\omega _{1}^{\mathit{CK}}$. In [9]. Makkai's example is made computable. Here we show that there are computable trees of Scott rank $\omega _{1}^{\mathit{CK}}$. We introduce a notion of "rank homogeneity". In rank homogeneous trees, orbits of tuples can be understood relatively easily. By using these trees, we avoid the need to pass to the more complicated "group trees" of [10] and [9]. Using the same kind of trees, we obtain one of rank (...) $\omega _{1}^{\mathit{CK}}$ that is "strongly computably approximable". We also develop some technology that may yield further results of this kind. (shrink)

There is no uniquely standard concept of an effectively decidable set of real numbers or real n-tuples. Here we consider three notions: decidability up to measure zero [M.W. Parker, Undecidability in Rn: Riddled basins, the KAM tori, and the stability of the solar system, Phil. Sci. 70(2) (2003) 359–382], which we abbreviate d.m.z.; recursive approximability [or r.a.; K.-I. Ko, Complexity Theory of Real Functions, Birkhäuser, Boston, 1991]; and decidability ignoring boundaries [d.i.b.; W.C. Myrvold, The decision problem for entanglement, in: R.S. (...) Cohen et al. (Eds.), Potentiality, Entanglement, and Passion-at-a-Distance: Quantum Mechanical Studies fo Abner Shimony, Vol. 2, Kluwer Academic Publishers, Great Britain, 1997, pp. 177–190]. Unlike some others in the literature, these notions apply not only to certain nice sets, but to general sets in Rn and other appropriate spaces. We consider some motivations for these concepts and the logical relations between them. It has been argued that d.m.z. is especially appropriate for physical applications, and on Rn with the standard measure, it is strictly stronger than r.a. [M.W. Parker, Undecidability in Rn: Riddled basins, the KAM tori, and the stability of the solar system, Phil. Sci. 70(2) (2003) 359–382]. Here we show that this is the only implication that holds among our three decidabilities in that setting. Under arbitrary measures, even this implication fails. Yet for intervals of non-zero length, and more generally, convex sets of non-zero measure, the three concepts are equivalent. (shrink)

An algebra is effective if its operations are computable under some numbering. When are two numberings of an effective partial algebra equivalent? For example, the computable real numbers form an effective field and two effective numberings of the field of computable reals are equivalent if the limit operator is assumed to be computable in the numberings . To answer the question for effective algebras in general, we give a general method based on an algebraic analysis of approximations by elements (...) of a finitely generated subalgebra. Commonly, the computable elements of a topological partial algebra are derived from such a finitely generated algebra and form a countable effective partial algebra. We apply the general results about partial algebras to the recursive reals, ultrametric algebras constructed by inverse limits, and to metric algebras in general. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim. (shrink)

We study the computational complexity of finding a line that bisects simultaneously two sets in the two-dimensional plane, called the pancake problem, using the oracle Turing machine model of Ko. We also study the basic problem of bisecting a set at a given direction. Our main results are: (1) The complexity of bisecting a nice (thick) polynomial-time approximable set at a given direction can be characterized by the counting class #P. (2) The complexity of bisecting simultaneously two linearly separable (...) nice (thick) polynomial-time approximable sets can be characterized by the counting class #P. (3) For either of these two problems, without the thickness condition and the linear separability condition (for the two-set case), it is arbitrarily hard to compute the bisector, even if it is unique. (shrink)

For any class of operators which transform unary total functions in the set of natural numbers into functions of the same kind, we define what it means for a real function to be uniformly computable or conditionally computable with respect to this class. These two computability notions are natural generalizations of certain notions introduced in a previous paper co-authored by Andreas Weiermann and in another previous paper by the same authors, respectively. Under certain weak assumptions about the class in question, (...) we show that conditional computability is preserved by substitution, that all conditionally computable real functions are locally uniformly computable, and that the ones with compact domains are uniformly computable. The introduced notions have some similarity with the uniform computability and its non-uniform extension considered by Katrin Tent and Martin Ziegler, however, there are also essential differences between the conditional computability and the non-uniform computability in question. (shrink)

A real X is defined to be relatively c.e. if there is a real Y such that X is c.e.(Y) and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${X \not\leq_T Y}$$\end{document}. A real X is relatively simple and above if there is a real Y (...) nonempty \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi^0_1}$$\end{document} class contains a member which is not relatively c.e. and that every 1-generic real is relatively simple and above. (shrink)

Recently, the Dimension Problem for effective Hausdorff dimension was solved by J. Miller in [14], where the author constructs a Turing degree of non-integral Hausdorff dimension. In this article we settle the Dimension Problem for effective packing dimension by constructing a real of strictly positive effective packing dimension that does not compute a real of effective packing dimension one (on the other hand, it is known via [10, 3, 7] that every real of strictly positive effective Hausdorff dimension computes (...) class='Hi'>reals whose effective packing dimensions are arbitrarily close to, but not necessarily equal to, one). (shrink)

We propose a lexical account of event nouns, in particular of deverbal nominalisations, whose meaning is related to the event expressed by their base verb. The literature on nominalisations often assumes that the semantics of the base verb completely defines the structure of action nominals. We argue that the information in the base verb is not sufficient to completely determine the semantics of action nominals. We exhibit some data from different languages, especially from Romance language, which show that nominalisations focus (...) on some aspects of the verb semantics. The selected aspects, however, seem to be idiosyncratic and do not automatically result from the internal structure of the verb nor from its interaction with the morphological suffix. We therefore propose a partially lexicalist approach view of deverbal nouns. It is made precise and computable by using the Montagovian generative lexicon, a type theoretical framework introduced by Bassac, Mery and Retoré in this journal in 2010. This extension of Montague semantics with a richer type system easily incorporates lexical phenomena like the semantics of action nominals in particular deverbals, including their polysemy and felicitous copredications. (shrink)

If one wants to compute with infinite objects like real numbers or data streams, continuity is a necessary requirement: better and better (finite) approximations of the input are transformed into better and better (finite) approximations of the output. In case the objects are constructively generated, they can be represented by a finite description of the generating procedure. By effectively transforming such descriptions for the generation of the input (respectively, their codes) into (the code of) a description for the generation of (...) the output another type of computable operation is obtained. Such operations are also called effective. The relationship of both classes of operations has always been a question of great interest. In this paper the setting is extended to the case of multifunctions. Various ways of coding (indexing) sets are discussed and their relationship is investigated. Moreover, effective versions of several continuity notions for multifunctions are introduced. For each of these notions an indexing system for sets is exhibited so that the multifunctions that are effective with respect to this indexing system are exactly the multifunction which are effectively continuous with respect to the continuity notion under consideration. Mostly, in addition to being effective the multifunctions need also possess certain witnessing functions. Important special cases are discussed where such witnessing functions always exist. (shrink)

-/- Continuous first-order logic has found interest among model theorists who wish to extend the classical analysis of “algebraic” structures (such as fields, group, and graphs) to various natural classes of complete metric structures (such as probability algebras, Hilbert spaces, and Banach spaces). With research in continuous first-order logic preoccupied with studying the model theory of this framework, we find a natural question calls for attention. Is there an interesting set of axioms yielding a completeness result? -/- The primary purpose (...) of this article is to show that a certain, interesting set of axioms does indeed yield a completeness result for continuous first-order logic. In particular, we show that in continuous first-order logic a set of formulae is (completely) satisfiable if (and only if) it is consistent. From this result it follows that continuous first-order logic also satisfies an approximated form of strong completeness, whereby Σ⊧φ (if and) only if Σ⊢φ ∸2−n for all n < ω. This approximated form of strong completeness asserts that if Σ⊧φ, then proofs from Σ, being finite, can provide arbitrarily better approximations of the truth of φ. -/- Additionally, we consider a different kind of question traditionally arising in model theory—that of decidability. When is the set of all consequences of a theory (in a countable, recursive language) recursive? Say that a complete theory T is decidable if for every sentence φ, the value φ T is a recursive real, and moreover, uniformly computable from φ. If T is incomplete, we say it is decidable if for every sentence φ the real number φ T o is uniformly recursive from φ, where φ T o is the maximal value of φ consistent with T. As in classical first-order logic, it follows from the completeness theorem of continuous first-order logic that if a complete theory admits a recursive (or even recursively enumerable) axiomatization then it is decidable. (shrink)

One of the disadvantages of the point estimate in survey sampling is that it fluctuates from sample to sample due to sampling error, as the estimator only provides a point value for the parameter under discussion. The neutrosophic approach, pioneered by Florentin Smarandache, is an excellent tool for estimating the parameters under consideration in sampling theory since it yields interval estimates in which the parameter lies with a very high probability. As a result, the neutrosophic technique, which is a generalization (...) of classical approach, is used to deal with ambiguous, indeterminate, and uncertain data. In this investigation, we suggest a new general family of ratio and exponential ratio type estimators for the elevated estimation of neutrosophic population mean of the primary variable utilizing known neutrosophic auxiliary parameters. For the first degree approximation, the bias and Mean Squared Error (MSE) of the suggested estimators are computed. The neutrosophic optimum values of the characterizing constants are determined, as well as the minimum value of the neutrosophic MSE of the suggested estimator is obtained for these optimum values of the characterizing scalars. Because the minimum MSE of the classical estimators of population mean lies inside the estimated interval of the neutrosophic estimators, the neutrosophic estimators are better than the equivalent classical estimators. The empirical investigation, which used both real and simulated data sets, backs up the theoretical findings. For practical utility in various areas of applications, the estimator with the lowest MSE or highest Percentage Relative Efficiency (PRE) is recommended. (shrink)

We propose a lexical account of event nouns, in particular of deverbal nominalisations, whose meaning is related to the event expressed by their base verb. The literature on nominalisations often assumes that the semantics of the base verb completely defines the structure of action nominals. We argue that the information in the base verb is not sufficient to completely determine the semantics of action nominals. We exhibit some data from different languages, especially from Romance language, which show that nominalisations focus (...) on some aspects of the verb semantics. The selected aspects, however, seem to be idiosyncratic and do not automatically result from the internal structure of the verb nor from its interaction with the morphological suffix. We therefore propose a partially lexicalist approach view of deverbal nouns. It is made precise and computable by using the Montagovian generative lexicon, a type theoretical framework introduced by Bassac, Mery and Retoré in this journal in 2010. This extension of Montague semantics with a richer type system easily incorporates lexical phenomena like the semantics of action nominals in particular deverbals, including their polysemy and felicitous copredications. (shrink)

BackgroundSocial cognition and competence are a key part of daily interactions and essential for satisfying relationships and well-being. Pediatric neurological and psychological conditions can affect social cognition and require assessment and remediation of social skills. To adequately approximate the complex and dynamic nature of real-world social interactions, innovative tools are needed. The aim of this study was to document the performance of adolescents on two versions of a serious video game presenting realistic, everyday, socio-moral conflicts, and to explore whether their (...) performance is associated with empathy or sense of presence, factors known to influence social cognition.MethodsParticipants first completed a pre-test measure of socio-moral reasoning based on three dilemmas from a previously validated computer task. Then, they either played an evaluative version or an adaptive version of a video game presenting nine social situations in which they made socio-moral decisions and provided justifications. In the evaluative version, participants’ audio justifications were recorded verbatim and coded manually to obtain a socio-moral reasoning maturity score. In the adaptive version, tailored feedback and social reinforcements were provided based on participant responses. An automatic coding algorithm developed using artificial intelligence was used to determine socio-moral maturity level in real-time and to provide a basis for the feedback and reinforcements in the game. All participants then completed a three-dilemma post-test assessment.ResultsThose who played the adaptive version showed improved SMR across the pre-test, in-game and post-test moral maturity scores, F = 9.81, pHF < 0.001, ϵ2 = 0.21, but those who played the Evaluative version did not. Socio-moral reasoning scores from both versions combined did not correlate with empathy or sense of presence during the game, though results neared significance. The study findings support preliminary validation of the game as a promising method for assessing and remediating social skills during adolescence. (shrink)

The Copenhagen interpretation of quantum mechanics assumes the existence of the classical deterministic Newtonian world. We argue that in fact the Newton determinism in classical world does not hold and in the classical mechanics there is fundamental and irreducible randomness. The classical Newtonian trajectory does not have a direct physical meaning since arbitrary real numbers are not observable. There are classical uncertainty relations: Δq>0 and Δp>0, i.e. the uncertainty (errors of observation) in the determination of coordinate and momentum is always (...) positive (non zero).A “functional” formulation of classical mechanics was suggested. The fundamental equation of the microscopic dynamics in the functional approach is not the Newton equation but the Liouville equation for the distribution function of the single particle. Solutions of the Liouville equation have the property of delocalization which accounts for irreversibility. The Newton equation in this approach appears as an approximate equation describing the dynamics of the average values of the position and momenta for not too long time intervals. Corrections to the Newton trajectories are computed. An interpretation of quantum mechanics is attempted in which both classical and quantum mechanics contain fundamental randomness. Instead of an ensemble of events one introduces an ensemble of observers. (shrink)

Disagreement about how best to think of the relation between theories and the realities they represent has a longstanding and venerable history. We take up this debate in relation to the free energy principle (FEP) - a contemporary framework in computational neuroscience, theoretical biology and the philosophy of cognitive science. The FEP is very ambitious, extending from the brain sciences to the biology of self-organisation. In this context, some find apparent discrepancies between the map (the FEP) and the territory (target (...) systems) a compelling reason to defend instrumentalism about the FEP. We take this to be misguided. We identify an important fallacy made by those defending instrumentalism about the FEP. We call it the literalist fallacy: this is the fallacy of inferring the truth of instrumentalism based on the claim that the properties of FEP models do not literally map onto real-world, target systems. We conclude that scientific realism about the FEP is a live and tenable option. (shrink)

The computability of reals was introduced by Alan Turing [20] by means of decimal representations. But the equivalent notion can also be introduced accordingly if the binary expansion, Dedekind cut or Cauchy sequence representations are considered instead. In other words, the computability of reals is independent of their representations. However, as it is shown by Specker [19] and Ko [9], the primitive recursiveness and polynomial time computability of the reals do depend on the representation. In this paper, (...) we explore how the weak computability of reals depends on the representation. To this end, we introduce three notions of weak computability in a way similar to the Ershov's hierarchy of Δ02-sets of natural numbers based on the binary expansion, Dedekind cut and Cauchy sequence, respectively. This leads to a series of classes of reals with different levels of computability. We investigate systematically questions as on which level these notions are equivalent. We also compare them with other known classes of reals like c. e. and d-c. e. reals. (shrink)

Continuous first-order logic has found interest among model theorists who wish to extend the classical analysis of “algebraic” structures to various natural classes of complete metric structures. With research in continuous first-order logic preoccupied with studying the model theory of this framework, we find a natural question calls for attention. Is there an interesting set of axioms yielding a completeness result?The primary purpose of this article is to show that a certain, interesting set of axioms does indeed yield a completeness (...) result for continuous first-order logic. In particular, we show that in continuous first-order logic a set of formulae is satisfiable if it is consistent. From this result it follows that continuous first-order logic also satisfies an approximated form of strong completeness, whereby Σ⊨φ only if Σ⊢φ∸ 2-n for all n < ω. This approximated form of strong completeness asserts that if Σ⊨φ, then proofs from Σ, being finite, can provide arbitrarily better approximations of the truth of φ.Additionally, we consider a different kind of question traditionally arising in model theory—that of decidability. When is the set of all consequences of a theory recursive? Say that a complete theory T is decidable if for every sentence φ, the value φT is a recursive real, and moreover, uniformly computable from φ. If T is incomplete, we say it is decidable if for every sentence φ the real number φT∘ is uniformly recursive from φ, where φT∘is the maximal value of φ consistent with T. As in classical first-order logic, it follows from the completeness theorem of continuous first-order logic that if a complete theory admits a recursive axiomatization then it is decidable. (shrink)