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)

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)

Young children with limited knowledge of formal mathematics can intuitively perform basic arithmetic‐like operations over nonsymbolic, approximate representations of quantity. However, the algorithmic rules that guide such nonsymbolic operations are not entirely clear. We asked whether nonsymbolic arithmetic operations have a function‐like structure, like symbolic arithmetic. Children (n = 74 4‐ to ‐8‐year‐olds in Experiment 1; n = 52 7‐ to 8‐year‐olds in Experiment 2) first solved two nonsymbolic arithmetic problems. We then showed children two unequal sets of objects, and (...) asked children which of the two derived solutions should be added to the smaller of the two sets to make them “about the same.” We hypothesized that, if nonsymbolic arithmetic follows similar function rules to symbolic arithmetic, then children should be able to use the solutions of nonsymbolic computations as inputs into another nonsymbolic problem. Contrary to this hypothesis, we found that children were unable to reliably do so, suggesting that these solutions may not operate as independent representations that can be used inputs into other nonsymbolic computations. These results suggest that nonsymbolic and symbolic arithmetic computations are algorithmically distinct, which may limit the extent to which children can leverage nonsymbolic arithmetic intuitions to acquire formal mathematics knowledge. (shrink)

Approximations form an essential part of scientific activity and they come in different forms: conceptual approximations (simplifications in models), mathematical approximations of various types (e.g. linear equations instead of non-linear ones, computational approximations), experimental approximations due to limitations of the instruments and so on and so forth. In this paper, we will consider one type of approximation, namely numerical approximations involved in the comparison of two results, be they experimental or theoretical. Our goal is to lay down the conceptual (...) and formal foundations of a local theory of partial truth. This is done by introducing and exploring the concept of truth space. (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.

Re-Engineering Philosophy for Limited Beings is about new approaches to many of the big topics in philosophy of science today, but with a very different take. To begin with, we are urged to reject the received Cartesian-Laplacean myths: Descartes’ certainty and Laplace’s computational omniscience. Instead, Wimsatt re-engineers a philosophy for human beings with all their cognitive limitations. His approaches find their starting point in the actual practices of scientists themselves, which he strongly identifies with engineering practices as the source of (...) researchers’ solutions for dealing with a complex world. He aims to construct an understanding of scientific methodology around the central role of reduction. But he dismisses eliminative reductionism in favor of a heuristic-based realist view. Wimsatt’s world is a complex one, and this means that science needs to do away with all the absolute and simple answers, because they do not reflect the world we are living in. A complex world requires the mindset and tinkering of an engineer to uncover its reality. The appropriate response must be heuristics all the way down as we constantly seek out reliable inferences on often shifting ground. To this end, we aim for models and theories that are robust, just as engineers aim to build robust machines. And although errors occur and approaches are fallible, they allow us to continually adapt the heuristics applied and sharpen our perceptions so as to develop more refined tools for investigating and understanding the world. (shrink)

Digital topology is an extreme approach to constructive spatial representation in that a classical space is replaced or represented by a finite combinatorial space. This has led to a popular research area in which theory and applications are very closely related, but the question remains as to ultimately how mathematically viable this approach is, and what the formal relationship between a space and its finite representations is. Several researchers have attempted to answer this by showing that a space can be (...) constructed as the inverse limit of its finite representations, and this construction has been developed independently in computer science and physics. Therefore, in this formal sense, finite representations of classical spaces can be arbitrarily good. The relationship between classical and finite topology is by now fairly well understood, and in this work we extend the theory by showing that measures on the classical space are approximated by measures on finite spaces. (shrink)

It has long been recognized that the concept of inconsistency is a central part of commonsense reasoning. In this issue, a number of authors have explored the idea of reasoning with maximal consistent subsets of an inconsistent stratified knowledge base. This paradigm, often called “coherent-based reasoning", has resulted in some interesting proposals for para-consistent reasoning, non-monotonic reasoning, and argumentation systems. Unfortunately, coherent-based reasoning is computationally very expensive. This paper harnesses the approach of approximate entailment by Schaerf and Cadoli [SCH 95] (...) to develop the concept of “approximate coherent-based reasoning". To this end, we begin to present a multi-modal propositional logic that incorporates two dual families of modalities: □S and?S defined for each subset S of the set of atomic propositions. The resource parameter S indicates what atoms are taken into account when evaluating formulas. Next, we define resource-bounded consolidation operations that limit and control the generation of maximal consistent subsets of a stratified knowledge base. Then, we present counterparts to existential, universal, and argumentative inference that are prominent in coherence-based approaches. By virtue of modalities □S and?S, these inferences are approximated from below and from above, in an incremental fashion. Based on these features, we show that an anytime view of coherent-based reasoning is tenable. (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)

Computability theorists have introduced multiple hierarchies to measure the complexity of sets of natural numbers. The Kleene Hierarchy classifies sets according to the first-order complexity of their defining formulas. The Ershov Hierarchy classifies limit computable sets with respect to the number of mistakes that are needed to approximate them. Biacino and Gerla extended the Kleene Hierarchy to the realm of fuzzy sets, whose membership functions range in a complete lattice. In this paper, we combine the Ershov Hierarchy and (...) fuzzy set theory, by introducing and investigating the Fuzzy Ershov Hierarchy. (shrink)

It is conventionally understood that computers play a rather limited role in theoretical mathematics. While computation is indispensable in applied mathematics and the theory of computing and algorithms is rich and thriving, one does not, even today, expect to find computers in theoretical mathematics settings beyond the theory of computing. Where computers are used, by those studying combinatorics , algebra, number theory, or dynamical systems, the computer most often assumes the role of an automated and speedy theoretician, performing manipulations and (...) checking cases in a way assumed to be possible for human theoreticians, if only they had the time, the memory, and the precision. Automated proofs have become standard tools in mathematical logic, and it is often expected that proofs be published in a computer-checkable format. It is not surprising, then, that most philosophical work on computers in theoretical mathematics has been on computers' roles as supplementary mathematicians. Donald MacKenzie's 2001 book Mechanizing Proof demonstrates the rich potential for social and historical studies to complement the substantial analytic debate in this area of philosophy. But what of computers in theoretical mathematics behaving as computers, and not as mere mechanized mathematicians? Very little role is commonly assumed for computers working as supplements to mathematicians, rather than as supplementary mathematicians themselves. Accordingly, very little philosophy has attempted to grapple with theoretical mathematics in which computers play an essential but essentially non-theoretical role. My presentation will draw on work I conducted as a researcher in harmonic analysis on fractals at Cornell University. I will analyze the explicit and implicit conceptual apparatus employed in my and my fellow researchers' use of computers in the theoretical study of second order differential equations, such as those for sound and heat flow, on various fractal analogues of the Sierpinski gasket. Such gaskets are easy to visualize in very crude approximation in a low number of dimensions. As one increases the complexity of the gasket or the refinement of one's analysis, visualization and precise computation become impossible, and soon computers are unable to produce even approximate data to model differential equations in these situations. We thus had to carefully choose analytic approaches and methods to make our theoretical mathematics amenable to computer simulation. In my case, studying the transformation of the gaskets as they are expanded into increasingly high dimensions, computer simulation eventually required that the problem be reimagined entirely in terms of interlinked systems of parameters. This computer-approximation-driven theoretical orientation shaped my mathematical intuitions toward the problem and guided my fellow researchers and me in both theoretical and computational directions. We discovered both that computer approximation could be incredibly powerful as an aid to intuition, and that it can be incredibly difficult to transfer computer-oriented mathematics back into the purely theoretical standards of our area of specialty. I will address the philosophical implications of computer-driven theoretical mathematics, asking how computer experiments can shape both the content and standards of theoretical sciences. (shrink)

In this paper a theory of finitistic and frequentistic approximations — in short: f-approximations — of probability measures P over a countably infinite outcome space N is developed. The family of subsets of N for which f-approximations converge to a frequency limit forms a pre-Dynkin system $${{D\subseteq\wp(N)}}$$. The limiting probability measure over D can always be extended to a probability measure over $${{\wp(N)}}$$, but this measure is not always σ-additive. We conclude that probability measures can be regarded as idealizations (...) of limiting frequencies if and only if σ-additivity is not assumed as a necessary axiom for probabilities. We prove that σ-additive probability measures can be characterized in terms of so-called canonical and in terms of so-called full f-approximations. We also show that every non-σ-additive probability measure is f-approximable, though neither canonically nor fully f-approximable. Finally, we transfer our results to probability measures on open or closed formulas of first-order languages. (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'$.

1. The Physical Church-Turing Thesis. Physicists often interpret the Church-Turing Thesis as saying something about the scope and limitations of physical computing machines. Although this was not the intention of Church or Turing, the Physical Church Turing thesis is interesting in its own right. Consider, for example, Wolfram’s formulation: One can expect in fact that universal computers are as powerful in their computational capabilities as any physically realizable system can be, that they can simulate any physical system . . . (...) No physically implementable procedure could then shortcut a computationally irreducible process. (Wolfram 1985) Wolfram’s thesis consists of two parts: (a) Any physical system can be simulated (to any degree of approximation) by a universal Turing machine (b) Complexity bounds on Turing machine simulations have physical significance. For example, suppose that the computation of the minimum energy of some system of n particles takes at least exponentially (in n) many steps. Then the relaxation time of the actual physical system to its minimum energy state will also take exponential time. (shrink)

Work in the setting of the recursively enumerable sets and their Turing degrees. A set X is low if X', its Turning jump, is recursive in $\varnothing'$ and high if X' computes $\varnothing''$ . Attempting to find a property between being low and being recursive, Bickford and Mills produced the following definition. W is deep, if for each recursively enumerable set A, the jump of $A \bigoplus W$ is recursive in the jump of A. We prove that there are no (...) deep degrees other than the recursive one. Given a set W, we enumerate a set A and approximate its jump. The construction of A is governed by strategies, indexed by the Turning functionals Φ. Simplifying the situation, a typical strategy converts a failure to recursively compute W into a constraint on the enumeration of A, so that $(W \bigoplus A)'$ is forced to disagree with Φ(-; A'). The conversion has some ambiguity; in particular, A cannot be found uniformly from W. We also show that there is a "moderately" deep degree: There is a low nonzero degree whose join with any other low degree is not high. (shrink)

Scholars have long debated the appropriate balance between efficiency and redistribution. But recently, a wave of critics has argued not only that efficiency is less important, but that efficiency analysis itself is fundamentally flawed. Some say that efficiency is incoherent because there is no neutral baseline from which to judge inefficiency. Others say that efficiency is biased toward those best able to pay (generally, the rich). This essay contends that efficiency is not meaningfully incoherent or biased. The most widely discussed (...) forms of efficiency do not require any particular baseline, and even those that do require a baseline can still serve as useful approximations of more theoretically sound but computationally demanding measures. Moreover, arguments of bias do not account for the source of funds in public projects, produce unintuitive results, and draw an arbitrary cutoff between bias and non-bias that elides important distributional details. Ultimately, the tradeoff between efficiency and redistribution remains the most useful frame for policy debate. (shrink)

Some problems rarely discussed in traditional philosophy of science are mentioned: The empirical sciences using mathematico-quantitative theoretical models are frequently confronted with several types of computational problems posing primarily methodological limitations on explanatory and prognostic matters. Such limitations may arise from the appearances of deterministic chaos and (too) high computational complexity in general. In many cases, however, scientists circumvent such limitations by utilizing reductional approximations or complexity reductions for intractable problem formulations, thus constructing new models which are computationally tractable. Such (...) activities are compared with reduction types (more) established in philosophy of science. (shrink)

V’yugin has shown that there are a computable shift-invariant measure on $2^{\mathbb{N}}$ and a simple function $f$ such that there is no computable bound on the rate of convergence of the ergodic averages $A_{n}f$ . Here it is shown that in fact one can construct an example with the property that there is no computable bound on the complexity of the limit; that is, there is no computable bound on how complex a simple function needs (...) to be to approximate the limit to within a given $\varepsilon$. (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.

Every scientist chooses a preferred level of analysis and this choice shapes the research program, even determining what counts as evidence. This contribution revisits Marr's three levels of analysis and evaluates the prospect of making progress at each individual level. After reviewing limitations of theorizing within a level, two strategies for integration across levels are considered. One is top–down in that it attempts to build a bridge from the computational to algorithmic level. Limitations of this approach include insufficient theoretical constraint (...) at the computation level to provide a foundation for integration, and that people are suboptimal for reasons other than capacity limitations. Instead, an inside-out approach is forwarded in which all three levels of analysis are integrated via the algorithmic level. This approach maximally leverages mutual data constraints at all levels. For example, algorithmic models can be used to interpret brain imaging data, and brain imaging data can be used to select among competing models. Examples of this approach to integration are provided. This merging of levels raises questions about the relevance of Marr's tripartite view. (shrink)

Some problems rarely discussed in traditional philosophy of science are mentioned: The empirical sciences using mathematico-quantitative theoretical models are frequently confronted with several types of computational problems posing primarily methodological limitations on explanatory and prognostic matters. Such limitations may arise from the appearances of deterministic chaos and high computational complexity in general. In many cases, however, scientists circumvent such limitations by utilizing reductional approximations or complexity reductions for intractable problem formulations, thus constructing new models which are computationally tractable. Such activities (...) are compared with reduction types established in philosophy of science. (shrink)

The Conditional Probability Interpretation of Quantum Mechanics replaces the abstract notion of time used in standard Quantum Mechanics by the time that can be read off from a physical clock. The use of physical clocks leads to apparent non-unitary and decoherence. Here we show that a close approximation to standard Quantum Mechanics can be recovered from conditional Quantum Mechanics for semi-classical clocks, and we use these clocks to compute the minimum decoherence predicted by the Conditional Probability Interpretation.

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.

Bayesian learning theory and evolutionary theory both formalize adaptive competition dynamics in possibly high‐dimensional, varying, and noisy environments. What do they have in common and how do they differ? In this paper, we discuss structural and dynamical analogies and their limits, both at a computational and an algorithmic‐mechanical level. We point out mathematical equivalences between their basic dynamical equations, generalizing the isomorphism between Bayesian update and replicator dynamics. We discuss how these mechanisms provide analogous answers to the challenge of adapting (...) to stochastically changing environments at multiple timescales. We elucidate an algorithmic equivalence between a sampling approximation, particle filters, and the Wright‐Fisher model of population genetics. These equivalences suggest that the frequency distribution of types in replicator populations optimally encodes regularities of a stochastic environment to predict future environments, without invoking the known mechanisms of multilevel selection and evolvability. A unified view of the theories of learning and evolution comes in sight. (shrink)

Let R be a real closed field. An integer part I for R is a discretely ordered subring such that for every \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${r \in R}$$\end{document}, there exists an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${i \in I}$$\end{document} so that i ≤ r < i + 1. Mourgues and Ressayre (J Symb Logic 58:641–647, 1993) showed that every real closed field has an integer part. The procedure of Mourgues and (...) Ressayre appears to be quite complicated. We would like to know whether there is a simple procedure, yielding an integer part that is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^0_2(R)}$$\end{document} —limit computable relative to R. We show that there is a maximal Z-ring \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${I \subseteq R}$$\end{document} which is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^0_2(R)}$$\end{document}. However, this I may not be an integer part for R. By a result of Wilkie (Logic Colloquium ’77), any Z-ring can be extended to an integer part for some real closed field. Using Wilkie’s ideas, we produce a real closed field R with a Z-ring \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${I \subseteq R}$$\end{document} such that I does not extend to an integer part for R. For a computable real closed field, we do not know whether there must be an integer part in the class \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^0_2}$$\end{document}. We know that certain subclasses of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^0_2}$$\end{document} are not sufficient. We show that for each \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${n \in \omega}$$\end{document}, there is a computable real closed field with no n-c.e. integer part. In fact, there is a computable real closed field with no n-c.e. integer part for any n. (shrink)

