We consider two classical computability notions for functions mapping all computable real numbers to computable real numbers. It is clear that any function that is computable in the sense of Markov, i.e., computable with respect to a standard Gödel numbering of the computable real numbers, is computable in the sense of Banach and Mazur, i.e., it maps any computable sequence of real numbers to a computable sequence of real numbers. We show (...) that the converse is not true. This solves a long-standing open problem posed by Kushner. (shrink)

We prove two embedding and extension theorems in the context of the constructive theory of metric spaces. The first states that Cantor space embeds in any inhabited complete separable metric space without isolated points, X, in such a way that every sequentially continuous function from Cantor space to ℤ extends to a sequentially continuous function from X to ℝ. The second asserts an analogous property for Baire space relative to any inhabited locally non-compact CSM. Both results rely on (...) having careful constructive formulations of the concepts involved.As a first application, we derive new relationships between “continuity principles” asserting that all functions between specified metric spaces are pointwise continuous. In particular, we give conditions that imply the failure of the continuity principle “all functions from X to ℝ are continuous”, when X is an inhabited CSM without isolated points, and when X is an inhabited locally non-compact CSM. One situation in which the latter case applies is in models based on “domain realizability”, in which the failure of the continuity principle for any inhabited locally non-compact CSM, X, generalizes a result previously obtained by Escardó and Streicher in the special case X = C[0, 1].As a second application, we show that, when the notion of inhabited complete separable metric space without isolated points is interpreted in a recursion-theoretic setting, then, for any such space X, there exists a Banach-Mazur computable function from X to the computable real numbers that is not Markov computable. This generalizes a result obtained by Hertling in the special case that X is the space of computable real numbers. (shrink)

We prove two embedding and extension theorems in the context of the constructive theory of metric spaces. The first states that Cantor space embeds in any inhabited complete separable metric space (CSM) without isolated points, X, in such a way that every sequentially continuous function from Cantor space to ℤ extends to a sequentially continuous function from X to ℝ. The second asserts an analogous property for Baire space relative to any inhabited locally non‐compact CSM. Both results rely (...) on having careful constructive formulations of the concepts involved.As a first application, we derive new relationships between “continuity principles” asserting that all functions between specified metric spaces are pointwise continuous. In particular, we give conditions that imply the failure of the continuity principle “all functions from X to ℝ are continuous”, when X is an inhabited CSM without isolated points, and when X is an inhabited locally non‐compact CSM. One situation in which the latter case applies is in models based on “domain realizability”, in which the failure of the continuity principle for any inhabited locally non‐compact CSM, X, generalizes a result previously obtained by Escardó and Streicher in the special case X = C[0, 1].As a second application, we show that, when the notion of inhabited complete separable metric space without isolated points is interpreted in a recursion‐theoretic setting, then, for any such space X, there exists a Banach‐Mazur computable function from X to the computable real numbers that is not Markov computable. This generalizes a result obtained by Hertling in the special case that X is the space of computable real numbers. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)

In this paper we give an axiomatisation of the concept of a computability structure with partial sequences on a many‐sorted metric partial algebra, thus extending the axiomatisation given by Pour‐El and Richards in [9] for Banach spaces. We show that every Banach‐Mazur computable partial function from an effectively separable computable metric partial Σ‐algebraAto a computable metric partial Σ‐algebraBmust be continuous, and conversely, that every effectively continuous partial function with semidecidable domain and which preserves the (...) computability of a computably enumerable dense set must be computable. Finally, as an application of these results we give an alternative proof of the first main theorem for Banach spaces first proved by Pour‐El and Richards. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)

In this paper we give an axiomatisation of the concept of a computability structure with partial sequences on a many-sorted metric partial algebra, thus extending the axiomatisation given by Pour-El and Richards in [9] for Banach spaces. We show that every Banach-Mazur computable partial function from an effectively separable computable metric partial Σ-algebra A to a computable metric partial Σ-algebra B must be continuous, and conversely, that every effectively continuous partial function with semidecidable domain and (...) which preserves the computability of a computably enumerable dense set must be computable. Finally, as an application of these results we give an alternative proof of the first main theorem for Banach spaces first proved by Pour-El and Richards. (shrink)

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 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 } 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. (shrink)

R. M. Friedberg demonstrated the existence of a recursive functional that agrees with no Banach-Mazur functional on the class of recursive functions. In this paper Friedberg's result is generalized to both α-recursive functionals and weak α-recursive functionals for all admissible ordinals α such that $\lambda , where α * is the Σ 1 -projectum of α and λ is the Σ 2 -cofinality of α. The theorem is also established for the metarecursive case, α = ω 1 , where α (...) * = λ = ω. (shrink)

We prove two embedding and extension theorems in the context of the constructive theory of metric spaces. The first states that Cantor space embeds in any inhabited complete separable metric space (CSM) without isolated points, X, in such a way that every sequentially continuous function from Cantor space to ℤ extends to a sequentially continuous function from X to ℝ. The second asserts an analogous property for Baire space relative to any inhabited locally non‐compact CSM. Both results rely (...) on having careful constructive formulations of the concepts involved.As a first application, we derive new relationships between “continuity principles” asserting that all functions between specified metric spaces are pointwise continuous. In particular, we give conditions that imply the failure of the continuity principle “all functions from X to ℝ are continuous”, when X is an inhabited CSM without isolated points, and when X is an inhabited locally non‐compact CSM. One situation in which the latter case applies is in models based on “domain realizability”, in which the failure of the continuity principle for any inhabited locally non‐compact CSM, X, generalizes a result previously obtained by Escardó and Streicher in the special case X = C[0, 1].As a second application, we show that, when the notion of inhabited complete separable metric space without isolated points is interpreted in a recursion‐theoretic setting, then, for any such space X, there exists a Banach‐Mazur computable function from X to the computable real numbers that is not Markov computable. This generalizes a result obtained by Hertling in the special case that X is the space of computable real numbers. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)

A notion of resource-bounded Baire category is developed for the class PC[0,1] of all polynomial-time computable real-valued functions on the unit interval. The meager subsets of PC[0,1] are characterized in terms of resource-bounded Banach-Mazur games. This characterization is used to prove that, in the sense of Baire category, almost every function in PC[0,1] is nowhere differentiable. This is a complexity-theoretic extension of the analogous classical result that Banach proved for the class C[0, 1] in 1931.

A notion of resource‐bounded Baire category is developed for the classPC[0,1]of all polynomial‐time computable real‐valued functions on the unit interval. The meager subsets ofPC[0,1]are characterized in terms of resource‐bounded Banach‐Mazur games. This characterization is used to prove that, in the sense of Baire category, almost every function inPC[0,1]is nowhere differentiable. This is a complexity‐theoretic extension of the analogous classical result that Banach proved for the classC[0, 1] in 1931. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim).

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)

We develop some parts of the theory of compact operators from the point of view of computable analysis. While computable compact operators on Hilbert spaces are easy to understand, it turns out that these operators on Banach spaces are harder to handle. Classically, the theory of compact operators on Banach spaces is developed with the help of the non-constructive tool of sequential compactness. We demonstrate that a substantial amount of this theory can be developed computably on Banach spaces (...) with computable Schauder bases that are well-behaved. The conditions imposed on the bases are such that they generalize the Hilbert space case. In particular, we prove that the space of compact operators on Banach spaces with monotone, computably shrinking, and computable bases is a computable Banach space itself and operations such as composition with bounded linear operators from left are computable. Moreover, we provide a computable version of the Theorem of Schauder on adjoints in this framework and we discuss a non-uniform result on composition with bounded linear operators from right. (shrink)

An alternative proof is given that to each LLM proof net there corresponds at least one LLM sequent proof. The construction is inspired by the sweepline technique from computational geometry and includes a treatment of the multiplicative constants and of proof boxes.

