This category needs an editor. We encourage you to help if you are qualified.
Volunteer, or read more about what this involves.
Related

Contents
156 found
Order:
1 — 50 / 156
  1. Strict Finitism's Unrequited Love for Computational Complexity.Noel Arteche - manuscript
    As a philosophy of mathematics, strict finitism has been traditionally concerned with the notion of feasibility, defended mostly by appealing to the physicality of mathematical practice. This has led the strict finitists to influence and be influenced by the field of computational complexity theory, under the widely held belief that this branch of mathematics is concerned with the study of what is “feasible in practice”. In this paper, I survey these ideas and contend that, contrary to popular belief, complexity theory (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  2. A contradiction and P=NP problem.Farzad Didehvar - manuscript
    Here, by introducing a version of “Unexpected hanging paradox” first we try to open a new way and a new explanation for paradoxes, similar to liar paradox. Also, we will show that we have a semantic situation which no syntactical logical system could support it. Finally, we propose a claim in Theory of Computation about the consistency of this Theory. One of the major claim is:Theory of Computation and Classical Logic leads us to a contradiction.
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  3. By considering Fuzzy time, P=BPP (P*=BPP*).Farzad Didehvar - manuscript
    The reason ability of considering time as a fuzzy concept is demonstrated in [7],[8]. One of the major questions which arise here is the new definitions of Complexity Classes. In [1],[2],…,[11] we show why we should consider time a fuzzy concept. It is noticeable to mention that that there were many attempts to consider time as a Fuzzy concept, in Philosophy, Mathematics and later in Physics but mostly based on the personal intuition of the authors or as a style of (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  4. (1 other version)Fuzzy Time, from Paradox to Paradox.Farzad Didehvar - manuscript
    Although Fuzzy logic and Fuzzy Mathematics is a widespread subject and there is a vast literature about it, yet the use of Fuzzy issues like Fuzzy sets and Fuzzy numbers was relatively rare in time concept. This could be seen in the Fuzzy time series. In addition, some attempts are done in fuzzing Turing Machines but seemingly there is no need to fuzzy time. Throughout this article, we try to change this picture and show why it is helpful to consider (...)
    Remove from this list  
     
    Export citation  
     
    Bookmark  
  5. Is Classical Mathematics Appropriate for Theory of Computation?Farzad Didehvar - manuscript
    Throughout this paper, we are trying to show how and why our Mathematical frame-work seems inappropriate to solve problems in Theory of Computation. More exactly, the concept of turning back in time in paradoxes causes inconsistency in modeling of the concept of Time in some semantic situations. As we see in the first chapter, by introducing a version of “Unexpected Hanging Paradox”,first we attempt to open a new explanation for some paradoxes. In the second step, by applying this paradox, it (...)
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  6. TC*.Didehvar Farzad - manuscript
    One of the possible hypotheses about time is to consider any instant of time as fuzzy number, so that two instants of time could be overlapped. Historically, some Mathematicians and Philosophers have had similar ideas like Brouwer and Husserl [5]. Throughout this article, the impact of this change on Theory of Computation and Complexity Theory are studied. In order to rebuild Theory of Computation in a more successful and productive approach to solve some major problems in Complexity Theory, the present (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  7. On probabilistic and causal reasoning with summation operators.Duligur Ibeling, Thomas Icard & Milan Mossé - forthcoming - Journal of Logic and Computation.
    Ibeling et al. (2023) axiomatize increasingly expressive languages of causation and probability, and Mossé et al. (2024) show that reasoning (specifically the satisfiability problem) in each causal language is as difficult, from a computational complexity perspective, as reasoning in its merely probabilistic or “correlational” counterpart. Introducing a summation operator to capture common devices that appear in applications—such as the do-calculus of Pearl (2009) for causal inference, which makes ample use of marginalization—van der Zander et al. (2023) partially extend these earlier (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  8. 1 Complexity of Computational Problems.D. B. Shmoys & E. Tardos - forthcoming - Complexity.
    Remove from this list  
     
    Export citation  
     
    Bookmark  
  9. Quantifying information in structural representations.Stephen Francis Mann - 2024 - Theoria. An International Journal for Theory, History and Foundations of Science:1-27.
    The goal of this paper is to show that the information carried by a structural representation can be decomposed into the information carried by its component parts. In particular, the relations between the components of a structural representation carry quantifiable information about the relations between components of their signifieds. It follows that the information carried by cognitive structural representations, including cognitive maps, can in principle be quantified and decomposed. This is perhaps surprising given that the formal tools of communication theory (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  10. Complex Emergent Model of Language Acquisition (CEMLA).Mir H. S. Quadri - 2024 - The Lumeni Notebook Research.
    The Complex Emergent Model of Language Acquisition (CEMLA) offers a new perspective on how humans acquire language, drawing on principles from complexity theory to explain this dynamic, adaptive process. Moving beyond linear and reductionist models, CEMLA views language acquisition as a system of interconnected nodes, feedback loops, and emergent patterns, operating at the edge of chaos. This framework captures the fluidity and adaptivity of language learning, highlighting how understanding and fluency arise through self-organisation, phase transitions, and interaction with diverse linguistic (...)
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  11. What is a machine? Exploring the meaning of ‘artificial’ in ‘artificial intelligence’.Stefan Schulz & Janna Hastings - 2024 - Cosmos+Taxis 12 (5+6):37-41.
    Landgrebe and Smith provide an argument for the impossibility of Artificial General Intelligence based on the limits of simulating complex systems. However, their argument presupposes a very contemporary vision of artificial intelligence as a model trained on data to produce an algorithm executable in a modern digital computing system. The present contribution explores what it means to be artificial. Current artificial intelligence approaches on modern computing systems are not the only conceivable way in which artificial intelligence technology might be created. (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  12. On the computational complexity of ethics: moral tractability for minds and machines.Jakob Stenseke - 2024 - Artificial Intelligence Review 57 (105):90.
    Why should moral philosophers, moral psychologists, and machine ethicists care about computational complexity? Debates on whether artificial intelligence (AI) can or should be used to solve problems in ethical domains have mainly been driven by what AI can or cannot do in terms of human capacities. In this paper, we tackle the problem from the other end by exploring what kind of moral machines are possible based on what computational systems can or cannot do. To do so, we analyze normative (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  13. On the difficulty of discovering mathematical proofs.Andrew Arana & Will Stafford - 2023 - Synthese 202 (2):1-29.
    An account of mathematical understanding should account for the differences between theorems whose proofs are “easy” to discover, and those whose proofs are difficult to discover. Though Hilbert seems to have created proof theory with the idea that it would address this kind of “discovermental complexity”, much more attention has been paid to the lengths of proofs, a measure of the difficulty of _verifying_ of a _given_ formal object that it is a proof of a given formula in a given (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  14. Tractable depth-bounded approximations to FDE and its satellites.A. Solares-Rojas & Marcello D'Agostino - 2023 - Journal of Logic and Computation 34 (5):815-855.
    FDE, LP and K3 are closely related to each other and admit of an intuitive informational interpretation. However, all these logics are co-NP complete, and so idealized models of how an agent can think. We address this issue by shifting to signed formulae, where the signs express imprecise values associated with two bipartitions of the corresponding set of standard values. We present proof systems whose operational rules are all linear and have only two structural branching rules that express a generalized (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  15. Computational complexity of hybrid interval temporal logics.Przemysław Andrzej Wałęga - 2023 - Annals of Pure and Applied Logic 174 (1):103165.
  16. The Maximization of Chaos.Ilexa Yardley - 2023 - Https://Medium.Com/the-Circular-Theory/.
  17. The Simple Solution to a Complex Problem.Ilexa Yardley - 2023 - Https://Medium.Com/the-Circular-Theory/.
    Conservation of the Circle is the only dynamic in Nature, and, therefore, the simple solution to the complex problem called ‘reality.’ (Also known as 'identity.') Financial, technological, and, therefore, psychological.
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  18. Computational complexity explains neural differences in quantifier verification.Heming Strømholt Bremnes, Jakub Szymanik & Giosuè Baggio - 2022 - Cognition 223 (C):105013.
  19. Tractable depth-bounded approximations to some propositional logics. Towards more realistic models of logical agents.A. Solares-Rojas - 2022 - Dissertation, University of Milan
    The depth-bounded approach seeks to provide realistic models of reasoners. Recognizing that most useful logics are idealizations in that they are either undecidable or likely to be intractable, the approach accounts for how they can be approximated in practice by resource-bounded agents. The approach has been applied to Classical Propositional Logic (CPL), yielding a hierarchy of tractable depth-bounded approximations to that logic, which in turn has been based on a KE/KI system. -/- This Thesis shows that the approach can be (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  20. Towards Tractable Approximations to Many-Valued Logics: the Case of First Degree Entailment.Alejandro Solares-Rojas & Marcello D’Agostino - 2022 - In Igor Sedlár (ed.), The Logica Yearbook 2021. College Publications. pp. 57-76.
    FDE is a logic that captures relevant entailment between implication-free formulae and admits of an intuitive informational interpretation as a 4-valued logic in which “a computer should think”. However, the logic is co-NP complete, and so an idealized model of how an agent can think. We address this issue by shifting to signed formulae where the signs express imprecise values associated with two distinct bipartitions of the set of standard 4 values. Thus, we present a proof system which consists of (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  21. Not All Computational Methods Are Effective Methods.Mark Sprevak - 2022 - Philosophies 7 (5):113.
    An effective method is a computational method that might, in principle, be executed by a human. In this paper, I argue that there are methods for computing that are not effective methods. The examples I consider are taken primarily from quantum computing, but these are only meant to be illustrative of a much wider class. Quantum inference and quantum parallelism involve steps that might be implemented in multiple physical systems, but cannot be implemented, or at least not at will, by (...)
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  22. The computational complexity of module socles.Huishan Wu - 2022 - Annals of Pure and Applied Logic 173 (5):103089.
  23. Sizing Up Free Will: The Scale of Compatibilism.Stuart Doyle - 2021 - Journal of Mind and Behavior 42 (3 & 4):271-289.
    Is human free will compatible with the natural laws of the universe? To “compatibilists” who see free actions as emanating from the wants and reasons of human agents, free will looks perfectly plausible. However, “incompatibilists” claim to see the more ultimate sources of human action. The wants and reasons of agents are said to be caused by physical processes which are themselves mere natural results of the previous state of the world and the natural laws which govern it. This paper (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  24. Recursive axiomatisations from separation properties.Rob Egrot - 2021 - Journal of Symbolic Logic 86 (3):1228-1258.
    We define a fragment of monadic infinitary second-order logic corresponding to an abstract separation property, We use this to define the concept of a separation subclass. We use model theoretic techniques and games to show that separation subclasses whose axiomatisations are recursively enumerable in our second-order fragment can also be recursively axiomatised in their original first-order language. We pin down the expressive power of this formalism with respect to first-order logic, and investigate some questions relating to decidability and computational complexity. (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  25. Computable irrational numbers with representations of surprising complexity.Ivan Georgiev, Lars Kristiansen & Frank Stephan - 2021 - Annals of Pure and Applied Logic 172 (2):102893.
  26. What Have Google’s Random Quantum Circuit Simulation Experiments Demonstrated about Quantum Supremacy?Jack K. Horner & John Symons - 2021 - In Hamid R. Arabnia, Leonidas Deligiannidis, Fernando G. Tinetti & Quoc-Nam Tran (eds.), Advances in Software Engineering, Education, and E-Learning: Proceedings From Fecs'20, Fcs'20, Serp'20, and Eee'20. Springer.
    Quantum computing is of high interest because it promises to perform at least some kinds of computations much faster than classical computers. Arute et al. 2019 (informally, “the Google Quantum Team”) report the results of experiments that purport to demonstrate “quantum supremacy” – the claim that the performance of some quantum computers is better than that of classical computers on some problems. Do these results close the debate over quantum supremacy? We argue that they do not. In the following, we (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  27. The canonical pairs of bounded depth Frege systems.Pavel Pudlák - 2021 - Annals of Pure and Applied Logic 172 (2):102892.
    The canonical pair of a proof system P is the pair of disjoint NP sets where one set is the set of all satisfiable CNF formulas and the other is the set of CNF formulas that have P-proofs bounded by some polynomial. We give a combinatorial characterization of the canonical pairs of depth d Frege systems. Our characterization is based on certain games, introduced in this article, that are parametrized by a number k, also called the depth. We show that (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  28. The Physics of God and the Quantum Gravity Theory of Everything: And Other Selected Works.James Redford (ed.) - 2021 - Chișinău, Moldova: Eliva Press.
    James Redford, The Physics of God and the Quantum Gravity Theory of Everything: And Other Selected Works (Chișinău, Moldova: Eliva Press, 2021), 268 pp., ISBN-10: 1636482775, ISBN-13: 9781636482774.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  29. Computational complexity for bounded distributive lattices with negation.Dmitry Shkatov & C. J. Van Alten - 2021 - Annals of Pure and Applied Logic 172 (7):102962.
    We study the computational complexity of the universal and quasi-equational theories of classes of bounded distributive lattices with a negation operation, i.e., a unary operation satisfying a subset of the properties of the Boolean negation. The upper bounds are obtained through the use of partial algebras. The lower bounds are either inherited from the equational theory of bounded distributive lattices or obtained through a reduction of a global satisfiability problem for a suitable system of propositional modal logic.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  30. The Key to Complexity.Ilexa Yardley - 2021 - Https://Medium.Com/the-Circular-Theory/.
    Complexity is dependent on the circular-linear relationship between an individual and a group, meaning we cannot use 'observation' to tell us what we need to know (to explain complexity).
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark  
  31. Strengthening Weak Emergence.Nora Berenstain - 2020 - Erkenntnis 87 (5):2457-2474.
    Bedau's influential (1997) account analyzes weak emergence in terms of the non-derivability of a system’s macrostates from its microstates except by simulation. I offer an improved version of Bedau’s account of weak emergence in light of insights from information theory. Non-derivability alone does not guarantee that a system’s macrostates are weakly emergent. Rather, it is non-derivability plus the algorithmic compressibility of the system’s macrostates that makes them weakly emergent. I argue that the resulting information-theoretic picture provides a metaphysical account of (...)
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  32. Proof Theory for Positive Logic with Weak Negation.Marta Bílková & Almudena Colacito - 2020 - Studia Logica 108 (4):649-686.
    Proof-theoretic methods are developed for subsystems of Johansson’s logic obtained by extending the positive fragment of intuitionistic logic with weak negations. These methods are exploited to establish properties of the logical systems. In particular, cut-free complete sequent calculi are introduced and used to provide a proof of the fact that the systems satisfy the Craig interpolation property. Alternative versions of the calculi are later obtained by means of an appropriate loop-checking history mechanism. Termination of the new calculi is proved, and (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  33. (1 other version)Representation and Reality by Language: How to make a home quantum computer?Vasil Penchev - 2020 - Philosophy of Science eJournal (Elsevier: SSRN) 13 (34):1-14.
    A set theory model of reality, representation and language based on the relation of completeness and incompleteness is explored. The problem of completeness of mathematics is linked to its counterpart in quantum mechanics. That model includes two Peano arithmetics or Turing machines independent of each other. The complex Hilbert space underlying quantum mechanics as the base of its mathematical formalism is interpreted as a generalization of Peano arithmetic: It is a doubled infinite set of doubled Peano arithmetics having a remarkable (...)
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  34. Two Strategies to Infinity: Completeness and Incompleteness. The Completeness of Quantum Mechanics.Vasil Penchev - 2020 - High Performance Computing eJournal 12 (11):1-8.
    Two strategies to infinity are equally relevant for it is as universal and thus complete as open and thus incomplete. Quantum mechanics is forced to introduce infinity implicitly by Hilbert space, on which is founded its formalism. One can demonstrate that essential properties of quantum information, entanglement, and quantum computer originate directly from infinity once it is involved in quantum mechanics. Thus, thеse phenomena can be elucidated as both complete and incomplete, after which choice is the border between them. A (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  35. A Mathematical Model of Quantum Computer by Both Arithmetic and Set Theory.Vasil Penchev - 2020 - Information Theory and Research eJournal 1 (15):1-13.
    A practical viewpoint links reality, representation, and language to calculation by the concept of Turing (1936) machine being the mathematical model of our computers. After the Gödel incompleteness theorems (1931) or the insolvability of the so-called halting problem (Turing 1936; Church 1936) as to a classical machine of Turing, one of the simplest hypotheses is completeness to be suggested for two ones. That is consistent with the provability of completeness by means of two independent Peano arithmetics discussed in Section I. (...)
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  36. Integrated Information Theory as a Conplexity Science Approach to Consciousness.L. H. Favela - 2019 - Journal of Consciousness Studies 26 (1-2):21-47.
    I claim that the integrated information theory of consciousness is a complexity science approach to consciousness. In general, complexity science investigates phenomena comprised of numerous non-linearly interacting parts, where global-scale behaviour and structures are irreducible to activities and properties of its constituent parts at local scales. I draw attention to some key features of IIT and complexity science in order to defend the claim that IIT is properly understood within the broader theoretical framework of complexity science. Doing so has the (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark   3 citations  
  37. (1 other version)Proof Compression and NP Versus PSPACE.L. Gordeev & E. H. Haeusler - 2019 - Studia Logica 107 (1):53-83.
    We show that arbitrary tautologies of Johansson’s minimal propositional logic are provable by “small” polynomial-size dag-like natural deductions in Prawitz’s system for minimal propositional logic. These “small” deductions arise from standard “large” tree-like inputs by horizontal dag-like compression that is obtained by merging distinct nodes labeled with identical formulas occurring in horizontal sections of deductions involved. The underlying geometric idea: if the height, h(∂), and the total number of distinct formulas, ϕ(∂), of a given tree-like deduction ∂ of a minimal (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  38. Universality, Invariance, and the Foundations of Computational Complexity in the light of the Quantum Computer.Michael Cuffaro - 2018 - In Hansson Sven Ove (ed.), Technology and Mathematics: Philosophical and Historical Investigations. Cham, Switzerland: Springer Verlag. pp. 253-282.
    Computational complexity theory is a branch of computer science dedicated to classifying computational problems in terms of their difficulty. While computability theory tells us what we can compute in principle, complexity theory informs us regarding our practical limits. In this chapter I argue that the science of \emph{quantum computing} illuminates complexity theory by emphasising that its fundamental concepts are not model-independent, but that this does not, as some suggest, force us to radically revise the foundations of the theory. For model-independence (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  39. Rational analysis, intractability, and the prospects of ‘as if’-explanations.Iris van Rooij, Johan Kwisthout, Todd Wareham & Cory Wright - 2018 - Synthese 195 (2):491-510.
    Despite their success in describing and predicting cognitive behavior, the plausibility of so-called ‘rational explanations’ is often contested on the grounds of computational intractability. Several cognitive scientists have argued that such intractability is an orthogonal pseudoproblem, however, since rational explanations account for the ‘why’ of cognition but are agnostic about the ‘how’. Their central premise is that humans do not actually perform the rational calculations posited by their models, but only act as if they do. Whether or not the problem (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  40. On the Significance of the Gottesman–Knill Theorem.Michael E. Cuffaro - 2017 - British Journal for the Philosophy of Science 68 (1):91-121.
    According to the Gottesman–Knill theorem, quantum algorithms that utilize only the operations belonging to a certain restricted set are efficiently simulable classically. Since some of the operations in this set generate entangled states, it is commonly concluded that entanglement is insufficient to enable quantum computers to outperform classical computers. I argue in this article that this conclusion is misleading. First, the statement of the theorem is, on reflection, already evident when we consider Bell’s and related inequalities in the context of (...)
    Remove from this list   Direct download (11 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  41. Incompleteness in the Finite Domain.Pavel Pudlák - 2017 - Bulletin of Symbolic Logic 23 (4):405-441.
    Motivated by the problem of finding finite versions of classical incompleteness theorems, we present some conjectures that go beyond NP ≠ coNP. These conjectures formally connect computational complexity with the difficulty of proving some sentences, which means that high computational complexity of a problem associated with a sentence implies that the sentence is not provable in a weak theory, or requires a long proof. Another reason for putting forward these conjectures is that some results in proof complexity seem to be (...)
    Remove from this list   Direct download (5 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  42. Human-Human Stigmergy.Ted Lewis & Leslie Marsh - 2016 - Cognitive Systems Research 38 (June):1-60.
  43. Membrane fission: A computational complexity perspective.Luis F. Macías-Ramos, Bosheng Song, Luis Valencia-Cabrera, Linqiang Pan & Mario J. Pérez-jiménez - 2016 - Complexity 21 (6):321-334.
    Remove from this list   Direct download  
     
    Export citation  
     
    Bookmark   2 citations  
  44. The Unexplained Intellect: Complexity, Time, and the Metaphysics of Embodied Thought.Christopher Mole - 2016 - New York: Routledge.
    The relationship between intelligent systems and their environment is at the forefront of research in cognitive science. The Unexplained Intellect: Complexity, Time, and the Metaphysics of Embodied Thought shows how computational complexity theory and analytic metaphysics can together illuminate long-standing questions about the importance of that relationship. It argues that the most basic facts about a mind cannot just be facts about mental states, but must include facts about the dynamic, interactive mental occurrences that take place when a creature encounters (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  45. Quantifiers and Cognition: Logical and Computational Perspectives.Jakub Szymanik - 2016 - Springer.
    This volume on the semantic complexity of natural language explores the question why some sentences are more difficult than others. While doing so, it lays the groundwork for extending semantic theory with computational and cognitive aspects by combining linguistics and logic with computations and cognition. -/- Quantifier expressions occur whenever we describe the world and communicate about it. Generalized quantifier theory is therefore one of the basic tools of linguistics today, studying the possible meanings and the inferential power of quantifier (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark   15 citations  
  46. How-Possibly Explanations in (Quantum) Computer Science.Michael E. Cuffaro - 2015 - Philosophy of Science 82 (5):737-748.
    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 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 subsequently asking a (...)
    Remove from this list   Direct download (9 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  47. Counting Steps: a Finitist Interpretation of Objective Probability in Physics.Amit Hagar & Giuseppe Sergioli - 2015 - Epistemologia 37 (2):262-275.
    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 (2 more)  
     
    Export citation  
     
    Bookmark  
  48. Отвъд машината на Тюринг: квантовият компютър.Vasil Penchev - 2014 - Sofia: BAS: ISSK (IPS).
    Quantum computer is considered as a generalization of Turing machine. The bits are substituted by qubits. In turn, a "qubit" is the generalization of "bit" referring to infinite sets or series. It extends the consept of calculation from finite processes and algorithms to infinite ones, impossible as to any Turing machines (such as our computers). However, the concept of quantum computer mets all paradoxes of infinity such as Gödel's incompletness theorems (1931), etc. A philosophical reflection on how quantum computer might (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  49. Why philosophers should care about computational complexity.Scott Aaronson - 2013 - Computability: Turing, Gödel, Church, and Beyond:261--328.
    One might think that, once we know something is computable, how efficiently it can be computed is a practical question with little further philosophical importance. In this essay, I offer a detailed case that one would be wrong. In particular, I argue that computational complexity theory---the field that studies the resources needed to solve computational problems---leads to new perspectives on the nature of mathematical knowledge, the strong AI debate, computationalism, the problem of logical omniscience, Hume's problem of induction and Goodman's (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark   37 citations  
  50. The Semimeasure Property of Algorithmic Probability -- “Feature‘ or “Bug‘?Douglas Campbell - 2013 - In David L. Dowe (ed.), Algorithmic Probability and Friends. Bayesian Prediction and Artificial Intelligence: Papers From the Ray Solomonoff 85th Memorial Conference, Melbourne, Vic, Australia, November 30 -- December 2, 2011. Springer. pp. 79--90.
    An unknown process is generating a sequence of symbols, drawn from an alphabet, A. Given an initial segment of the sequence, how can one predict the next symbol? Ray Solomonoff’s theory of inductive reasoning rests on the idea that a useful estimate of a sequence’s true probability of being outputted by the unknown process is provided by its algorithmic probability (its probability of being outputted by a species of probabilistic Turing machine). However algorithmic probability is a “semimeasure”: i.e., the sum, (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
1 — 50 / 156