What is computational explanation? Many accounts treat it as a kind of causal explanation. I argue against two more specific versions of this view, corresponding to two popular treatments of causal explanation. The first holds that computational explanation is mechanistic, while the second holds that it is interventionist. However, both overlook an important class of computational explanations, which I call limitative explanations. Limitative explanations explain why certain problems cannot be solved computationally, either in principle or in practice. I argue that (...) limitative explanations are not plausibly understood in either mechanistic or interventionist terms. One upshot of this argument is that there are causal and non-causal kinds of computational explanation. I close the paper by suggesting that both are grounded in the notion of computational implementation. (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)

Given any oracle, A, we construct a basic sequence Q, computable in the jump of A, such that no A-computable real is Q-distribution-normal. A corollary to this is that there is a Δn+10 basic sequence with respect to which no Δn0 real is distribution-normal. As a special case, there is a limit computable sequence relative to which no computable real is distribution-normal.

In this paper, we analyzed the periodicity of discrete Logistic and Tent sequences with different computational precision in detail. Further, we found that the process of iterations of the Logistic and Tent mapping is composed of transient and periodic stages. Surprisingly, for the different initial iterative values, we first discovered that all periodic stages have the same periodic limit cycles. This phenomenon has seriously affected the security of chaotic cipher. To solve this problem, we designed a novel discrete chaotic (...) sequence generator based on m-sequence and discrete chaotic mapping. The experimental results indicated that the chaotic sequence generator can generate pseudorandom chaotic sequences with large periodicity and good performance under the condition of limited computational precision. (shrink)