The classical Hahn–Banach Theorem states that any linear bounded functional defined on a linear subspace of a normed space admits a norm-preserving linear bounded extension to the whole space. The constructive and computational content of this theorem has been studied by Bishop, Bridges, Metakides, Nerode, Shore, Kalantari Downey, Ishihara and others and it is known that the theorem does not admit a general computable version. We prove a new computable version of this theorem without unrolling the classical proof (...) of the theorem itself. More precisely, we study computability properties of the uniform extension operator which maps each functional and subspace to the set of corresponding extensions. It turns out that this operator is upper semi-computable in a well-defined sense. By applying a computable version of the Banach–Alaoglu Theorem we can show that computing a Hahn–Banach extension cannot be harder than finding a zero in a compact metric space. This allows us to conclude that the Hahn–Banach extension operator is ${\bf {\Sigma^{0}_{2}}}$ -computable while it is easy to see that it is not lower semi-computable in general. Moreover, we can derive computable versions of the Hahn–Banach Theorem for those functionals and subspaces which admit unique extensions. (shrink)

The aim of the article is to present the application of the lean management method as appropriate for the management of the organizational system of psychiatric care in the Zealand region of Denmark. The organizational solutions of the Danish psychiatric care system presented in this paper are individualized and adapted to the regional needs of the residents. In Denmark, there are five administrative regions, in which each independently organizes its own system of medical (psychiatric) care. This means that the regions (...) have considerable independence in choosing the acceptable and necessary methods of management, including – as is clear from the conducted research – the use of methods put-upon other areas of economy. Although the national laws in Denmark define certain conditions and guidelines for the functioning of psychiatric care (e.g. regarding the use of direct coercion/restrains for patients treated in the centres), there is a distinct separation of structures and methods of functioning throughout the whole country, which constitutes unique observation material – from the cognitive point of view. The authors of this paper conduct extensive research and analyse the systems of psychiatric care organizations in various countries (including Spain, Italy and Japan) and, as a result, the obtained results may lead to the selection of the best models from other systems (good organizational practices and management, the management methods in use), which can be applied in the currently reorganised system of the Polish psychiatric care. The choice of Denmark for the observational study is not accidental and is related not only to the fact that there is a large degree of systemic identity within the country and between the regions, but also because the country applies solutions addressed to patients with very different cultural conditions and needs, resulting from their descent, religion, and (world)-views. Denmark is one of those European countries that express a significant acceptance of diversity and tolerance, which is why communities with very different imponderables, denominations, and worldviews co-exist. In the area related to the organization of the psychiatric system, these conditions are of key importance. In the period from January 2015 to December 2017 the authors participated in study visits in Denmark, conducting research aimed at identifying the key success factors of the psychiatric care organization system in the country. The conducted analysis is also based on the analysis of literature and own and participant observations. The conclusions concerning this subject are also the result of interviews conducted with employees of the visited hospitals and system users, both professionals and patients. As the search for an optimal organizational model of psychiatric care is currently an ongoing concern in Poland, it seems justified to review the existing solutions in Europe and perform their critical analysis. A comparison of the adopted solutions was performed, in the context of, above all, the improvement of the quality of these services, their availability, and the satisfaction of patients and their families from the proposed organizational changes. The economic benefits of these solutions are also significant. (shrink)

The title question of the paper has its empirical origin in the form of an individual’s existential experience arising from the personal use of a computer, which we attempt to describe in the first section. The rest of the entire paper can be understood as a philosophical essay answering the question posed. First the connection between the main problem of the article and its “premonition” by mankind, which was expressed in the form of ancient myths and legends, is briefly suggested. (...) After shortly discussing the problems that early considerations of AI focused on, i.e. whether machines can think at all, we move on to reformulate our title question, about the possibility of outsmarting AI. This outsmarting will be understood by us in a rather limited way as to prevent a machine from completing its implemented task. To achieve this objective, after softly clarifying the basic terms, an analogy is built between the “outsmarting” of a machine by a human (the target domain) and the playing of a mathematical game between two players (the base domain), where this outsmarting is assigned a “winning strategy” in the certain game. This mathematical model is formed by games similar to Banach-Mazur games. The strict theorems of such games are then proved and applied to the target of the analogy. We then draw conclusions and look for counter-examples to our findings. The answer to the title question posed is negative, and it is not clear how far it should be taken seriously. (shrink)

