It is known that the box dimension of any Martin-Löf random closed set of ${\{0,1\}^\mathbb{N}}$ is ${\log_2(\frac{4}{3})}$ . Barmpalias et al. [J Logic Comput 17(6):1041–1062, 2007] gave one method of producing such random closed sets and then computed the box dimension, and posed several questions regarding other methods of construction. We outline a method using random recursive constructions for computing the Hausdorff dimension of almost every random closed set of ${\{0,1\}^\mathbb{N}}$ , and propose a general method for random closed (...) sets in other spaces. We further find both the appropriate dimensional Hausdorff measure and the exact Hausdorff dimension for such random closed sets. (shrink)

Let ω be a Kolmogorov–Chaitin random sequence with ω1: n denoting the first n digits of ω. Let P be a recursive predicate defined on all finite binary strings such that the Lebesgue measure of the set {ω|∃nP(ω1: n )} is a computable real α. Roughly, P holds with computable probability for a random infinite sequence. Then there is an algorithm which on input indices for any such P and α finds an n such that P holds within the (...) first n digits of ω or not in ω at all. We apply the result to the halting probability Ω and show that various generalizations of the result fail. (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)

This paper is concerned with the event-based state and fault estimation problem for a class of linear discrete systems with randomly occurring faults and missing measurements. Different from the static event-based transmission mechanism with a constant threshold, a dynamic event-based mechanism is exploited here to regulate the threshold parameter, thus further reducing the amount of data transmission. Some mutually independent Bernoulli random variables are used to characterize the phenomena of ROFs and missing measurements. In order to simultaneously estimate the system (...) state and the fault signals, the main attention of this paper is paid to the design of recursive filter; for example, for all DETM, ROFs, and missing measurements, an upper bound for the estimation error covariance is ensured and the relevant filter gain matrix is designed by minimizing the obtained upper bound. Moreover, the rigorous mathematical analysis is carried out for the exponential boundedness of the estimation error. It is clear that the developed algorithms are dependent on the threshold parameters and the upper bound together with the probabilities of missing measurements and ROFs. Finally, a numerical example is provided to indicate the effectiveness of the presented estimation schemes. (shrink)

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

We prove that there are uncountably many sets that are low for the class of Schnorr random reals. We give a purely recursion theoretic characterization of these sets and show that they all have Turing degree incomparable to 0'. This contrasts with a result of Kučera and Terwijn [5] on sets that are low for the class of Martin-Löf random reals.

This fascinating popular science journey explores key concepts in information theory in terms of Conway's "Game of Life" program. The author explains the application of natural law to a random system and demonstrates the necessity of limits. Other topics include the limits of knowledge, paradox of complexity, Maxwell's demon, Big Bang theory, and much more. 1985 edition.

The book is intended to explain the larger and intuitive concept of randomness by means of computation, particularly through algorithmic complexity and recursion theory. It also includes the transcriptions (by A. German) of two panel discussion on the topics: Is The Universe Random?, held at the University of Vermont in 2007; and What is Computation? (How) Does Nature Compute?, held at the University of Indiana Bloomington in 2008. The book is intended to the general public, undergraduate and graduate students (...) in math, computer science, physics and other sciences, but also to philosophers of science and researchers. (shrink)

We consider the question of randomness of the probability ΩU[X] that an optimal Turing machine U halts and outputs a string in a fixed set X. The main results are as follows: ΩU[X] is random whenever X is $\Sigma _{n}^{0}$-complete or $\Pi _{n}^{0}$-complete for some n ≥ 2. However, for n ≥ 2, ΩU[X] is not n-random when X is $\Sigma _{n}^{0}$ or $\Pi _{n}^{0}$ Nevertheless, there exists $\Delta _{n+1}^{0}$ sets such that ΩU[X] is n-random. There are $\Delta _{2}^{0}$ (...) sets X such that ΩU[X] is rational. Also, for every n ≥ 1, there exists a set X which is $\Delta _{n+1}^{0}$ and $\Sigma _{n}^{0}$-hard such that ΩU[X] is not random. We also look at the range of ΩU as an operator. We prove that the set {ΩU[X]: X ⊆ 2<ω} is a finite union of closed intervals. It follows that for any optimal machine U and any sufficiently small real r, there is a set X ⊆ 2<ω recursive in ∅′ ⊕ r, such that ΩU[X] = r. The same questions are also considered in the context of infinite computations, and lead to similar results. (shrink)

We formalise the notion of those infinite binary sequences z that admit a single program P which expresses the entire algorithmical structure of z. Such a program P minimizes the information which must be used in a relative computation for z. We propose two concepts with different strength for this notion, the learnable and the super-learnable sequences. We establish three different equivalent characterizations of learnable (super-learnable, resp.) sequences. In particular, we prove that a sequences z is learnable (super-learnable, resp.) if (...) and only if there is a computable probability measure p such that p is Schnorr (Martin-Lof, resp.) p-random. There is a recursively enumerable sequence which is not learnable. The learnable sequences are invariant with respect to all total and effective transformations of infinite binary sequences. (shrink)

The weakly random reals contain not only the Schnorr random reals as a subclass but also the weakly 1-generic reals and therefore the n -generic reals for every n . While the class of Schnorr random reals does not overlap with any of these classes of generic reals, their degrees may. In this paper, we describe the extent to which this is possible for the Turing, weak truth-table, and truth-table degrees and then extend our analysis to the Schnorr random and (...) hyperimmune reals. (shrink)

Kuera, A., On relative randomness, Annals of Pure and Applied Logic 63 61–67. It is the aim of the paper to answer a question raised by M. van Lambalgen and D. Zambella whether there can be a nonrecursive set A having the property that there is a set B such that B is 1-random relative to A and simultaneously A is recursive in B. We give apositive answer to this question as well as further information about relative (...) class='Hi'>randomness. (shrink)

We prove that degrees that are low for Kurtz randomness cannot be diagonally non-recursive. Together with the work of Stephan and Yu [16], this proves that they coincide with the hyperimmune-free non-DNR degrees, which are also exactly the degrees that are low for weak 1-genericity. We also consider Low(M, Kurtz), the class of degrees a such that every element of M is a-Kurtz random. These are characterised when M is the class of Martin-Löf random, computably random, or Schnorr (...) random reals. We show that Low(ML, Kurtz) coincides with the non-DNR degrees, while both Low(CR, Kurtz) and Low(Schnorr, Kurtz) are exactly the non-high, non-DNR degrees. (shrink)

We consider the following problem for various infinite-time machines. If a real is computable relative to a large set of oracles such as a set of full measure or just of positive measure, a comeager set, or a nonmeager Borel set, is it already computable? We show that the answer is independent of ZFC for ordinal Turing machines with and without ordinal parameters and give a positive answer for most other machines. For instance, we consider infinite-time Turing machines, unresetting and (...) resetting infinite-time register machines, and α-Turing machines for countable admissible ordinals α. (shrink)

We discuss resource-bounded measures on the class of recursive structures and prove that with respect to such measures a random recursive structure is almost surely isomorphic to the unique countable model of the extension axioms.

This note fleshes in and generalizes an argument suggested by W. Salmon to the effect that the addition of a requirement of mathematical randomness to his requirement of physical homogeneity is unimportant for his ontic account of objective homogeneity. I consider an argument from measure theory as a plausible justification of Salmon''s skepticism concerning the possibility that a physically homogeneous sequence might nonetheless be recursive and show that this argument does not succeed. However, I state a principle (the (...) Generalized Salmon Thesis) that is intuitively plausible and reflects this skepticism. The principle entails that one should be just as certain that the limit of such an infinite sequence is irrational as one is certain that the sequence is not computable. But I claim that this consequence is acceptable. (shrink)

Let ${2-\textsf{RAN}}$ be the statement that for each real X a real 2-random relative to X exists. We apply program extraction techniques we developed in Kreuzer and Kohlenbach (J. Symb. Log. 77(3):853–895, 2012. doi:10.2178/jsl/1344862165), Kreuzer (Notre Dame J. Formal Log. 53(2):245–265, 2012. doi:10.1215/00294527-1715716) to this principle. Let ${{\textsf{WKL}_0^\omega}}$ be the finite type extension of ${\textsf{WKL}_0}$ . We obtain that one can extract primitive recursive realizers from proofs in ${{\textsf{WKL}_0^\omega} + \Pi^0_1-{\textsf{CP}} + 2-\textsf{RAN}}$ , i.e., if ${{\textsf{WKL}_0^\omega} + \Pi^0_1-{\textsf{CP}} + (...) 2-\textsf{RAN} \, {\vdash} \, \forall{f}\, {\exists}{x} A_{qf}(f,x)}$ then one can extract from the proof a primitive recursive term t(f) such that ${A_{qf}(f,t(f))}$ . As a consequence, we obtain that ${{\textsf{WKL}_0}+ \Pi^0_1 - {\textsf{CP}} + 2-\textsf{RAN}}$ is ${\Pi^0_3}$ -conservative over ${\textsf{RCA}_0}$. (shrink)