We introduce an implication-free fragment image of ω-arithmetic, having Exchange rule for sequents dropped. Exchange rule for formulas is, instead, an admissible rule in image. Our main result is that cut-free proofs of image are isomorphic with recursive winning strategies of a set of games called “1-backtracking games” in [S. Berardi, Th. Coquand, S. Hayashi, Games with 1-backtracking, Games for Logic and Programming Languages, Edinburgh, April 2005].We also show that image is a sound and complete formal system for the implication-free (...) fragment of LCM , Seventh International Conference on Typed Lambda Calculi and Applications, in: Lecture Notes in Computer Science, vol. 3461, 2005, pp. 11–22. Invited paper]). A simple syntactical description of this fragment was still missing. No sound and complete formal system is known for LCM itself. (shrink)

This paper attempts to make sense of a notion of ``approximation on certain scales'' in physical theories. I use this notion to understand the classical limit of ordinary quantum mechanics as a kind of scaling limit, showing that the mathematical tools of strict quantization allow one to make the notion of approximation precise. I then compare this example with the scaling limits involved in renormalization procedures for effective field theories. I argue that one does not yet (...) have the mathematical tools to make a notion of ``approximation on certain scales" precise in extant mathematical formulations of effective field theories. This provides guidance on the kind of further work that is needed for an adequate interpretation of quantum field theory. (shrink)

It's uncontroversial that notions of idealization and approximation are central to understanding computer simulations and their rationale. What's not so clear is what exactly these notions come to. Two distinct forms of approximation will be distinguished and their features contrasted with those of idealizations. These distinctions will be refined and closely tied to computer simulations by means of Scott-Strachey denotational programming semantics. The use of this sort of semantics also provides a convenient format for argumentation in favor of (...) several theses I shall propose concerning the role computer implemented approximations and idealizations play in fixing what the acceptance of an underlying scientific theory is or should be. (shrink)

In this paper we start from the assumption that in a metaphor, or an analogy, some terms belonging to one domain (source domain) are used to refer to objects other than their conventional referents belonging to a possibly different domain (target domain). We describe a formalism, which is based on the First Order Predicate Calculus, for representing the knowledge structure associated with a domain and then develop a theory of Constrained Semantic Transference [CST] which allows the terms and the structural (...) relationships of the source domain to be transferred coherently across to the target domain. We show how metaphors and analogies can be characterized in CST in such a way that many of their cognitive properties con be explained.We then propose a theory of Approximate Semantic Transference [AST] which is a computational version of CST and is derived from it by replacing the coherency requirement with approximate coherency. We show how AST can be used as a basis for designing models of cognitive processes involved in comprehending metaphors and analogies. (shrink)

This paper focuses on the interpretation of the Italian approximative adverb quasi 'almost' by primarily looking at cases in which it modifies temporal connectives, a domain which, to our knowledge, has been largely unexplored thus far. Consideration of this domain supports the need for a scalar account of the semantics of quasi (close in spirit to Hitzeman's semantic analysis of almost, in: Canakis et al. (eds) Papers from the 28th regional meeting of the Chicago Linguistic Society, 1992). When paired with (...) suitable analyses of temporal connectives, such an account can provide a simple explanation of the patterns of implication that are observed when quasi modifies locational (e. g. quando 'when'), directional (e. g. fino 'until' and da 'since'), and event-sequencing temporal connectives (e. g. prima 'before' and dopo ' after'). A challenging empirical phenomenon that is observed is a contrast between the modification of fino and da by quasi, on the one hand, and the modification of prima and dopo by the same adverb, on the other. While quasi fino and quasi da behave symmetrically, a puzzling asymmetry is observed between quasi prima and quasi dopo. To explain the asymmetry, we propose an analysis of prima and dopo on which the former has the meaning of the temporal comparative più presto 'earlier', while the latter is seen as an atomic predicate denoting temporal succession between events (Del Prete, Nat Lang Semantics 16: 157-203, 2008). We show that the same pattern of implication observed for quasi prima is attested when quasi modifies overt comparatives, and propose a pragmatic analysis of this pattern that uniformly applies to both cases, thus providing new evidence for the claim that prima is underlyingly a comparative. A major point of this paper is a discussion of the notion of scale which is relevant for the semantics of quasi', in particular, we show that the notion of Horn (entailment-based) scale is not well-suited for handling modification of temporal connectives, and that a more general notion of scale is required in order to provide a uniform analysis of quasi as a cross-categorial modifier. (shrink)

We discuss computability properties of the set of elements of best approximation of some point xX by elements of GX in computable Banach spaces X. It turns out that for a general closed set G, given by its distance function, we can only obtain negative information about as a closed set. In the case that G is finite-dimensional, one can compute negative information on as a compact set. This implies that one can compute the point in whenever it (...) is uniquely determined. This is also possible for a wider class of subsets G, given that one imposes additionally convexity properties on the space. If the Banach space X is computably uniformly convex and G is convex, then one can compute the uniquely determined point in . We also discuss representations of finite-dimensional subspaces of Banach spaces and we show that a basis representation contains the same information as the representation via distance functions enriched by the dimension. Finally, we study computability properties of the dimension and the codimension map and we show that for finite-dimensional spaces X the dimension is computable, given the distance function of the subspace. (shrink)

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)