We determine the computational complexity of the Hahn-Banach Extension Theorem. To do so, we investigate some basic connections between reverse mathematics and computable analysis. In particular, we use Weak König's Lemma within the framework of computable analysis to classify incomputable functions of low complexity. By defining the multivalued function Sep and a natural notion of reducibility for multivalued functions, we obtain a computational counterpart of the subsystem of second-order arithmetic WKL0. We study analogies and differences between WKL0 (...) and the class of Sep-computable multivalued functions. Extending work of Brattka, we show that a natural multivalued function associated with the Hahn-Banach Extension Theorem is Sep-complete. (shrink)

We study theorems from Functional Analysis with regard to their relationship with various weak choice principles and prove several results about them: “Every infinite‐dimensional Banach space has a well‐orderable Hamel basis” is equivalent to ; “ can be well‐ordered” implies “no infinite‐dimensional Banach space has a Hamel basis of cardinality ”, thus the latter statement is true in every Fraenkel‐Mostowski model of ; “No infinite‐dimensional Banach space has a Hamel basis of cardinality ” is not provable in ; “No infinite‐dimensional (...) Banach space has a well‐orderable Hamel basis of cardinality ” is provable in ; (the Axiom of Choice for denumerable families of non‐empty finite sets) is equivalent to “no infinite‐dimensional Banach space has a Hamel basis which can be written as a denumerable union of finite sets”; Mazur's Lemma (“If X is an infinite‐dimensional Banach space, Y is a finite‐dimensional vector subspace of X, and, then there is a unit vector such that for all and all scalars α”) is provable in ; “A real normed vector space X is finite‐dimensional if and only if its closed unit ball is compact” is provable in ; (Principle of Dependent Choices) + “ can be well‐ordered” does not imply the Hahn‐Banach Theorem () in ; and “no infinite‐dimensional Banach space has a Hamel basis of cardinality ” are independent from each other in ; “No infinite‐dimensional Banach space can be written as a denumerable union of finite‐dimensional subspaces” lies in strength between (the Axiom of Countable Choice) and ; implies “No infinite‐dimensional Banach space can be written as a denumerable union of closed proper subspaces” which in turn implies ; “Every infinite‐dimensional Banach space has a denumerable linearly independent subset” is a theorem of, but not a theorem of ; and “Every infinite‐dimensional Banach space has a linearly independent subset of cardinality ” implies “every Dedekind‐finite set is finite”. (shrink)

The investigation of computational properties of discontinuous functions is an important concern in computable analysis. One method to deal with this subject is to consider effective variants of Borel measurable functions. We introduce such a notion of Borel computability for single-valued as well as for multi-valued functions by a direct effectivization of the classical definition. On Baire space the finite levels of the resulting hierarchy of functions can be characterized using a notion of reducibility for functions and corresponding complete (...) functions. We use this classification and an effective version of a Selection Theorem of Bhattacharya-Srivastava in order to prove a generalization of the Representation Theorem of Kreitz-Weihrauch for Borel measurable functions on computable metric spaces: such functions are Borel measurable on a certain finite level, if and only if they admit a realizer on Baire space of the same quality. This Representation Theorem enables us to introduce a realizer reducibility for functions on metric spaces and we can extend the completeness result to this reducibility. Besides being very useful by itself, this reducibility leads to a new and effective proof of the Banach-Hausdorff-Lebesgue Theorem which connects Borel measurable functions with the Baire functions. Hence, for certain metric spaces the class of Borel computable functions on a certain level is exactly the class of functions which can be expressed as a limit of a pointwise convergent and computable sequence of functions of the next lower level. (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)

We analyse the connection between the computability and continuity of functions in the case of homomorphisms between topological algebraic structures. Inspired by the Pour-El and Richards equivalence theorem between computability and boundedness for closed linear operators on Banach spaces, we study the rather general situation of partial homomorphisms between metric partial universal algebras. First, we develop a set of basic notions and results that reveal some of the delicate algebraic, topological and effective properties of partial algebras. Our main computability concepts (...) are based on numerations and include those of effective metric partial algebras and effective partial homomorphisms. We prove a general equivalence theorem that includes a version of the Pour-El and Richards Theorem, and has other applications. Finally, the Pour-El and Richards axioms for computable sequence structures on Banach spaces are generalised to computable partial sequence structures on metric algebras, and we prove their equivalence with our computability model based on numerations. (shrink)

