Results for 'Kolmogorov complexity'

1000+ found
Order:
  1.  94
    Kolmogorov Complexity and Information Theory. With an Interpretation in Terms of Questions and Answers.Peter D. Grünwald & Paul M. B. Vitányi - 2003 - Journal of Logic, Language and Information 12 (4):497-529.
    We compare the elementary theories of Shannon information and Kolmogorov complexity, the extent to which they have a common purpose, and wherethey are fundamentally different. We discuss and relate the basicnotions of both theories: Shannon entropy, Kolmogorov complexity, Shannon mutual informationand Kolmogorov (``algorithmic'') mutual information. We explainhow universal coding may be viewed as a middle ground betweenthe two theories. We consider Shannon's rate distortion theory, whichquantifies useful (in a certain sense) information.We use the communication of (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  2.  25
    The Kolmogorov Complexity of Random Reals.Liang Yu, Decheng Ding & Rodney Downey - 2004 - Annals of Pure and Applied Logic 129 (1-3):163-180.
    We investigate the initial segment complexity of random reals. Let K denote prefix-free Kolmogorov complexity. A natural measure of the relative randomness of two reals α and β is to compare complexity K and K. It is well-known that a real α is 1-random iff there is a constant c such that for all n, Kn−c. We ask the question, what else can be said about the initial segment complexity of random reals. Thus, we study (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  3.  29
    Kolmogorov Complexity and the Second Incompleteness Theorem.Makoto Kikuchi - 1997 - Archive for Mathematical Logic 36 (6):437-443.
    . We shall prove the second incompleteness theorem via Kolmogorov complexity.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  4.  13
    Kolmogorov Complexity and Noncomputability.George Davie - 2002 - Mathematical Logic Quarterly 48 (4):574-581.
    We use a method suggested by Kolmogorov complexity to examine some relations between Kolmogorov complexity and noncomputability. In particular we show that the method consistently gives us more information than conventional ways of demonstrating noncomputability . Also, many sets which are awkward to embed into the halting problem are easily shown noncomputable. We also prove a gap-theorem for outputting consecutive integers and find, for a given length n, a statement of length n with maximal proof length.
    Direct download  
     
    Export citation  
     
    Bookmark  
  5.  6
    Kolmogorov Complexity and Set Theoretical Representations of Integers.Marie Ferbus-Zanda & Serge Grigorieff - 2006 - Mathematical Logic Quarterly 52 (4):375-403.
    We reconsider some classical natural semantics of integers in the perspective of Kolmogorov complexity. To each such semantics one can attach a simple representation of integers that we suitably effectivize in order to develop an associated Kolmogorov theory. Such effectivizations are particular instances of a general notion of “self-enumerated system” that we introduce in this paper. Our main result asserts that, with such effectivizations, Kolmogorov theory allows to quantitatively distinguish the underlying semantics. We characterize the families (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  6.  34
    Relative Kolmogorov Complexity and Geometry.Stephen Binns - 2011 - Journal of Symbolic Logic 76 (4):1211-1239.
    We use the notions of effective dimension and Kolmogorov complexity to describe a geometry on the set of infinite binary sequences. Geometric concepts that we define and use include angle, projections and scalar multiplication. A question related to compressibility is addressed using these ideas.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  7.  65
    Kolmogorov Complexity for Possibly Infinite Computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.
    In this paper we study the Kolmogorov complexity for non-effective computations, that is, either halting or non-halting computations on Turing machines. This complexity function is defined as the length of the shortest input that produce a desired output via a possibly non-halting computation. Clearly this function gives a lower bound of the classical Kolmogorov complexity. In particular, if the machine is allowed to overwrite its output, this complexity coincides with the classical Kolmogorov (...) for halting computations relative to the first jump of the halting problem. However, on machines that cannot erase their output –called monotone machines–, we prove that our complexity for non effective computations and the classical Kolmogorov complexity separate as much as we want. We also consider the prefix-free complexity for possibly infinite computations. We study several properties of the graph of these complexity functions and specially their oscillations with respect to the complexities for effective computations. (shrink)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  8.  17
    Kolmogorov Complexity Estimates for Detection of Viruses in Biologically Inspired Security Systems: A Comparison with Traditional Approaches.Sanjay Goel & Stephen F. Bush - 2003 - Complexity 9 (2):54-73.
  9.  9
    Kolmogorov Complexity and Characteristic Constants of Formal Theories of Arithmetic.Shingo Ibuka, Makoto Kikuchi & Hirotaka Kikyo - 2011 - Mathematical Logic Quarterly 57 (5):470-473.
    We investigate two constants cT and rT, introduced by Chaitin and Raatikainen respectively, defined for each recursively axiomatizable consistent theory T and universal Turing machine used to determine Kolmogorov complexity. Raatikainen argued that cT does not represent the complexity of T and found that for two theories S and T, one can always find a universal Turing machine such that equation image. We prove the following are equivalent: equation image for some universal Turing machine, equation image for (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  10.  14
    Kolmogorov Complexity and Computably Enumerable Sets.George Barmpalias & Angsheng Li - 2013 - Annals of Pure and Applied Logic 164 (12):1187-1200.
  11.  13
    Kolmogorov Complexity and Symmetric Relational Structures.W. L. Fouché & P. H. Potgieter - 1998 - Journal of Symbolic Logic 63 (3):1083-1094.
    We study partitions of Fraïssé limits of classes of finite relational structures where the partitions are encoded by infinite binary strings which are random in the sense of Kolmogorov-Chaitin.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  12. Kolmogorov Complexity and Characteristic Constants of Formal Theories of Arithmetic.Shingo Ibuka, Masato Kikuchi & Hirotaka Kikyo - 2011 - Mathematical Logic Quarterly 57 (5):470-473.
     
    Export citation  
     
    Bookmark  
  13. On the Kolmogorov Complexity of Continuous Real Functions.Amin Farjudian - 2013 - Annals of Pure and Applied Logic 164 (5):566-576.
    Kolmogorov complexity was originally defined for finitely-representable objects. Later, the definition was extended to real numbers based on the asymptotic behaviour of the sequence of the Kolmogorov complexities of the finitely-representable objects—such as rational numbers—used to approximate them.This idea will be taken further here by extending the definition to continuous functions over real numbers, based on the fact that every continuous real function can be represented as the limit of a sequence of finitely-representable enclosures, such as polynomials (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  14.  36
    Compressibility and Kolmogorov Complexity.Stephen Binns & Marie Nicholson - 2013 - Notre Dame Journal of Formal Logic 54 (1):105-123.
    This paper continues the study of the metric topology on $2^{\mathbb {N}}$ that was introduced by S. Binns. This topology is induced by a directional metric where the distance from $Y\in2^{\mathbb {N}}$ to $X\in2^{\mathbb {N}}$ is given by \[\limsup_{n}\frac{C(X\upharpoonright n|Y\upharpoonright n)}{n}.\] This definition is closely related to the notions of effective Hausdorff and packing dimensions. Here we establish that this is a path-connected topology on $2^{\mathbb {N}}$ and that under it the functions $X\mapsto\operatorname{dim}_{\mathcal{H}}X$ and $X\mapsto\operatorname{dim}_{p}X$ are continuous. We also investigate (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  15.  23
    Using Shannon Entropy and Kolmogorov Complexity to Study the Communicative System and Cognitive Capacities in Ants.Boris Ryabko & Zhanna Reznikova - 1996 - Complexity 2 (2):37-42.
  16.  12
    Applications of Kolmogorov Complexity to Computable Model Theory.B. Khoussainov, P. Semukhin & F. Stephan - 2007 - Journal of Symbolic Logic 72 (3):1041 - 1054.
    In this paper we answer the following well-known open question in computable model theory. Does there exist a computable not ‮א‬₀-categorical saturated structure with a unique computable isomorphism type? Our answer is affirmative and uses a construction based on Kolmogorov complexity. With a variation of this construction, we also provide an example of an ‮א‬₁-categorical but not ‮א‬₀-categorical saturated $\Sigma _{1}^{0}$ -structure with a unique computable isomorphism type. In addition, using the construction we give an example of an (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  17.  16
    Prefix and Plain Kolmogorov Complexity Characterizations of 2-Randomness: Simple Proofs.Bruno Bauwens - 2015 - Archive for Mathematical Logic 54 (5-6):615-629.
  18. Quantum Observer and Kolmogorov Complexity.Alexei Grinbaum - 2013 - In Tilman Sauer & Adrian Wüthrich (eds.), New Vistas on Old Problems. Max Planck Research Library for the History and Development of Knowledge. pp. 13.
     
    Export citation  
     
    Bookmark  
  19.  9
    On Measuring the Complexity of Networks: Kolmogorov Complexity Versus Entropy.Mikołaj Morzy, Tomasz Kajdanowicz & Przemysław Kazienko - 2017 - Complexity:1-12.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  20.  17
    Unified Characterizations of Lowness Properties Via Kolmogorov Complexity.Takayuki Kihara & Kenshi Miyabe - 2015 - Archive for Mathematical Logic 54 (3-4):329-358.
    Consider a randomness notion C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C}}$$\end{document}. A uniform test in the sense of C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C}}$$\end{document} is a total computable procedure that each oracle X produces a test relative to X in the sense of C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C}}$$\end{document}. We say that a binary sequence Y is C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C}}$$\end{document}-random uniformly relative to (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  21.  30
    Quantum Observer, Information Theory and Kolmogorov Complexity.Alexei Grinbaum - 2013 - In Hanne Andersen, Dennis Dieks, Wenceslao González, Thomas Uebel & Gregory Wheeler (eds.), New Challenges to Philosophy of Science. Springer Verlag. pp. 59--72.
  22.  21
    Ming Li and Paul Vitányi. An Introduction to Kolmogorov Complexity and its Applications. Texts and Monographs in Computer Science. Springer-Verlag, New York, Berlin, Heidelberg, Etc., 1993, Xx + 546 Pp. [REVIEW]V. A. Uspensky & A. Shen - 1995 - Journal of Symbolic Logic 60 (3):1017-1020.
  23.  31
    Complexity of Complexity and Strings with Maximal Plain and Prefix Kolmogorov Complexity.B. Bauwens & A. Shen - 2014 - Journal of Symbolic Logic 79 (2):620-632.
  24. Itzhak Gilboa.Kolmogorov'S. Complexity Measure & L. Simpucism - 1994 - In Dag Prawitz & Dag Westerståhl (eds.), Logic and Philosophy of Science in Uppsala. Kluwer Academic Publishers. pp. 205.
    No categories
    Translate
     
     
    Export citation  
     
    Bookmark  
  25. On the Kolmogorov-Chaitin Complexity for Short Sequences.Hector Zenil - unknown
    This is a presentation about joint work between Hector Zenil and Jean-Paul Delahaye. Zenil presents Experimental Algorithmic Theory as Algorithmic Information Theory and NKS, put together in a mixer. Algorithmic Complexity Theory defines the algorithmic complexity k(s) as the length of the shortest program that produces s. But since finding this short program is in general an undecidable question, the only way to approach k(s) is to use compression algorithms. He shows how to use the Compress function in (...)
     
    Export citation  
     
    Bookmark   3 citations  
  26.  23
    Kolmogorov–Loveland Randomness and Stochasticity.Wolfgang Merkle, Joseph S. Miller, André Nies, Jan Reimann & Frank Stephan - 2006 - Annals of Pure and Applied Logic 138 (1):183-210.
    An infinite binary sequence X is Kolmogorov–Loveland random if there is no computable non-monotonic betting strategy that succeeds on X in the sense of having an unbounded gain in the limit while betting successively on bits of X. A sequence X is KL-stochastic if there is no computable non-monotonic selection rule that selects from X an infinite, biased sequence.One of the major open problems in the field of effective randomness is whether Martin-Löf randomness is the same as KL-randomness. Our (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  27.  67
    Enumerations of the Kolmogorov Function.Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan & Leen Torenvliet - 2006 - Journal of Symbolic Logic 71 (2):501 - 528.
    A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x), f is a k(n)-enumerator if for every input x of length n, h(x) is among the first k(n) elements enumerated by f. If there is a k(n)-enumerator for h then h is called k(n)-enumerable. We also consider enumerators which are only A-recursive for some oracle A. We determine exactly how hard it is to enumerate the Kolmogorov function, (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  28.  18
    Shift-Complex Sequences.Mushfeq Khan - 2013 - Bulletin of Symbolic Logic 19 (2):199-215.
    A Martin-Löf random sequence is an infinite binary sequence with the property that every initial segment $\sigma$ has prefix-free Kolmogorov complexity $K$ at least $|\sigma| - c$, for some constant $c \in \omega$. Informally, initial segments of Martin-Löf randoms are highly complex in the sense that they are not compressible by more than a constant number of bits. However, all Martin-Löf randoms necessarily have contiguous substrings of arbitrarily low complexity. If we demand that all substrings of a (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  29. Every 2-Random Real is Kolmogorov Random.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (3):907-913.
    We study reals with infinitely many incompressible prefixes. Call $A \in 2^{\omega}$ Kolmogorot random if $(\exists^{\infty}n) C(A \upharpoonright n) \textgreater n - \mathcal{O}(1)$ , where C denotes plain Kolmogorov complexity. This property was suggested by Loveland and studied by $Martin-L\ddot{0}f$ , Schnorr and Solovay. We prove that 2-random reals are Kolmogorov random. Together with the converse-proved by Nies. Stephan and Terwijn [11]-this provides a natural characterization of 2-randomness in terms of plain complexity. We finish with a (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  30. Algorithm, Information.A. N. Kolmogorov - forthcoming - Complexity.
     
    Export citation  
     
    Bookmark  
  31. 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 (...) functions. In particular, $H^\infty$ is different from $H^A$, the prefix-free complexity of monotone machines with oracle A. (shrink)
    Direct download (11 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  32.  18
    Complex Tilings.Bruno Durand, Leonid A. Levin & Alexander Shen - 2008 - Journal of Symbolic Logic 73 (2):593-613.
    We study the minimal complexity of tilings of a plane with a given tile set. We note that every tile set admits either no tiling or some tiling with.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  33.  11
    Information-Theoretic Measures Predict the Human Judgment of Rhythm Complexity.Remi Fleurian, Tim Blackwell, Oded Ben‐Tal & Daniel Müllensiefen - 2017 - Cognitive Science 41 (3):800-813.
    To formalize the human judgment of rhythm complexity, we used five measures from information theory and algorithmic complexity to measure the complexity of 48 artificially generated rhythmic sequences. We compared these measurements to human prediction accuracy and easiness judgments obtained from a listening experiment, in which 32 participants guessed the last beat of each sequence. We also investigated the modulating effects of musical expertise and general pattern identification ability. Entropy rate and Kolmogorov complexity were correlated (...)
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark   2 citations  
  34.  9
    What Can Be Efficiently Reduced to the Kolmogorov-Random Strings?Eric Allender, Harry Buhrman & Michal Koucký - 2006 - Annals of Pure and Applied Logic 138 (1):2-19.
    We investigate the question of whether one can characterize complexity classes in terms of efficient reducibility to the set of Kolmogorov-random strings . This question arises because and , and no larger complexity classes are known to be reducible to in this way. We show that this question cannot be posed without explicitly dealing with issues raised by the choice of universal machine in the definition of Kolmogorov complexity. What follows is a list of some (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  35. Complexity and Information.Panu Raatikainen - 1998 - ”, Reports From the Department of Philosophy, University of Helsinki, 2.
    \Complexity" is a catchword of certain extremely popular and rapidly developing interdisciplinary new sciences, often called accordingly the sciences of complexity1. It is often closely associated with another notably popular but ambiguous word, \information" information, in turn, may be justly called the central new concept in the whole 20th century science. Moreover, the notion of information is regularly coupled with a key concept of thermodynamics, viz. entropy. And like this was not enough, it is quite usual to add one (...)
    Direct download  
    Translate
     
     
    Export citation  
     
    Bookmark  
  36.  11
    Π⁰₁ Classes with Complex Elements.Stephen Binns - 2008 - Journal of Symbolic Logic 73 (4):1341-1353.
    An infinite binary sequence is complex if the Kolmogorov complexity of its initial segments is bounded below by a computable function. We prove that a Π₁⁰ class P contains a complex element if and only if it contains a wtt-cover for the Cantor set. That is, if and only if for every Y⊆ω there is an X in P such that X≥wtt Y. We show that this is also equivalent to the Π₁⁰ class's being large in some sense. (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  37.  8
    About Segment Complexity of Turing Reductions.Valeriy K. Bulitko - 1999 - Mathematical Logic Quarterly 45 (4):561-571.
  38.  44
    Ecosystem Complexity Through the Lens of Logical Depth: Capturing Ecosystem Individuality.Cédric Gaucherel - 2014 - Biological Theory 9 (4):440-451.
    In this article, I will discuss possible differences between ecosystems and organisms on the basis of their intrinsic complexity. As the concept of complexity still remains highly debated, I propose here a practical and original way to measure the complexity of an ecosystem or an organism. For this purpose, I suggest using the concept of logical depth (LD) in a specific manner, in order to take into account the difficulty as well as the time needed to generate (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  39.  1
    On Reals with -Bounded Complexity and Compressive Power.Ian Herbert - 2016 - Journal of Symbolic Logic 81 (3):833-855.
    The Kolmogorov complexity of a finite binary string is the length of the shortest description of the string. This gives rise to some ‘standard’ lowness notions for reals: A isK-trivial if its initial segments have the lowest possible complexity and A is low forKif using A as an oracle does not decrease the complexity of strings by more than a constant factor. We weaken these notions by requiring the defining inequalities to hold only up to all${\rm{\Delta (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  40.  4
    On the Control of the 2D Navier–Stokes Equations with Kolmogorov Forcing.Nejib Smaoui, Alaa El-Kadri & Mohamed Zribi - 2021 - Complexity 2021:1-18.
    This paper is devoted to the control problem of a nonlinear dynamical system obtained by a truncation of the two-dimensional Navier–Stokes equations with periodic boundary conditions and with a sinusoidal external force along the x-direction. This special case of the 2D N-S equations is known as the 2D Kolmogorov flow. Firstly, the dynamics of the 2D Kolmogorov flow which is represented by a nonlinear dynamical system of seven ordinary differential equations of a laminar steady state flow regime and (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  41.  14
    Numerical Simulation of a Class of Three-Dimensional Kolmogorov Model with Chaotic Dynamic Behavior by Using Barycentric Interpolation Collocation Method.Mingjing Du, Junmei Li, Yulan Wang & Wei Zhang - 2019 - Complexity 2019:1-14.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  42. Complexity Measures for Maxwell–Boltzmann Distribution.Nicholas Smaal & José Roberto C. Piqueira - 2021 - Complexity 2021:1-6.
    This work presents a discussion about the application of the Kolmogorov; López-Ruiz, Mancini, and Calbet ; and Shiner, Davison, and Landsberg complexity measures to a common situation in physics described by the Maxwell–Boltzmann distribution. The first idea about complexity measure started in computer science and was proposed by Kolmogorov, calculated similarly to the informational entropy. Kolmogorov measure when applied to natural phenomena, presents higher values associated with disorder and lower to order. However, it is considered (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  43.  24
    Degrees of Monotone Complexity.William C. Calhoun - 2006 - Journal of Symbolic Logic 71 (4):1327 - 1341.
    Levin and Schnorr (independently) introduced the monotone complexity, Km(α), of a binary string α. We use monotone complexity to define the relative complexity (or relative randomness) of reals. We define a partial ordering ≤Km on 2ω by α ≤Km β iff there is a constant c such that Km(α ↾ n) ≤ Km(β ↾ n) + c for all n. The monotone degree of α is the set of all β such that α ≤Km β and β (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  44.  1
    Symmetries, Dynamics, and Control for the 2D Kolmogorov Flow.Nejib Smaoui - 2018 - Complexity 2018:1-15.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  45.  2
    The Interplay of Complexity and Subjectivity in Opinionated Discourse.Maite Taboada & Katharina Ehret - 2021 - Discourse Studies 23 (2):141-165.
    This paper brings together cutting-edge, quantitative corpus methodologies and discourse analysis to explore the relationship between text complexity and subjectivity as descriptive features of opinionated language. We are specifically interested in how text complexity and markers of subjectivity and argumentation interact in opinionated discourse. Our contributions include the marriage of quantitative approaches to text complexity with corpus linguistic methods for the study of subjectivity, in addition to large-scale analyses of evaluative discourse. As our corpus, we use the (...)
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark  
  46.  2
    On Some Complexity Characteristics of Immune Sets.Valeriy K. Bulitko - 1995 - Mathematical Logic Quarterly 41 (3):307-313.
    We suggest some new ways to effectivize the definitions of several classes of simple sets. On this basis, new completeness criterions for simple sets are obtained. In particular, we give descriptions of the class of complete maximal sets.
    Direct download  
     
    Export citation  
     
    Bookmark  
  47. Probability and Randomness.Antony Eagle - 2016 - In Alan Hájek & Christopher Hitchcock (eds.), The Oxford Handbook of Probability and Philosophy. Oxford, U.K.: Oxford University Press. pp. 440-459.
    Early work on the frequency theory of probability made extensive use of the notion of randomness, conceived of as a property possessed by disorderly collections of outcomes. Growing out of this work, a rich mathematical literature on algorithmic randomness and Kolmogorov complexity developed through the twentieth century, but largely lost contact with the philosophical literature on physical probability. The present chapter begins with a clarification of the notions of randomness and probability, conceiving of the former as a property (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  48. On Interpreting Chaitin's Incompleteness Theorem.Panu Raatikainen - 1998 - Journal of Philosophical Logic 27 (6):569-586.
    The aim of this paper is to comprehensively question the validity of the standard way of interpreting Chaitin's famous incompleteness theorem, which says that for every formalized theory of arithmetic there is a finite constant c such that the theory in question cannot prove any particular number to have Kolmogorov complexity larger than c. The received interpretation of theorem claims that the limiting constant is determined by the complexity of the theory itself, which is assumed to be (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  49.  29
    The K -Degrees, Low for K Degrees,and Weakly Low for K Sets.Joseph S. Miller - 2009 - Notre Dame Journal of Formal Logic 50 (4):381-391.
    We call A weakly low for K if there is a c such that $K^A(\sigma)\geq K(\sigma)-c$ for infinitely many σ; in other words, there are infinitely many strings that A does not help compress. We prove that A is weakly low for K if and only if Chaitin's Ω is A-random. This has consequences in the K-degrees and the low for K (i.e., low for random) degrees. Furthermore, we prove that the initial segment prefix-free complexity of 2-random reals is (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  50.  53
    On Proofs of the Incompleteness Theorems Based on Berry's Paradox by Vopěnka, Chaitin, and Boolos.Makoto Kikuchi, Taishi Kurahashi & Hiroshi Sakai - 2012 - Mathematical Logic Quarterly 58 (4-5):307-316.
    By formalizing Berry's paradox, Vopěnka, Chaitin, Boolos and others proved the incompleteness theorems without using the diagonal argument. In this paper, we shall examine these proofs closely and show their relationships. Firstly, we shall show that we can use the diagonal argument for proofs of the incompleteness theorems based on Berry's paradox. Then, we shall show that an extension of Boolos' proof can be considered as a special case of Chaitin's proof by defining a suitable Kolmogorov complexity. We (...)
    Direct download  
     
    Export citation  
     
    Bookmark   7 citations  
1 — 50 / 1000