It’s uncontroversial that notions of idealization and approximation are central to understanding computer simulations and their rationale. So, for example, one common form of computer simulation is to abandon a realistic approach that is computationally non-tractable for a more idealized but computationally tractable approach. Many simulations of systems of interacting members can be understood this way. In such simulations, realistic descriptions of individual members are replaced with less realistic descriptions which have the virtue of making interactions computationally tractable. Such (...) simulations can be supplemented with empirically determined correction factors which render the output produced by means of the idealizations more in accord, one hopes, with what the more realistic approach would have produced had it been computationally tractable. Another way to utilize computers is to replace an idealized but analytically tractable account of some phenomenon with a less idealized account which has no closed form or analytical solutions but where the computer can be used generate approximations to the desired solutions. (shrink)

This book offers a philosophy for error-prone humans trying to understand messy systems in the real world.

In this chapter, I argue that some aspects of cognitive phenomena cannot be explained computationally. In the first part, I sketch a mechanistic account of computational explanation that spans multiple levels of organization of cognitive systems. In the second part, I turn my attention to what cannot be explained about cognitive systems in this way. I argue that information-processing mechanisms are indispensable in explanations of cognitive phenomena, and this vindicates the computational explanation of cognition. At the same time, it has (...) to be supplemented with other explanations to make the mechanistic explanation complete, and that naturally leads to explanatory pluralism in cognitive science. The price to pay for pluralism, however, is the abandonment of the traditional autonomy thesis asserting that cognition is independent of implementation details. (shrink)