We analyse the connection between the computability and continuity of functions in the case of homomorphisms between topological algebraic structures. Inspired by the Pour-El and Richards equivalence theorem between computability and boundedness for closed linear operators on Banach spaces, we study the rather general situation of partial homomorphisms between metric partial universal algebras. First, we develop a set of basic notions and results that reveal some of the delicate algebraic, topological and effective properties of partial algebras. Our main computability concepts (...) are based on numerations and include those of effective metric partial algebras and effective partial homomorphisms. We prove a general equivalence theorem that includes a version of the Pour-El and Richards Theorem, and has other applications. Finally, the Pour-El and Richards axioms for computable sequence structures on Banach spaces are generalised to computable partial sequence structures on metric algebras, and we prove their equivalence with our computability model based on numerations. (shrink)

In this paper we study a reducibility that has been introduced by Klaus Weihrauch or, more precisely, a natural extension for multi-valued functions on represented spaces. We call the corresponding equivalence classes Weihrauch degrees and we show that the corresponding partial order induces a lower semi-lattice. It turns out that parallelization is a closure operator for this semi-lattice and that the parallelized Weihrauch degrees even form a lattice into which the Medvedev lattice and the Turing degrees can be embedded. The (...) importance of Weihrauch degrees is based on the fact that multi-valued functions on represented spaces can be considered as realizers of mathematical theorems in a very natural way and studying the Weihrauch reductions between theorems in this sense means to ask which theorems can be transformed continuously or computably into each other. As crucial corner points of this classification scheme the limited principle of omniscience LPO, the lesser limited principle of omniscience LLPO and their parallelizations are studied. It is proved that parallelized LLPO is equivalent to Weak Kőnig's Lemma and hence to the Hahn—Banach Theorem in this new and very strong sense. We call a multi-valued function weakly computable if it is reducible to the Weihrauch degree of parallelized LLPO and we present a new proof, based on a computational version of Kleene's ternary logic, that the class of weakly computable operations is closed under composition. Moreover, weakly computable operations on computable metric spaces are characterized as operations that admit upper semi-computable compact-valued selectors and it is proved that any single-valued weakly computable operation is already computable in the ordinary sense. (shrink)

We present a survey of the recent applications of continuous domains for providing simple computational models for classical spaces in mathematics including the real line, countably based locally compact spaces, complete separable metric spaces, separable Banach spaces and spaces of probability distributions. It is shown how these models have a logical and effective presentation and how they are used to give a computational framework in several areas in mathematics and physics. These include fractal geometry, where new results on existence and (...) uniqueness of attractors and invariant distributions have been obtained, measure and integration theory, where a generalization of the Riemann theory of integration has been developed, and real arithmetic, where a feasible setting for exact computer arithmetic has been formulated. We give a number of algorithms for computation in the theory of iterated function systems with applications in statistical physics and in period doubling route to chaos; we also show how efficient algorithms have been obtained for computing elementary functions in exact real arithmetic. (shrink)

It was proved recently that Telgársky’s conjecture, which concerns partial information strategies in the Banach–Mazur game, fails in models of \. The proof introduces a combinatorial principle that is shown to follow from \, namely: \::Every separative poset \ with the \-cc contains a dense sub-poset \ such that \ for every \. We prove this principle is independent of \ and \, in the sense that \ does not imply \, and \ does not imply \ assuming the consistency (...) of a huge cardinal. We also consider the more specific question of whether \ holds with \ equal to the weight-\ measure algebra. We prove, again assuming the consistency of a huge cardinal, that the answer to this question is independent of \. (shrink)

This book is dedicated to a classic presentation of the theory of computable functions in the context of the foundations of mathematics. Part I motivates the study of computability with discussions and readings about the crisis in the foundations of mathematics in the early 20th century, while presenting the basic ideas of whole number, function, proof, and real number. Part II starts with readings from Turing and Post leading to the formal theory of recursive functions. Part III presents (...) sufficient formal logic to give a full development of Gödel's incompleteness theorems. Part IV considers the significance of the technical work with a discussion of Church's Thesis and readings on the foundations of mathematics. This new edition contains the timeline "Computability and Undecidability" as well as the essay "On mathematics". (shrink)

