Mariko Yasugi, Vasco Brattka, Masako Washihara · 1999
We speculate on the Gauian function [x] as an example of a noncontinuous function which is nevertheless possessed of some properties of computability. An algorithm how to compute [x] for a single computable real number is first described, followed by a remark that [x] does not necessarily preserve sequential computability. Second, [x] is studied in the light of the notion of upper semi-computability. Then two Fr'echet spaces, R Z and L 1 loc (R) , in which the Gauian function is computable, will be taken up. 1 Introduction The Gauian function [x] is a real function which assigns to x the greatest integer not exceeding x. It is a good example of a function which is not continuous but is easy to understand. In the naive sense of computability, that is, in the sense of Chapter 0 of [7], it is not computable for the obvious reason that it is not continuous. On the other hand, in the sense of Blum-Shub-Smale, it is a simplest example of a computable function (Example 5 in [1]). The r...
Cited by 0
Apoloniusz Tyszka · SPIRE - Sciences Po Institutional REpository · 2024
K denotes both the knowledge predicate satisfied by every currently known theorem and the finite set of all currently known theorems.The set K is time-dependent and publicly available.Any theorem of any mathematician from past or present forever belongs to K. We prove the following Statement 1: there is a limit-computable function : N N of unknown computability which eventually dominates every function : N N with a single-fold Diophantine representation.Statement 1 holds when, for every. ., n}} has a unique solution in N n+1 , then this solution belongs to {0, . . ., b} n+1 .Statement 1 does not follow from any widely known mathematical theorem.Ignoring the epistemic condition in Statement 1, Statement 1 is implied by the following result of Royer and Case: There is a limit-computable function 1 : N N which eventually dominates every computable function 1 : N N. The proof of Statement 1 shows that Statement 1 follows from some mathematical theorem and the following conjunction: ((The function is computable) K) ((The function is uncomputable) K).
Cited by 0Open access
Philippe Moser · Mathematical logic quarterly · 2010
This paper studies how well computable functions can be approximated by their Fourier series. To this end, we equip the space of Lp-computable functions (computable Lebesgue integrable functions) with a size notion, by introducing Lp-computable Baire categories. We show that Lp-computable Baire categories satisfy the following three basic properties. Singleton sets {f } (where f is Lp-computable) are meager, suitable infinite unions of meager sets are meager, and the whole space of Lp-computable functions is not meager. We give an alternative characterization of meager sets via Banach-Mazur games. We study the convergence of Fourier series for Lp-computable functions and show that whereas for every p > 1, the Fourier series of every Lp-computable function f converges to f in the Lp norm, the set of L1-computable functions whose Fourier series does not diverge almost everywhere is meager (© 2010 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)
Cited by 2
Fred Richman · Journal of Symbolic Logic · 1983
The modern theory of computability is based on the works of Church, Markov and Turing who, starting from quite different models of computation, arrived at the same class of computable functions. The purpose of this paper is the show how the main results of the Church-Markov-Turing theory of computable functions may quickly be derived and understood without recourse to the largely irrelevant theories of recursive functions, Markov algorithms, or Turing machines. We do this by ignoring the problem of what constitutes a computable function and concentrating on the central feature of the Church-Markov-Turing theory: that the set of computable partial functions can be effectively enumerated. In this manner we are led directly to the heart of the theory of computability without having to fuss about what a computable function is. The spirit of this approach is similar to that of [RGRS]. A major difference is that we operate in the context of constructive mathematics in the sense of Bishop [BSH1], so all functions are computable by definition, and the phrase “you can find” implies “by a finite calculation.” In particular if P is some property, then the statement “for each m there is n such that P(m, n) ” means that we can construct a (computable) function θ such that P(m, θ(m)) for all m . Church's thesis has a different flavor in an environment like this where the notion of a computable function is primitive. One point of such a treatment of Church's thesis is to make available to Bishopstyle constructivists the Markovian counterexamples of Russian constructivism and recursive function theory. The lack of serious candidates for computable functions other than recursive functions makes it quite implausible that a Bishopstyle constructivist could refute Church's thesis, or any consequence of Church's thesis. Hence counterexamples such as Specker's bounded increasing sequence of rational numbers that is eventually bounded away from any given real number [SPEC] may be used, as Brouwerian counterexamples are, as evidence of the unprovability of certain assertions.
Cited by 26
Franklin, Johanna · Centre International de Rencontres Mathématiques · 2016
Carleson's Theorem states that for $1 < p < \infty$, the Fourier series of a function $f$ in $L^p[-\pi,\pi]$ converges to $f$ almost everywhere. We consider this theorem in the context of computable analysis and show the following two results. (1) For a computable $p > 1$, if $f$ is a computable vector in $L^p[?\pi,\pi]$ and $t_0 \in [-\pi,\pi]$ is Schnorr random, then the Fourier series for $f$ converges at $t_0$. (2) If $t_0 \in [-\pi,\pi]$ is not Schnorr random, then there is a computable function $f : [-\pi,\pi] \rightarrow \mathbb{C}$ whose Fourier series diverges at $t_0$. This is joint work with Timothy H. McNicholl, and Jason Rute.
Cited by 0Open access
Newcomb Greenleaf · ACM SIGCSE Bulletin · 1990
The concept of a non-computable function has been valuable in showing absolute limits to our power to compute. But it is problematically oxymoronic, particular in computer science classes, since functions are generally understood algorithmically, as objects which can be computed. This paper presents an alternative explanation for functions usually regarded as non-computable, based on a more careful examination of the data types of domain and range. The limits of computation are still revealed, and additional algorithmic consequences are found. But the confusion inherent in the self-contradictory phrase "non-computable function" is avoided.
Cited by 1Open access
Dingmar van Eck, Erik Weber · Riviste UNIMI (Università degli studi di Milano) · 2018
against the statements in L).We can avoid this problem by using codes for computable ordinals.Computable ordinals have the property that there is a computable function f such that, given a code n for a computably enumerable list of codes of computable ordinals 1 , 2 , . .., f (n) is a code for a computable ordinal greater than all the i .Having the source-code for the simulation, we could infer a code n for the list of all numbers k such that the statement "k is a code of a computable ordinal" is implied by the inhabitants' axioms.If we know the inhabitants do not assert false axioms, we can infer f (n) is a code of a computable ordinal.Thus, we know a computable ordinal bigger than all the computable ordinals the inhabitants know. (Self-reference) Perhaps, by diagonalization and selfreference, L already contains a statement equivalent to .This objection can be defeated by the same computable ordinal trick used above.
Cited by 0Open access
Kenshi Miyabe · 2016
Some recent researches show that some classical theorems with \\almost ev-erywhere &quot; can be converted to eective version with \\for each random point&quot;. One example is that a real is Martin-Lof random i each computable function of bounded variation is dierentiable at the real. The author [1] has given a Kurtz randomness version where we nd that an integral test is a useful tool to study the relation between algorithmic randomness and computable analysis. Here we give a version of Schnorr randomness. Consider a computable metric space (X; d; ) and a computable measure on it. De nition 1. An integral test for Schnorr randomness is a nonnegative lower semicomputable function t: X! R such that R td is a computable real. Theorem 1. A point z is Schnorr random i t(z) &lt; 1 for each integral test t for Schnorr randomness.
Cited by 0
Leeds Ls Jt · 2007
Abstract We investigate notions of randomness in the space C(2N) of continuous functions on 2N. A probability measure is given and a version of the Martin-L&amp;quot;of Test for randomness is defined. Random \\Delta 02 continuous functions exist, but no computable function can be random and no random function can map a computable real to a computable real. The image of a random continuous function is always a perfect set and hence uncountable. For any y 2 2N, there exists a random continuous function F with y in the image of F. Thus the image of a random continuous function need not be a random closed set. The set of zeroes of a random continuous function is always a random closed set. Research was partially supported by the National Science Foundation grants DMS 0532644 and 0554841. 1
Cited by 0
2005
The references are to Barendregt’s book [1]. Kleene’s characterization of the computable and partial computable functions. A numeric (or number-theoretic) function is a mapping ϕ: N p → N for some p ∈ N (§6.3, page 135). A partial numeric (or number theoretic) function is a partial mapping ϕ: N p ⇀ N for some p ∈ N (§8.4, page 178).
Cited by 0
Arno Pauly, Martin Ziegler, J Barwise et al. · Inactive DOIs · 2016
A type-2 computable real function is necessarily continuous; and this remains true for computations relative to any oracle. Conversely, by the Weierstrass Approximation Theorem, every continuous f : [0; 1] R is computable relative to some oracle.
Cited by 0Open access
Felipe S. Abrahão · WORLD SCIENTIFIC eBooks · 2016
In this article, we will show that uncomputability is a relative property not only of oracle Turing machines, but also of subrecursive classes. We will define the concept of a Turing submachine, and a recursive relative version for the Busy Beaver function which we will call Busy Beaver Plus function. Therefore, we will prove that the computable Busy Beaver Plus function defined on any Turing submachine is not computable by any program running on this submachine. We will thereby demonstrate the existence of a “paradox” of computability a la Skolem: a function is computable when “seen from the outside” the subsystem, but uncomputable when “seen from within” the same subsystem. Finally, we will raise the possibility of defining universal submachines, and a hierarchy of negative Turing degrees.
Cited by 8Open access
Tian Wu, Mengbo Zhang, Xunmin Ou · 2014
Cited by 0
Charles M. Harris, Kyung Il Lee, S. Barry Cooper · Mathematical logic quarterly · 2016
We develop an approach to the longstanding conjecture of Kierstead concerning the character of strongly nontrivial automorphisms of computable linear orderings. Our main result is that for any η-like computable linear ordering , such that has no interval of order type η, and such that the order type of is determined by a -limitwise monotonic maximal block function, there exists computable such that has no nontrivial automorphism.
Cited by 5Open access
Dieter Spreen · arXiv (Cornell University) · 2023
Partiality is a natural phenomenon in computability that we cannot get around. So, the question is whether we can give the areas where partiality occurs, that is, where non-termination happens, more structure. In this paper we consider function classes which besides the total functions only contain finite functions whose domain of definition is an initial segment of the natural numbers. Such functions appear naturally in computation. We show that a rich computability theory can be developed for these functions classes which embraces the central results of classical computability theory, in which all partial (computable) functions are considered. To do so, the concept of a Gödel number is generalised, resulting in a broader class of numberings. The central algorithmic idea in this approach is to search in enumerated lists. In this way, function computability is reduced to set listability. Besides the development of a computability theory for the functions classes, the new numberings -- called quasi-Gödel numberings -- are studied from a numbering-theoretic perspective: they are complete, and each of the function classes numbered in this way is a retract of the Gödel numbered set of all partial computable functions. Moreover, the Rogers semi-lattice of all computable numberings of the considered function classes is studied and results as in the case of the computable numberings of the partial computable functions are obtained. The function classes are shown to be effectively given algebraic domains in the sense of Scott-Ershov. The quasi-Gödel numberings are exactly the admissible numberings of the computable elements of the domain. Moreover, the domain can be computably mapped onto every other effectively given one so that every admissible numbering of the computable domain elements is generated by a quasi-Gödel numbering via this mapping.
Cited by 0Open access
Allen H. Brady · 1965
Cited by 1
Peter Hertling, Christoph Spandl · Logical Methods in Computer Science · 2014
Lanford has shown that Feigenbaum's functional equation has an analytic solution. We show that this solution is a polynomial time computable function. This implies in particular that the so-called first Feigenbaum constant is a polynomial time computable real number.
Cited by 2Open access
Timothy H. McNicholl · LMS Journal of Computation and Mathematics · 2014
Abstract We show that a computable and conformal map of the unit disk onto a bounded domain $\def \xmlpi #1{}\def \mathsfbi #1{\boldsymbol {\mathsf {#1}}}\let \le =\leqslant \let \leq =\leqslant \let \ge =\geqslant \let \geq =\geqslant \def \Pr {\mathit {Pr}}\def \Fr {\mathit {Fr}}\def \Rey {\mathit {Re}}D$ has a computable boundary extension if $D$ has a computable boundary connectivity function.
Cited by 3Open access
Antony Van der Mude · arXiv (Cornell University) · 2013
We define a class of functions termed "Computable in the Limit", based on the Machine Learning paradigm of "Identification in the Limit". A function is Computable in the Limit if it defines a property P_p of a recursively enumerable class A of recursively enumerable data sequences S in A, such that each data sequence S is generated by a total recursive function s that enumerates . Let the index s represent the data sequence S. The property P_p(s)=x is computed by a partial recursive function f_p(s,t) such that there exists a u where f_p(s,u)=x and for all t>=u, f_p(s,t)=x if it converges. Since the index s is known, this is not an identification problem - instead it is computing a common property of the sequences in A. We give a Normal Form Theorem for properties that are Computable in the Limit, similar to Kleene's Normal Form Theorem. We also give some examples of sets that are Computable in the Limit, and derive some properties of Canonical and Complexity Bound Enumerations of classes of total functions, and show that no full enumeration of all indices of Turing machines TM_i that compute a given total function can be Computable in the Limit.
Cited by 0Open access
Dawit Tirore, Jesper Bengtson, Marco Carbone · Journal of Automated Reasoning · 2025
Abstract Multiparty session types is a typing discipline used to write specifications, known as global types, for branching and recursive message-passing systems. A necessary operation on global types is projection to abstractions of local behaviour, called local types. Typically, this is a computable partial function that given a global type and a role erases all details irrelevant to this role. Computable projection functions in the literature are either unsound or too restrictive when dealing with recursion and branching. Recent work has taken a more general approach to projection defining it as a coinductive, but not computable, relation. Our work defines a new computable projection function that is sound and complete with respect to its coinductive counterpart and, hence, equally expressive. All results have been mechanised in the Coq proof assistant.
Cited by 2Open access