Developing an analogue of Solovay reducibility in the higher recursion setting, we show that results from the classical computably enumerable case can be extended to the new context.

We show that van Lambalgen's Theorem fails with respect to recursive randomness and Schnorr randomness for some real in every high degree and provide a full characterization of the Turing degrees for which van Lambalgen's Theorem can fail with respect to Kurtz randomness. However, we also show that there is a recursively random real that is not Martin-Löf random for which van Lambalgen's Theorem holds with respect to recursive randomness.

An illustrated exploration of fandom that combines academic essays with artist pages and experimental texts. Fandom as Methodology examines fandom as a set of practices for approaching and writing about art. The collection includes experimental texts, autobiography, fiction, and new academic perspectives on fandom in and as art. Key to the idea of “fandom as methodology” is a focus on the potential for fandom in art to create oppositional spaces, communities, and practices, particularly from queer perspectives, but also through transnational, (...) feminist and artist-of-color fandoms. The book provides a range of examples of artists and writers working in this vein, as well as academic essays that explore the ways in which fandom can be theorized as a methodology for art practice and art history. Fandom as Methodology proposes that many artists and art writers already draw on affective strategies found in fandom. With the current focus in many areas of art history, art writing, and performance studies around affective engagement with artworks and imaginative potentials, fandom is a key methodology that has yet to be explored. Interwoven into the academic essays are lavishly designed artist pages in which artists offer an introduction to their use of fandom as methodology. Contributors Taylor J. Acosta, Catherine Grant, Dominic Johnson, Kate Random Love, Maud Lavin, Owen G. Parry, Alice Butler, SooJin Lee, Jenny Lin, Judy Batalion, Ika Willis. Artists featured in the artist pages Jeremy Deller, Ego Ahaiwe Sowinski, Anna Bunting-Branch, Maria Fusco, Cathy Lomax, Kamau Amu Patton, Holly Pester, Dawn Mellor, Michelle Williams Gamaker, The Women of Colour Index Reading Group, Liv Wynter, Zhiyuan Yang. (shrink)

We develop arithmetical measure theory along the lines of Lutz [10]. This yields the same notion of measure 0 set as considered before by Martin-Löf, Schnorr, and others. We prove that the class of sets constructible by r.e.-constructors, a direct analogue of the classes Lutz devised his resource bounded measures for in [10], is not equal to RE, the class of r.e. sets, and we locate this class exactly in terms of the common recursion-theoretic reducibilities below K. We note that (...) the class of sets that bounded truth-table reduce to K has r.e.-measure 0, and show that this cannot be improved to truth-table. For Δ2-measure the borderline between measure zero and measure nonzero lies between weak truth-table reducibility and Turing reducibility to K. It follows that there exists a Martin-Löf random set that is tt-reducible to K, and that no such set is btt-reducible to K. In fact, by a result of Kautz, a much more general result holds. (shrink)

A real is Martin-Löf (Schnorr) random if it does not belong to any effectively presented null ${\Sigma^0_1}$ (recursive) class of reals. Although these randomness notions are very closely related, the set of Turing degrees containing reals that are K-trivial has very different properties from the set of Turing degrees that are Schnorr trivial. Nies proved in (Adv Math 197(1):274–305, 2005) that all K-trivial reals are low. In this paper, we prove that if ${{\bf h'} \geq_T {\bf 0''}}$ , (...) then h contains a Schnorr trivial real. Since this concept appears to separate computational complexity from computational strength, it suggests that Schnorr trivial reals should be considered in a structure other than the Turing degrees. (shrink)

We examine the concept of almost everywhere domination from the viewpoint of mass problems. Let AED and MLR be the sets of reals which are almost everywhere dominating and Martin-Löf random, respectively. Let b1, b2, and b3 be the degrees of unsolvability of the mass problems associated with AED, MLR × AED, and MLR ∩ AED, respectively. Let [MATHEMATICAL SCRIPT CAPITAL P]w be the lattice of degrees of unsolvability of mass problems associated with nonempty Π01 subsets of 2ω. Let 1 (...) and 0 be the top and bottom elements of [MATHEMATICAL SCRIPT CAPITAL P]w. We show that inf, inf, and inf belong to [MATHEMATICAL SCRIPT CAPITAL P]w and 0 < inf < inf < inf < 1. Under the natural embedding of the recursively enumerable Turing degrees into [MATHEMATICAL SCRIPT CAPITAL P]w, we show that inf and inf but not inf are comparable with some recursively enumerable Turing degrees other than 0 and 0′. In order to make this paper more self-contained, we exposit the proofs of some recent theorems due to Hirschfeldt, Miller, Nies, and Stephan. (shrink)

Twitter integrates with streaming data technologies and machine learning to add new value to healthcare. This paper presented a real-time system to predict breast cancer based on streaming patient’s health data from Twitter. The proposed system consists of two major components: developing an offline building model and an online prediction pipeline. For the first component, we made a correlation between the features to determine the correlation between features and reduce the number of features from the Breast Cancer Wisconsin Diagnostic dataset. (...) Two feature selection algorithms are recursive feature elimination and univariate feature selection algorithms which are applied to features after correlation to select the essential features. Four decision trees, logistic regression, support vector machine, and random forest classifier have been used on features after correlation and feature selection. Also, hyperparameter tuning and cross-validation have been applied with machine learning to optimize models and enhance accuracy. Apache Spark, Apache Kafka, and Twitter Streaming API are used to develop the second component. The best model with the highest accuracy obtained from the first component predicts breast cancer in real time from tweets’ streaming. The results showed that the best model is the random forest classifier which achieved the best accuracy. (shrink)

This book presents new results in computability theory, a branch of mathematical logic and computer science that has become increasingly relevant in recent years. The field's connections with disparate areas of mathematical logic and mathematics more generally have grown deeper, and now have a variety of applications in topology, group theory, and other subfields. This monograph establishes new directions in the field, blending classic results with modern research areas such as algorithmic randomness. The significance of the book lies not (...) only in the depth of the results contained therein, but also in the fact that the notions the authors introduce allow them to unify results from several subfields of computability theory. (shrink)

We say that A≤LRB if every B-random set is A-random with respect to Martin–Löf randomness. We study this relation and its interactions with Turing reducibility, classes, hyperimmunity and other recursion theoretic notions.

We define theories of bounded arithmetic, whose definable functions and relations are exactly those in certain complexity classes. Based on a recursion-theoretic characterization of NC in Clote , the first-order theory TNC, whose principal axiom scheme is a form of short induction on notation for nondeterministic polynomial-time computable relations, has the property that those functions having nondeterministic polynomial-time graph Θ such that TNC x y Θ are exactly the functions in NC, computable on a parallel random-access machine in polylogarithmic parallel (...) time with a polynomial number of processors.0 We then define three theories of weak second-order arithmetic which respectively characterize relations in the classes of alternating logarithmic time, logspace and nondeterministic logspace. (shrink)

Social networks play a significant role in learning and thus in farmers’ adoption of new agricultural technologies. This study examined the effects of social network factors on information acquisition and adoption of new seed varieties among groundnut farmers in Uganda and Kenya. The data were generated through face-to-face interviews from a random sample of 461 farmers, 232 in Uganda and 229 in Kenya. To assess these effects two alternative econometric models were used: a seemingly unrelated bivariate probit model and a (...) recursive bivariate probit model. The statistical evaluation of the SUBP shows that information acquisition and adoption decisions are interrelated while tests for the RBP do not support this latter model. Therefore, the analysis is based on the results obtained from the SUBP. These results reveal that social network factors, particularly weak ties with external support, partially influence information acquisition, but do not influence adoption. In Uganda, external support, gender, farm size, and geographic location have an impact on information acquisition. In Kenya, external support and geographic location also have an impact on information acquisition. With regard to adoption, gender, household size, and geographic location play the most important roles for Ugandan farmers, while in Kenya information from external sources, education, and farm size affect adoption choice. The study provides insight on the importance of external weak ties in groundnut farming, and a need to understand regional differences along gender lines while developing agricultural strategies. This study further illustrates the importance of farmer participation in applied technology research and the impact of social interactions among farmers and external agents. (shrink)

We define a program size complexity function $H^\infty$ as a variant of the prefix-free Kolmogorov complexity, based on Turing monotone machines performing possibly unending computations. We consider definitions of randomness and triviality for sequences in ${\{0,1\}}^\omega$ relative to the $H^\infty$ complexity. We prove that the classes of Martin-Löf random sequences and $H^\infty$-random sequences coincide and that the $H^\infty$-trivial sequences are exactly the recursive ones. We also study some properties of $H^\infty$ and compare it with other complexity functions. In (...) particular, $H^\infty$ is different from $H^A$, the prefix-free complexity of monotone machines with oracle A. (shrink)

In the recent years, gesture recognition based on the surface electromyography (sEMG) signals has been extensively studied. However, the accuracy and stability of gesture recognition through traditional machine learning algorithms are still insufficient to some actual application scenarios. To enhance this situation, this paper proposed a method combining feature selection and ensemble extreme learning machine (EELM) to improve the recognition performance based on sEMG signals. First, the input sEMG signals are preprocessed and 16 features are then extracted from each channel. (...) Next, features that mostly contribute to the gesture recognition are selected from the extracted features using the recursive feature elimination (RFE) algorithm. Then, several independent ELM base classifiers are established using the selected features. Finally, the recognition results are determined by integrating the results obtained by ELM base classifiers using the majority voting method. The Ninapro DB5 dataset containing 52 different hand movements captured from 10 able-bodied subjects was used to evaluate the performance of the proposed method. The results showed that the proposed method could perform the best (overall average accuracy 77.9%) compared with decision tree (DT), ELM, and random forest (RF) methods. (shrink)

We consider the foundational relation between arithmetic and set theory. Our goal is to criticize the construction of standard arithmetic models as providing grounds for arithmetic truth (even in a relative sense). Our method is to emphasize the incomplete picture of both theories and treat models as their syntactical counterparts. Insisting on the incomplete picture will allow us to argue in favor of the revisability of the standard model interpretation. We then show that it is hopeless to expect that the (...) relative grounding provided by a standard interpretation can resist being revisable. We start briefly characterizing the expansion of arithmetic `truth' provided by the interpretation in a set theory. Further, we show that, for every well-founded interpretation of recursive extensions of PA in extensions of ZF, the interpreted version of arithmetic has more theorems than the original. This theorem expansion is not complete however. We continue by defining the coordination problem. The problem can be summarized as follows. We consider two independent communities of mathematicians responsible for deciding over new axioms for ZF and PA. How likely are they to be coordinated regarding PA’s interpretation in ZF? We prove that it is possible to have extensions of PA not interpretable in a given set theory ST. We further show that the probability of a random extension of arithmetic being interpretable in ST is zero. (shrink)

Reviewed Works:Andrea Sorbi, Complexity, Logic, and Recursion Theory.Klaus Ambos-Spies, Elvira Mayordomo, Resource-Bounded Measure and Randomness.Marat Arslanov, Degree Structures in Local Degree Theory.Jose L. Balcazar, Ricard Gavalda, Montserrat Hermo, Compressibility of Infinite Binary Sequences.S. Barry Cooper, Beyond Godel's Theorem: The Failure to Capture Information Content.Robert A. Di Paola, Franco Montagna, Progressions of Theories of Bounded Arithmetic.Rodney G. Downey, On Presentations of Algebraic Structures.Sophie Fischer, Lane Hemaspaandra, Leen Torenvliet, Witness-Isomorphic Reductions and Local Search.William Gasarch, Carl H. Smith, A Survey of Inductive (...) Inference with an Emphasis on Queries.Andre Nies, A Uniformity of Degree Structures.Piergiorgio Odifreddi, Short Course on Logic, Algebra, and Topology.Andrea Sorbi, The Enumeration Degrees of the $\sigma^0_2$ Sets.Peter van Emde Boas, The Convenience of Tilings. (shrink)

The article deals with the algorithm of encrypting graphic information using transformation matrixes. It presents the actions that can be done with the image. The article also gives algorithms for forming matrixes that are created with the use of random processes. Examples of matrixes and encryption results are shown. Calculations of the analysis of combinations and conclusions to them are carried out. The article shows the possibilities and advantages of this image encryption algorithm. The proposed algorithm will allow to transmit (...) encrypted information through open communication channels. The algorithm uses all possible actions that can be done with the image, namely: image resizing, adding redundant elements to the image, changing the location of the pixels, changing the brightness of the image pixels, inverting the image pixels, changing the colours of the images pixels. A randomized approach to matrix formation will make it impossible to use neural systems. The algorithm of the implementation of writing encryption code is rather simple. It is not possible to decrypt the image without a key as the number of possible combinations is extremely large. This algorithm can be used in the military, intelligence, information security. Encryption does not require significant computing or RAM resources. This algorithm can be implemented in WEB-technology and in mobile applications, it has no recursive functions and loop in loop. The algorithm hides the image size, which in turn adds extra protection. Redundant elements will not allow neural networks to compare pixels. Changing colors, changing brightness, inversion by random processes will not allow neural networks to find the decryption function. The article considers an image encryption algorithm that will give a possibility to generate a key. The key will be a set of two-dimensional arrays formed in a randomized manner. A randomized approach to matrix formation will make it impossible to use neural systems. The algorithm uses all possible actions that can be done with the image, namely: Image resizing. Adding redundant elements to the image. Changing the location of the pixels. Changing the brightness of the image pixels. Inverting the image pixels. Changing the colours of the images pixels. The pixel positioning matrix gives us! combinations. The pixel brightness change matrix gives us 8 *! combinations. The pixel inversion matrix gives us 8 *! combinations. The pixel colour change matrix gives us 6 *! Combinations. The total number of combinations N is equal to: It is not possible to decrypt the image without a key as the number of possible combinations is extremely large. The algorithm of the implementation of writing encryption code is rather simple. This algorithm can be used in the military, intelligence, information security. The advantage of this algorithm is the fact that the encrypted image can be transmitted through open chann. (shrink)

The truth-table degree of the set of shortest programs remains an outstanding problem in recursion theory. We examine two related sets, the set of shortest descriptions and the set of domain-random strings, and show that the truth-table degrees of these sets depend on the underlying acceptable numbering. We achieve some additional properties for the truth-table incomplete versions of these sets, namely retraceability and approximability. We give priority-free constructions of bounded truth-table chains and bounded truth-table antichains inside the truth-table complete degree (...) by identifying an acceptable set of domain-random strings within each degree. (shrink)

We define and study a new notion called k-immunity that lies between immunity and hyperimmunity in strength. Our interest in k-immunity is justified by the result that θ does not k-tt reduce to a k-immune set, which improves a previous result by Kobzev [7]. We apply the result to show that Φ′ does not btt-reduce to MIN, the set of minimal programs. Other applications include the set of Kolmogorov random strings, and retraceable and regressive sets. We also give a new (...) characterization of effectively simple sets and show that simple sets are not btt-cuppable. (shrink)

This graduate-level_text by a master in the field builds a function theory of the rational field that combines aspects of classical and intuitionist analysis. Topics include recursive convergence, recursive and relative continuity, recursive and relative differentiability, the relative integral, elementary functions, and transfinite ordinals. 1961 edition.

Volume II of Classical Recursion Theory describes the universe from a local (bottom-up or synthetical) point of view, and covers the whole spectrum, from the recursive to the arithmetical sets. The first half of the book provides a detailed picture of the computable sets from the perspective of Theoretical Computer Science. Besides giving a detailed description of the theories of abstract Complexity Theory and of Inductive Inference, it contributes a uniform picture of the most basic complexity classes, ranging from (...) small time and space bounds to the elementary functions, with a particular attention to polynomial time and space computability. It also deals with primitive recursive functions and larger classes, which are of interest to the proof theorist. The second half of the book starts with the classical theory of recursively enumerable sets and degrees, which constitutes the core of Recursion or Computability Theory. Unlike other texts, usually confined to the Turing degrees, the book covers a variety of other strong reducibilities, studying both their individual structures and their mutual relationships. The last chapters extend the theory to limit sets and arithmetical sets. The volume ends with the first textbook treatment of the enumeration degrees, which admit a number of applications from algebra to the Lambda Calculus. The book is a valuable source of information for anyone interested in Complexity and Computability Theory. The student will appreciate the detailed but informal account of a wide variety of basic topics, while the specialist will find a wealth of material sketched in exercises and asides. A massive bibliography of more than a thousand titles completes the treatment on the historical side. (shrink)

This volume presents the lecture notes of short courses given by three leading experts in mathematical logic at the 2012 Asian Initiative for Infinity Logic Summer School. The major topics cover set-theoretic forcing, higher recursion theory, and applications of set theory to C*-algebra. This volume offers a wide spectrum of ideas and techniques introduced in contemporary research in the field of mathematical logic to students, researchers and mathematicians.

Presents a new framework for the complexity of algorithms, for all readers interested in the theory of computation.

The series is devoted to the publication of high-level monographs on all areas of mathematical logic and its applications. It is addressed to advanced students and research mathematicians, and may also serve as a guide for lectures and for seminars at the graduate level.