Let S be the set of those α ∈ ω₂ that have cofinality ω₁. It is consistent relative to a measurable that the nonempty player wins the pressing down game of length ω₁, but not the Banach-Mazur game of length ω + 1 (both games starting with S).

Inspired from a joint work by A. Beckmann, S. Buss and S. Friedman, we propose a class of set-theoretic functions, predicatively computable set functions. Each function in this class is polynomial time computable when we restrict to finite binary strings.

Quantum mechanical measurements on a physical system are represented by observables - Hermitian operators on the state space of the observed system. It is an important question whether all observables may be realized, in principle, as measurements on a physical system. Dirac’s influential text ( [1], page 37) makes the following assertion on the question: The question now presents itself – Can every observable be measured? The answer theoretically is yes. In practice it may be very awkward, or perhaps even (...) beyond the ingenuity of the experimenter, to devise an apparatus which could measure some particular observable, but the theory always allows one to imagine that the measurement can be made. This Letter re-examines the question of whether it is possible, even in principle, to measure every quantum mechanical observable. Unexpectedly, ideas from com-. (shrink)

"A valuable collection both for original source material as well as historical formulations of current problems."-- The Review of Metaphysics "Much more than a mere collection of papers . . . a valuable addition to the literature."-- Mathematics of Computation An anthology of fundamental papers on undecidability and unsolvability by major figures in the field, this classic reference opens with Godel's landmark 1931 paper demonstrating that systems of logic cannot admit proofs of all true assertions of arithmetic. Subsequent papers by (...) Godel, Church, Turing, and Post single out the class of recursive functions as computable by finite algorithms. Additional papers by Church, Turing, and Post cover unsolvable problems from the theory of abstract computing machines, mathematical logic, and algebra, and material by Kleene and Post includes initiation of the classification theory of unsolvable problems. Suitable for graduate and undergraduate courses. 1965 ed. (shrink)

Horsten and Roelants have raised a number of important questions about my analysis of effective procedures and my evaluation of the Church-Turing thesis. They suggest that, on my account, effective procedures cannot enter the mathematical world because they have a built-in component of causality, and, hence, that my arguments against the Church-Turing thesis miss the mark. Unfortunately, however, their reasoning is based upon a number of misunderstandings. Effective mundane procedures do not, on my view, provide an analysis of ourgeneral concept (...) of an effective procedure; mundane procedures and Turing machine procedures are different kinds of procedure. Moreover, the same sequence ofparticular physical action can realize both a mundane procedure and a Turing machine procedure; it is sequences of particular physical actions, not mundane procedures, which enter the world of mathematics. I conclude by discussing whether genuinely continuous physical processes can enter the world of real numbers and compute real-valued functions. I argue that the same kind of correspondence assumptions that are made between non-numerical structures and the natural numbers, in the case of Turing machines and personal computers, can be made in the case of genuinely continuous, physical processes and the real numbers. (shrink)

As is well known the derivative of a computable and C1 function may not be computable. For a computable and C∞ function f, the sequence {f} of its derivatives may fail to be computable as a sequence, even though its derivative of any order is computable. In this paper we present a necessary and sufficient condition for the sequence {f} of derivatives of a computable and C∞ function f to be (...) class='Hi'>computable. We also give a sharp regularity condition on an initial computable function f which insures the computability of its derivative f′. (shrink)

Epstein and Carnielli's fine textbook on logic and computability is now in its second edition. The readers of this journal might be particularly interested in the timeline `Computability and Undecidability' added in this edition, and the included wall-poster of the same title. The text itself, however, has some aspects which are worth commenting on.

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)

This is an annotated reading list on the beginning elements of the theory of computable functions. It is now structured so as to complement the first eight lectures of Thomas Forster’s Part III course in Lent 2011 (see the first four chapters of his evolving handouts).

We compute here the Borel complexity of the relation of isometry between separable Banach spaces, using results of Gao, Kechris [2], Mayer-Wolf [5], and Weaver [8]. We show that this relation is Borel bireducible to the universal relation for Borel actions of Polish groups. (© 2007 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim).