This category needs an editor. We encourage you to help if you are qualified.
Volunteer, or read more about what this involves.
Related categories
Siblings:
11 found
Search inside:
(import / add options)   Sort by:
  1. Erik Aarts (1994). Proving Theorems of the Second Order Lambek Calculus in Polynomial Time. Studia Logica 53 (3):373 - 387.
    In the Lambek calculus of order 2 we allow only sequents in which the depth of nesting of implications is limited to 2. We prove that the decision problem of provability in the calculus can be solved in time polynomial in the length of the sequent. A normal form for proofs of second order sequents is defined. It is shown that for every proof there is a normal form proof with the same axioms. With this normal form we can give (...)
    Remove from this list | Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  2. Michael E. Cuffaro (forthcoming). How-Possibly Explanations in Quantum Computer Science. Philosophy of Science.
    A primary goal of quantum computer science is to find an explanation for the fact that quantum computers are more powerful than classical computers. In this paper I argue that to answer this question is to compare algorithmic processes of various kinds, and in so doing to describe the possibility spaces associated with these processes. By doing this we explain how it is possible for one process to outperform its rival. Further, in this and similar examples little is gained in (...)
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  3. Antony Eagle, Chance Versus Randomness. Stanford Encyclopedia of Philosophy.
    This article explores the connection between objective chance and the randomness of a sequence of outcomes. Discussion is focussed around the claim that something happens by chance iff it is random. This claim is subject to many objections. Attempts to save it by providing alternative theories of chance and randomness, involving indeterminism, unpredictability, and reductionism about chance, are canvassed. The article is largely expository, with particular attention being paid to the details of algorithmic randomness, a topic relatively unfamiliar to philosophers.
    Remove from this list |
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  4. Amit Hagar & Giuseppe Sergioli (forthcoming). Counting Steps: A Finitist Interpretation of Objective Probability in Physics. Epistemologia.
    We propose a new interpretation of objective deterministic chances in statistical physics based on physical computational complexity. This notion applies to a single physical system (be it an experimental set--up in the lab, or a subsystem of the universe), and quantifies (1) the difficulty to realize a physical state given another, (2) the 'distance' (in terms of physical resources) from a physical state to another, and (3) the size of the set of time--complexity functions that are compatible with the physical (...)
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  5. N. D. Jones (1997). Computability and Complexity: From a Programming Perspective Vol. 21. Mit Press.
    This makes his book especially valuable." -- Yuri Gurevich, Professor of Computer Science, University of Michigan Computability and complexity theory should be of central concern to practitioners as well as theorists.
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  6. Brian Rabern & Landon Rabern (2008). A Simple Solution to the Hardest Logic Puzzle Ever. Analysis 68 (2):105-112.
    We present the simplest solution ever to 'the hardest logic puzzle ever'. We then modify the puzzle to make it even harder and give a simple solution to the modified puzzle. The final sections investigate exploding god-heads and a two-question solution to the original puzzle.
    Remove from this list | Direct download (9 more)  
     
    My bibliography  
     
    Export citation  
  7. Samuel Rathmanner & Marcus Hutter (2011). A Philosophical Treatise of Universal Induction. Entropy 13 (6):1076-1136.
    Understanding inductive reasoning is a problem that has engaged mankind for thousands of years. This problem is relevant to a wide range of fields and is integral to the philosophy of science. It has been tackled by many great minds ranging from philosophers to scientists to mathematicians, and more recently computer scientists. In this article we argue the case for Solomonoff Induction, a formal inductive framework which combines algorithmic information theory with the Bayesian framework. Although it achieves excellent theoretical results (...)
    Remove from this list |
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  8. Tim S. Roberts (2001). Some Thoughts About the Hardest Logic Puzzle Ever. Journal of Philosophical Logic 30 (6):609-612.
    "The Hardest Logic Puzzle Ever" was first described by the late George Boolos in the Spring 1996 issue of the Harvard Review of Philosophy. Although not dissimilar in appearance from many other simpler puzzles involving gods (or tribesmen) who always tell the truth or always lie, this puzzle has several features that make the solution far from trivial. This paper examines the puzzle and describes a simpler solution than that originally proposed by Boolos.
    Remove from this list | Direct download (8 more)  
     
    My bibliography  
     
    Export citation  
  9. Hector Zenil, Towards a Stable Definition of Program-Size Complexity.
    We propose a test based on the theory of algorithmic complexity and an experimental evaluation of Levin's universal distribution to identify evidence in support of or in contravention of the claim that the world is algorithmic in nature. To this end statistical comparisons are undertaken of the frequency distributions of data from physical sources--repositories of information such as images, data stored in a hard drive, computer programs and DNA sequences--and the output frequency distributions generated by purely algorithmic means--by running abstract (...)
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  10. Hector Zenil, On the Kolmogorov-Chaitin Complexity for Short Sequences.
    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 Mathematica to (...)
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  11. Hector Zenil, Randomness Through Computation: Some Answers, More Questions.
    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 (...)
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation