Results for ' recursive randomness'

1000+ found
Order:
  1.  46
    Random closed sets viewed as random recursions.R. Daniel Mauldin & Alexander P. McLinden - 2009 - Archive for Mathematical Logic 48 (3-4):257-263.
    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 (...)
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  2.  16
    Loveland Donald. A new interpretation of the von Mises' concept of random sequence. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 12 , pp. 279–294.Loveland D. W.. The Kleene hierarchy classification of recursively random sequences. Transactions of the American Mathematical Society, vol. 125 , pp. 497–510. [REVIEW]Robert A. DiPaola - 1971 - Journal of Symbolic Logic 36 (3):537-538.
  3.  17
    Recursive events in random sequences.George Davie - 2001 - Archive for Mathematical Logic 40 (8):629-638.
    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 (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  4.  3
    Recursive State and Random Fault Estimation for Linear Discrete Systems under Dynamic Event-Based Mechanism and Missing Measurements.Xuegang Tian & Shaoying Wang - 2020 - Complexity 2020:1-10.
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  5. Randomness and Recursive Enumerability.Siam J. Comput - unknown
    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. (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  6.  23
    Randomness, Unpredictability and Absence of Order: The Identification by the Theory of Recursivity of the Mathematical Notion of Random Sequence.Jean-Paul Delahaye - 1993 - In J. Dubucs (ed.), Philosophy of Probability. Kluwer, Dordrecht. pp. 145--167.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark   2 citations  
  7.  4
    Hierarchical semi-Markov conditional random fields for deep recursive sequential data.Truyen Tran, Dinh Phung, Hung Bui & Svetha Venkatesh - 2017 - Artificial Intelligence 246 (C):53-85.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  8.  63
    Randomness, relativization and Turing degrees.André Nies, Frank Stephan & Sebastiaan A. Terwijn - 2005 - Journal of Symbolic Logic 70 (2):515-535.
    We compare various notions of algorithmic randomness. First we consider relativized randomness. A set is n-random if it is Martin-Löf random relative to ∅. We show that a set is 2-random if and only if there is a constant c such that infinitely many initial segments x of the set are c-incompressible: C ≥ |x|-c. The ‘only if' direction was obtained independently by Joseph Miller. This characterization can be extended to the case of time-bounded C-complexity. Next we prove (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   25 citations  
  9.  86
    Computational randomness and lowness.Sebastiaan A. Terwijn & Domenico Zambella - 2001 - Journal of Symbolic Logic 66 (3):1199-1205.
    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.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   23 citations  
  10.  17
    Recursive Approximability of Real Numbers.Xizhong Zheng - 2002 - Mathematical Logic Quarterly 48 (S1):131-156.
    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.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  11.  25
    Randomness and Halting Probabilities.VeróNica Becher, Santiago Figueira, Serge Grigorieff & Joseph S. Miller - 2006 - Journal of Symbolic Logic 71 (4):1411 - 1430.
    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}$ (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  12.  7
    George Barmpalias, Andrew E. M. Lewis and Keng Meng NG. The importance of Π 0 1 classes in effective randomness. The Journal of Symbolic Logic, vol. 75 (2010), pp. 387–400. - George Barmpalias, Andrew E. M. Lewis and Frank Stephan. Π 0 1 classes, LR degrees and Turing degrees. Annals of Pure and Applied Logic, vol. 156 (2008), pp. 21–38. - Antonin Kučera. Measure, Π 0 1 classes and complete extensions of PA. Recursion Theory Week (Oberwofach, 1984). Lecture Notes in Mathematics, vol. 1141. Springer, Berlin, 1985, pp. 245–259. - Frank Stephan. Martin-Löf randomness and PA complete sets. Logic Colloquium '02. Lecture Notes in Logic, vol. 27, Association for Symbolic Logic, La Jolla, CA, 2006, pp. 342–348. [REVIEW]Douglas Cenzer - 2012 - Bulletin of Symbolic Logic 18 (3):409-412.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  13.  8
    The recursive universe: cosmic complexity and the limits of scientific knowledge.William Poundstone - 1985 - Mineola, New York: Dover Publications.
    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.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark   7 citations  
  14.  29
    Randomness Through Computation: Some Answers, More Questions.Hector Zenil (ed.) - 2011 - World Scientific.
    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 (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  15. Subclasses of the Weakly Random Reals.Johanna N. Y. Franklin - 2010 - Notre Dame Journal of Formal Logic 51 (4):417-426.
    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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  16.  28
    General random sequences and learnable sequences.C. P. Schnorr & P. Fuchs - 1977 - Journal of Symbolic Logic 42 (3):329-340.
    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 (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  17.  13
    On relative randomness.Antonín Kučera - 1993 - Annals of Pure and Applied Logic 63 (1):61-67.
    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 (...). (shrink)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  18.  39
    Lowness for Kurtz randomness.Noam Greenberg & Joseph S. Miller - 2009 - Journal of Symbolic Logic 74 (2):665-678.
    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 (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  19.  14
    Infinite Computations with Random Oracles.Merlin Carl & Philipp Schlicht - 2017 - Notre Dame Journal of Formal Logic 58 (2):249-270.
    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 (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  20.  28
    0-1 laws for recursive structures.E. Grädel & A. Malmström - 1999 - Archive for Mathematical Logic 38 (4-5):205-215.
    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.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  21.  69
    The unimportance of being random.Michael J. White - 1988 - Synthese 76 (1):171 - 178.
    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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  22.  21
    Program extraction for 2-random reals.Alexander P. Kreuzer - 2013 - Archive for Mathematical Logic 52 (5-6):659-666.
    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}} + (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  23.  2
    Π11‐Martin‐Löf randomness and Π11‐Solovay completeness.Claude Sureson - 2019 - Mathematical Logic Quarterly 65 (3):265-279.
    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.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  24. Van Lambalgen's Theorem and High Degrees.Johanna N. Y. Franklin & Frank Stephan - 2011 - Notre Dame Journal of Formal Logic 52 (2):173-185.
    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.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  25.  18
    Arithmetical Measure.Sebastiaan A. Terwijn & Leen Torenvliet - 1998 - Mathematical Logic Quarterly 44 (2):277-286.
    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 (...)
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark  
  26.  8
    Schnorr trivial reals: a construction. [REVIEW]Johanna N. Y. Franklin - 2008 - Archive for Mathematical Logic 46 (7-8):665-678.
    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''}}$ , (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  27.  40
    Mass problems and almost everywhere domination.Stephen G. Simpson - 2007 - Mathematical Logic Quarterly 53 (4):483-492.
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  28. Peter Kirschenmann.Concepts Of Randomness - 1973 - In Mario Augusto Bunge (ed.), Exact Philosophy; Problems, Tools, and Goals. Boston: D. Reidel. pp. 129.
    No categories
     
    Export citation  
     
    Bookmark  
  29.  9
    Reference Explained Away: Anaphoric Reference and Indirect.Robert Bb Random - 2005 - In J. C. Beall & B. Armour-Garb (eds.), Deflationary Truth. Open Court. pp. 258.
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  30.  7
    Fandom as Methodology: A Sourcebook for Artists and Writers.Catherine Grant & Kate Random Love (eds.) - 2019 - London: MIT Press.
    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, (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  31. Pierre mounoud.P. Rochat & A. Recursive Model - 1995 - In The Self in Infancy: Theory and Research. Elsevier. pp. 112--141.
     
    Export citation  
     
    Bookmark  
  32. Introduction: Fandom as methodology.Catherine Grant & Kate Random Love - 2019 - In Catherine Grant & Kate Random Love (eds.), Fandom as methodology: a sourcebook for artists and writers. Goldsmiths Press.
     
    Export citation  
     
    Bookmark  
  33. Program Size Complexity for Possibly Infinite Computations.Verónica Becher, Santiago Figueira, André Nies & Silvana Picchi - 2005 - Notre Dame Journal of Formal Logic 46 (1):51-64.
    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 (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  34.  17
    Effects of social network factors on information acquisition and adoption of improved groundnut varieties: the case of Uganda and Kenya.Mary Thuo, Alexandra A. Bell, Boris E. Bravo-Ureta, Michée A. Lachaud, David K. Okello, Evelyn Nasambu Okoko, Nelson L. Kidula, Carl M. Deom & Naveen Puppala - 2014 - Agriculture and Human Values 31 (3):339-353.
    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 (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  35.  18
    Bounded arithmetic for NC, ALogTIME, L and NL.P. Clote & G. Takeuti - 1992 - Annals of Pure and Applied Logic 56 (1-3):73-117.
    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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   13 citations  
  36.  30
    Π 1 0 classes, L R degrees and Turing degrees.George Barmpalias, Andrew E. M. Lewis & Frank Stephan - 2008 - Annals of Pure and Applied Logic 156 (1):21-38.
    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.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  37.  9
    Encryption of graphic information by means of transformation matrixes for protection against decofing by neural algorithms.Yunak O. M., Stryxaluk B. M. & Yunak O. P. - 2020 - Artificial Intelligence Scientific Journal 25 (2):15-20.
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  38.  4
    Breast Cancer Identification from Patients’ Tweet Streaming Using Machine Learning Solution on Spark.Nahla F. Omran, Sara F. Abd-el Ghany, Hager Saleh & Ayman Nabil - 2021 - Complexity 2021:1-12.
    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. (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  39.  5
    Gesture Recognition by Ensemble Extreme Learning Machine Based on Surface Electromyography Signals.Fulai Peng, Cai Chen, Danyang Lv, Ningling Zhang, Xingwei Wang, Xikun Zhang & Zhiyong Wang - 2022 - Frontiers in Human Neuroscience 16:911204.
    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. (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  40. Does set theory really ground arithmetic truth?Alfredo Roque Freire - manuscript
    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 (...)
     
    Export citation  
     
    Bookmark  
  41.  12
    [Omnibus Review].Steven Homer - 1999 - Journal of Symbolic Logic 64 (1):399-401.
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  42.  42
    An incomplete set of shortest descriptions.Frank Stephan & Jason Teutsch - 2012 - Journal of Symbolic Logic 77 (1):291-307.
    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 (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  43.  22
    Bounded Immunity and Btt‐Reductions.Stephen Fenner & Marcus Schaefer - 1999 - Mathematical Logic Quarterly 45 (1):3-21.
    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 (...)
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark   4 citations  
  44.  3
    A hierarchy of Turing degrees: a transfinite hierarchy of lowness notions in the computably enumerable degrees, unifying classes, and natural definability.R. G. Downey - 2020 - Princeton: Princeton University Press. Edited by Noam Greenberg.
    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 (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  45.  18
    Commentary on Risto Naatanen (1990). The role of attention in auditory information processing as revealed by event-related potentials and other brain measures of cognitive fenctiono BBS 13s201-2888. [REVIEW]A. Ryan, R. D. Ryder, L. Schiebinger, P. Singer & Random House - 1991 - Behavioral and Brain Sciences 14:4.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark  
  46.  40
    Classical recursion theory: the theory of functions and sets of natural numbers.Piergiorgio Odifreddi - 1989 - New York, N.Y., USA: Sole distributors for the USA and Canada, Elsevier Science Pub. Co..
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   72 citations  
  47.  15
    Recursion-theoretic hierarchies.Peter G. Hinman - 1978 - New York: Springer Verlag.
  48.  2
    Random Justice: On Lotteries and Legal Decision-Making.Neil Duxbury - 2002 - Oxford University Press UK.
    This controversial book explores the potential for the use of lotteries in social, and particularly legal, decision-making contexts. Utilizing a variety of disciplines and materials, the author considers in detail the history, advantages, and drawbacks of deciding issues of social significance by lot and argues that the value of the lottery as a legal decision-making device has generally been underestimated. The final chapter of the book considers how lotteries might be combined with other decision-mechanisms and suggests that it may sometimes (...)
    Direct download  
     
    Export citation  
     
    Bookmark   5 citations  
  49.  13
    Random Justice: On Lotteries and Legal Decision-Making.Neil Duxbury - 1999 - Oxford University Press UK.
    Chance inevitably plays a role in law but it is not often that we consciously try to import an element of randomness into a legal process. Random Justice: On Lotteries and Legal Decision-Making explores the potential for the use of lotteries in social, and particularly legal, decision-making contexts. Utilizing a variety of disciplines and materials, Neil Duxbury considers in detail the history, advantages, and drawbacks of deciding issues of social significance by lot and argues that the value of the (...)
    Direct download  
     
    Export citation  
     
    Bookmark   5 citations  
  50.  18
    Rudimentary Recursion, Gentle Functions and Provident Sets.A. R. D. Mathias & N. J. Bowler - 2015 - Notre Dame Journal of Formal Logic 56 (1):3-60.
    This paper, a contribution to “micro set theory”, is the study promised by the first author in [M4], as improved and extended by work of the second. We use the rudimentarily recursive functions and the slightly larger collection of gentle functions to initiate the study of provident sets, which are transitive models of $\mathsf{PROVI}$, a subsystem of $\mathsf{KP}$ whose minimal model is Jensen’s $J_{\omega}$. $\mathsf{PROVI}$ supports familiar definitions, such as rank, transitive closure and ordinal addition—though not ordinal multiplication—and Shoenfield’s (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   3 citations  
1 — 50 / 1000