Apoloniusz Tyszka · 2024
The theorem of Royer and Case states that there exists a limit-computable function β_1:N→N which eventually dominates every computable function δ_1:N→N. We present an alternative proof of this theorem. 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. The statement ¬K(P≠NP)∧¬K(P=NP) does not justify the title of the article. We prove: (1) there exists a limit-computable function f:N→N of unknown computability which eventually dominates every function δ:N→N with a single-fold Diophantine representation; (2) for every computable functions g:N→N, there exists a limit-computable function f:N→N of unknown computability such that f eventually dominates every function δ:N→N with a single-fold Diophantine representation and f(n)>g(n) for every n∈N. Both (1) and (2) justify the title of the article.
Cited by 0Open access
Avigad, Jeremy · arXiv (Cornell University) · 2011
V'yugin has shown that there are a computable shift-invariant measure on Cantor space 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 epsilon.
Cited by 0Open access
Jockusch, Carl G., Schupp, Paul E. · arXiv (Cornell University) · 2010
Generic computability has been studied in group theory and we now study it in the context of classical computability theory. A set A of natural numbers is generically computable if there is a partial computable function f whose domain has density 1 and which agrees with the characteristic function of A on its domain. A set A is coarsely computable if there is a computable set C such that the symmetric difference of A and C has density 0. We prove that there is a c.e. set which is generically computable but not coarsely computable and vice versa. We show that every nonzero Turing degree contains a set which is not coarsely computable. We prove that there is a c.e. set of density 1 which has no computable subset of density 1. As a corollary, there is a generically computable set A such that no generic algorithm for A has computable domain. We define a general notion of generic reducibility in the spirt of Turing reducibility and show that there is a natural order-preserving embedding of the Turing degrees into the generic degrees which is not surjective.
Cited by 0Open access
Nathanael Ackerman, Julian Asilis, Jieqi Di et al. · arXiv (Cornell University) · 2021
We introduce definitions of computable PAC learning for binary classification over computable metric spaces. We provide sufficient conditions for learners that are empirical risk minimizers (ERM) to be computable, and bound the strong Weihrauch degree of an ERM learner under more general conditions. We also give a presentation of a hypothesis class that does not admit any proper computable PAC learner with computable sample function, despite the underlying class being PAC learnable.
Cited by 0Open access
2008
We study the computational complexity of the distance function associated with a polynomial-time computable two-dimensional domains, in the context of the Turing machine-based complexity theory of real functions. It is proved that the distance function is not necessarily computable even if a two-dimensional domain is polynomial-time recognizable. On the other hand, if both the domain and its complement are strongly polynomial-time recognizable, then the distance function is polynomial-time computable if and only if P = NP. 1
Cited by 0
Hiroyasu Kamo · Electronic Notes in Theoretical Computer Science · 2005
We show that if a computable sequence of real-valued functions on an effectively compact metric space converges pointwise monotonically to a computable function, then the sequence converges effectively uniformly to the function. This is an effectivized version of Dini's Theorem.
Cited by 7Open access
Karol Duda · arXiv (Cornell University) · 2021
We prove a computable version of the Hall Harem Theorem where the matching realizes a unary function with controlled sizes of cycles. We apply it to non-amenable computable coarse spaces. As a result, we obtain a computable version of the geometric von Neumann conjecture.
Cited by 0Open access
Apoloniusz Tyszka · SHILAP Revista de lepidopterología · 2013
Let En ={xi = 1; xi + xj = xk; xi ∙ xj = xk : i; j; k ∊ {1;. . . ; n}}. We present two algorithms. The first accepts as input any computable function f : ℕ → ℕ and returns a positive integer m( f ) and a computable function g which to each integer n ≥ m( f ) assigns a system S ⊆ En such that S is satisfiable over integers and each integer tuple (x1;. . .; xn) that solves S satisfies x1 = f (n). The second accepts as input any computable function f: ℕ → ℕ and returns a positive integer w( f ) and a computable function h which to each integer n ≥ w( f ) assigns a system S ⊆ En such that S is satisfiable over non-negative integers and each tuple (x1;. . .; xn) of non-negative integers that solves S satisfies x1 = f (n).
Cited by 1Open access
Xiangfeng Zheng, Robert Rettinger, Burchard von Braunmühl · 2003
The classical Jordan decomposition Theorem says that any real function of bounded variation can be expressed as a difference of two increasing functions. This paper explores the effective version of Jordan decomposition. We give a sufficient and necessary condition for those computable real functions of bounded variation which can be expressed as a difference of two computable increasing functions. Using this condition, we prove further that there is a computable real function which has even a computable modulus of absolute continuity (hence is of bounded variation) but it is not a difference of any two computable increasing functions. The polynomial time version of this result holds too and this gives a negative answer to an open question of Ko in [6].
Cited by 0
S.A. Nigiyan · Proceedings of the YSU A Physical and Mathematical Sciences · 2016
In this paper the arithmetical functions with indeterminate values of arguments are regarded. It is known that every $\lambda$-definable arithmetical function with indeterminate values of arguments is monotonic and computable. The $\lambda$-definability of every computable, monotonic, 1-ary arithmetical function with indeterminate values of arguments is proved. For computable, monotonic, $k$-ary, $k \geq 2$, arithmetical functions with indeterminate values of arguments, the so-called diagonal property is defined. It is proved that every computable, monotonic, $k$-ary, $k \geq 2$, arithmetical function with indeterminate values of arguments, which has the diagonal property, is not $\lambda$-definable. It is proved that for any $k \geq 2$; the problem of $\lambda$-definability for computable, monotonic, $k$-ary arithmetical functions with indeterminate values of arguments is algorithmic unsolvable. It is also proved that the problem of diagonal property of such functions is algorithmic unsolvable, too.
Cited by 0Open access
Xizhong Zheng, Robert Rettinger, George Barmpalias · Mathematical logic quarterly · 2005
Let h : ℕ → ℚ be a computable function. A real number x is called h-monotonically computable (h-mc, for short) if there is a computable sequence (xs) of rational numbers which converges to x h-monotonically in the sense that h(n)|x – xn| ≥ |x – xm| for all n andm > n. In this paper we investigate classes h-MC of h-mc real numbers for different computable functions h. Especially, for computable functions h : ℕ → (0, 1)ℚ, we show that the class h-MC coincides with the classes of computable and semi-computable real numbers if and only if Σi∈ℕ(1 – h(i)) = ∞and the sum Σi∈ℕ(1 – h(i)) is a computable real number, respectively. On the other hand, if h(n) ≥ 1 and h converges to 1, then h-MC = SC (the class of semi-computable reals) no matter how fast h converges to 1. Furthermore, for any constant c > 1, if h is increasing and converges to c, then h-MC = c-MC. Finally, if h is monotone and unbounded, then h-MC contains all ω-mc real numbers which are g-mc for some computable function g. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)
Cited by 2
2006
This paper studies the notion of Lebesgue integrable computable functions (denoted L p-computable where p is an integer), that naturally extends the classical model of bitcomputable functions. We introduce L p-computable Baire categories. We observe that L p-computability is incomparable to the recently introduced notion of graph-computable functions. We study the convergence of Fourier series for L p-computable functions and show that whereas for every p> 1, the Fourier series of every L p-computable function f converges to f in the L p norm, the set of L 1-computable functions whose Fourier series does not diverge almost everywhere is meager. 1
Cited by 0
Kurt Ammon · arXiv (Cornell University) · 2013
We give an effective procedure that produces a natural number in its output from any natural number in its input, that is, it computes a total function. The elementary operations of the procedure are Turing-computable. The procedure has a second input which can contain the Goedel number of any Turing-computable total function whose range is a subset of the set of the Goedel numbers of all Turing-computable total functions. We prove that the second input cannot be set to the Goedel number of any Turing-computable function that computes the output from any natural number in its first input. In this sense, there is no Turing program that computes the output from its first input. The procedure is used to define creative procedures which compute functions that are not Turing-computable. We argue that creative procedures model an aspect of reasoning that cannot be modeled by Turing machines.
Cited by 0Open access
Xizhong Zheng, Vasco Brattka, Klaus Weihrauch · Mathematical logic quarterly · 1999
Abstract For semi‐continuous real functions we study different computability concepts defined via computability of epigraphs and hypographs. We call a real function f lower semi‐computable of type one, if its open hypograph hypo( f ) is recursively enumerably open in dom( f ) × ℝ; we call f lower semi‐computable of type two, if its closed epigraph Epi( f ) is recursively enumerably closed in dom( f ) × ℝ; we call f lower semi‐computable of type three, if Epi( f ) is recursively closed in dom( f ) × ℝ. We show that type one and type two semi‐computability are independent and that type three semi‐computability plus effectively uniform continuity implies computability, which is false for type one and type two instead of type three. We show also that the integral of a type three semi‐computable real function on a computable interval is not necessarily computable.
Cited by 6
Rutger Kuyper, Sebastiaan A. Terwijn · arXiv (Cornell University) · 2013
We prove that a real x is 1-generic if and only if every differentiable computable function has continuous derivative at x. This provides a counterpart to recent results connecting effective notions of randomness with differentiability. We also consider multiply differentiable computable functions and polynomial time computable functions.
Cited by 0Open access
Apoloniusz Tyszka · 2025
For n∈N, f(n) denotes the smallest b∈N such that if a system of equations S⊆{1=x_k, x_i+x_j=x_k, x_i·x_j=x_k: i,j,k∈{0,...,n}} has a solution in N^{n+1}, then S has a solution in {0,...,b}^{n+1}. The author proved earlier that the function f:N→N is computable in the limit and eventually dominates every computable function g:N→N. We present a simple code in MuPAD which for n∈N prints the sequence {f_i(n)}_{i=0}^∞ of non-negative integers converging to f(n). For n∈N, h(n) denotes the smallest b∈N such that if a system of equations S⊆{x_i+1=x_k, x_i·x_j=x_k: i,j,k∈{0,...,n}} has a solution in N^{n+1}, then S has a solution in {0,...,b}^{n+1}. The function h:N→N is computable in the limit and eventually dominates every computable function g:N→N. A bit shorter code in MuPAD computes h in the limit. It establishes the most effective proof that there exists a non-computable function from N to N.
Cited by 0Open access
Johanna N. Y. Franklin, Lucas Rodríguez, Diego A. Rojas · ArXiv.org · 2026
Within the last fifteen years, a program of establishing relationships between algorithmic randomness and almost-everywhere theorems in analysis and ergodic theory has developed. In harmonic analysis, Franklin, McNicholl, and Rute characterized Schnorr randomness using an effective version of Carleson's Theorem. We show here that, for computable $1<p<\infty$, the reals at which the Fourier series of a weakly computable vector in $L^p[-π,π]$ converges are precisely the Martin-Löf random reals. Furthermore, we show that radial limits of the Poisson integral of an $L^1(\mathbb{R})$-computable function coincide with the values of the function at exactly the Schnorr random reals and that radial limits of the Poisson integral of a weakly $L^1(\mathbb{R})$-computable function coincide with the values of the function at exactly the Martin-Löf random reals.
Cited by 0Open access
Khoussainov, B, Kowalski, T · ResearchSpace (University of Auckland) · 2002
One of the central topics in computable algebra and model theory is concerned with the study of computable isomorphisms. Classically, we do not distinguish between isomorphic structures, however, from computability point of view, isomorphic structures can differ quite dramatically. A typical example is provided by the linear order of type ω. It has two computable copies such that in one the successor function is computable, but it is not computable in the other. These are clearly classically isomorphic, but they are not computably isomorphic.
Cited by 0Open access
Tian Wu, Mengbo Zhang, Xunmin Ou · Energies · 2014
This paper presents a model for the projection of Chinese vehicle stocks and road vehicle energy demand through 2050 based on low-, medium-, and high-growth scenarios. To derive a gross-domestic product (GDP)-dependent Gompertz function, Chinese GDP is estimated using a recursive dynamic Computable General Equilibrium (CGE) model. The Gompertz function is estimated using historical data on vehicle development trends in North America, Pacific Rim and Europe to overcome the problem of insufficient long-running data on Chinese vehicle ownership. Results indicate that the number of projected vehicle stocks for 2050 is 300, 455 and 463 million for low-, medium-, and high-growth scenarios respectively. Furthermore, the growth in China’s vehicle stock will increase beyond the inflection point of Gompertz curve by 2020, but will not reach saturation point during the period 2014–2050. Of major road vehicle categories, cars are the largest energy consumers, followed by trucks and buses. Growth in Chinese vehicle demand is primarily determined by per capita GDP. Vehicle saturation levels solely influence the shape of the Gompertz curve and population growth weakly affects vehicle demand. Projected total energy consumption of road vehicles in 2050 is 380, 575 and 586 million tonnes of oil equivalent for each scenario.
Cited by 43Open access
Prof Dr, Thomas Streicher · 2002
For knowing that a function f: Nk → N is computable one does not need a definition of what is computable in principle simply because one recognizes an algorithm whenever one sees it.1 However, for showing that f is not computable one definitly has to delineate a priori the collection of functions
Cited by 0