Switch to: References

Add citations

You must login to add citations.
  1. The Abstraction/Representation Account of Computation and Subjective Experience.Jochen Szangolies - 2020 - Minds and Machines 30 (2):259-299.
    I examine the abstraction/representation theory of computation put forward by Horsman et al., connecting it to the broader notion of modeling, and in particular, model-based explanation, as considered by Rosen. I argue that the ‘representational entities’ it depends on cannot themselves be computational, and that, in particular, their representational capacities cannot be realized by computational means, and must remain explanatorily opaque to them. I then propose that representation might be realized by subjective experience, through being the bearer of the structure (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Some Non-Recursive Classes of Thue Systems With Solvable Word Problem.Ann Yasuhara - 1974 - Mathematical Logic Quarterly 20 (8-12):121-132.
    Download  
     
    Export citation  
     
    Bookmark  
  • Some Reflections on the Foundations of Ordinary Recursion Theory and a New Proposal.George Tourlakis - 1986 - Mathematical Logic Quarterly 32 (31-34):503-515.
    Download  
     
    Export citation  
     
    Bookmark  
  • Relativized Halting Problems.Alan L. Selman - 1974 - Mathematical Logic Quarterly 20 (13-18):193-198.
    Download  
    Translate
     
     
    Export citation  
     
    Bookmark   2 citations  
  • The Nature of Appearance in Kant’s Transcendentalism: A Seman- Tico-Cognitive Analysis.Sergey L. Katrechko - 2018 - Kantian Journal 37 (3):41-55.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Splitting Properties of {$N$}-C.E. Enumeration Degrees.I. Sh Kalimullin - 2002 - Journal of Symbolic Logic 67 (2):537-546.
    It is proved that if 1 $\langle \mathscr{D}_{2n}, \leq, P\rangle$ and $\langle \mathscr{D}_{2n}, \leq, P\rangle$ are not elementary equivalent where P is the predicate P(a) = "a is a Π 0 1 e-degree".
    Download  
     
    Export citation  
     
    Bookmark  
  • Arithmetical Analogues of Productive and Universal Sets.Bruce M. Horowitz - 1982 - Mathematical Logic Quarterly 28 (14-18):203-210.
    Download  
     
    Export citation  
     
    Bookmark  
  • An Isomorphism Type of Arithmetically Productive Sets.Bruce M. Horowitz - 1982 - Mathematical Logic Quarterly 28 (14-18):211-214.
    Download  
     
    Export citation  
     
    Bookmark  
  • Die Struktur des Halbverbandes der Effektiven Numerierungen.Bernhard Goetze - 1974 - Mathematical Logic Quarterly 20 (8-12):183-188.
    Download  
    Translate
     
     
    Export citation  
     
    Bookmark  
  • Unentscheidbarkeitsgrade Rekursiver Funktionen.Bernhard Goetze - 1974 - Mathematical Logic Quarterly 20 (8-12):189-191.
    Download  
    Translate
     
     
    Export citation  
     
    Bookmark  
  • Every Polynomial-Time 1-Degree Collapses If and Only If P = PSPACE.Stephen A. Fenner, Stuart A. Kurtz & James S. Royer - 2004 - Journal of Symbolic Logic 69 (3):713-741.
    A set A is m-reducible to B if and only if there is a polynomial-time computable function f such that, for all x, x∈ A if and only if f ∈ B. Two sets are: 1-equivalent if and only if each is m-reducible to the other by one-one reductions; p-invertible equivalent if and only if each is m-reducible to the other by one-one, polynomial-time invertible reductions; and p-isomorphic if and only if there is an m-reduction from one set to the (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Reduzierbarkeit von Berechenbaren Numerierungen von P1.Josef Falkinger - 1980 - Mathematical Logic Quarterly 26 (28-30):445-458.
    Download  
    Translate
     
     
    Export citation  
     
    Bookmark  
  • Incompleteness Via Paradox and Completeness.Walter Dean - 2020 - Review of Symbolic Logic 13 (3):541-592.
    This paper explores the relationship borne by the traditional paradoxes of set theory and semantics to formal incompleteness phenomena. A central tool is the application of the Arithmetized Completeness Theorem to systems of second-order arithmetic and set theory in which various “paradoxical notions” for first-order languages can be formalized. I will first discuss the setting in which this result was originally presented by Hilbert & Bernays and also how it was later adapted by Kreisel and Wang in order to obtain (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Trial and Error Mathematics II: Dialectical Sets and Quasidialectical Sets, Their Degrees, and Their Distribution Within the Class of Limit Sets.Jacopo Amidei, Duccio Pianigiani, Luca San Mauro & Andrea Sorbi - 2016 - Review of Symbolic Logic 9 (4):810-835.
    Download  
     
    Export citation  
     
    Bookmark  
  • Trial and Error Mathematics I: Dialectical and Quasidialectical Systems.Jacopo Amidei, Duccio Pianigiani, Luca San Mauro, Giulia Simi & Andrea Sorbi - 2016 - Review of Symbolic Logic 9 (2):299-324.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • On the Concept of Complexity and its Relationship to the Methodology of Policy-Oriented Research.Hannu Nurmi - 1974 - Social Science Information 13 (1):55-80.
    Download  
     
    Export citation  
     
    Bookmark  
  • Weaker variants of infinite time Turing machines.Matteo Bianchetti - 2020 - Archive for Mathematical Logic 59 (3):335-365.
    Infinite time Turing machines represent a model of computability that extends the operations of Turing machines to transfinite ordinal time by defining the content of each cell at limit steps to be the lim sup of the sequences of previous contents of that cell. In this paper, we study a computational model obtained by replacing the lim sup rule with an ‘eventually constant’ rule: at each limit step, the value of each cell is defined if and only if the content (...)
    Download  
    Translate
     
     
    Export citation  
     
    Bookmark  
  • Scott sentences for equivalence structures.Sara B. Quinn - 2020 - Archive for Mathematical Logic 59 (3):453-460.
    For a computable structure \, if there is a computable infinitary Scott sentence, then the complexity of this sentence gives an upper bound for the complexity of the index set \\). If we can also show that \\) is m-complete at that level, then there is a correspondence between the complexity of the index set and the complexity of a Scott sentence for the structure. There are results that suggest that these complexities will always match. However, it was shown in (...)
    Download  
    Translate
     
     
    Export citation  
     
    Bookmark  
  • A note on uniform density in weak arithmetical theories.Duccio Pianigiani & Andrea Sorbi - forthcoming - Archive for Mathematical Logic:1-15.
    Answering a question raised by Shavrukov and Visser :569–582, 2014), we show that the lattice of \-sentences ) over any computable enumerable consistent extension T of \ is uniformly dense. We also show that for every \ and \ refer to the known hierarchies of arithmetical formulas introduced by Burr for intuitionistic arithmetic) the lattices of \-sentences over any c.e. consistent extension T of the intuitionistic version of Robinson Arithmetic \ are uniformly dense. As an immediate consequence of the proof, (...)
    Download  
    Translate
     
     
    Export citation  
     
    Bookmark  
  • A Unified Theory of Truth and Paradox.Lorenzo Rossi - 2019 - Review of Symbolic Logic 12 (2):209-254.
    The sentences employed in semantic paradoxes display a wide range of semantic behaviours. However, the main theories of truth currently available either fail to provide a theory of paradox altogether, or can only account for some paradoxical phenomena by resorting to multiple interpretations of the language. In this paper, I explore the wide range of semantic behaviours displayed by paradoxical sentences, and I develop a unified theory of truth and paradox, that is a theory of truth that also provides a (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • On Σ1 1 Equivalence Relations Over the Natural Numbers.Ekaterina B. Fokina & Sy-David Friedman - 2012 - Mathematical Logic Quarterly 58 (1-2):113-124.
    We study the structure of Σ11 equivalence relations on hyperarithmetical subsets of ω under reducibilities given by hyperarithmetical or computable functions, called h-reducibility and FF-reducibility, respectively. We show that the structure is rich even when one fixes the number of properly equation imagei.e., Σ11 but not equation image equivalence classes. We also show the existence of incomparable Σ11 equivalence relations that are complete as subsets of ω × ω with respect to the corresponding reducibility on sets. We study complete Σ11 (...)
    Download  
     
    Export citation  
     
    Bookmark   6 citations  
  • Logique mathématique et philosophie des mathématiques.Yvon Gauthier - 1971 - Dialogue 10 (2):243-275.
    Pour le philosophe intéressé aux structures et aux fondements du savoir théorétique, à la constitution d'une « méta-théorétique «, θεωρíα., qui, mieux que les « Wissenschaftslehre » fichtéenne ou husserlienne et par-delà les débris de la métaphysique, veut dans une intention nouvelle faire la synthèse du « théorétique », la logique mathématique se révèle un objet privilégié.
    Download  
    Translate
     
     
    Export citation  
     
    Bookmark  
  • Parsimony Hierarchies for Inductive Inference.Andris Ambainis, John Case, Sanjay Jain & Mandayam Suraj - 2004 - Journal of Symbolic Logic 69 (1):287-327.
    Freivalds defined an acceptable programming system independent criterion for learning programs for functions in which the final programs were required to be both correct and "nearly" minimal size, i.e., within a computable function of being purely minimal size. Kinber showed that this parsimony requirement on final programs limits learning power. However, in scientific inference, parsimony is considered highly desirable. A lim-computablefunction is (by definition) one calculable by a total procedure allowed to change its mind finitely many times about its output. (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Methodologies for Studying Human Knowledge.John R. Anderson - 1987 - Behavioral and Brain Sciences 10 (3):467-477.
    The appropriate methodology for psychological research depends on whether one is studying mental algorithms or their implementation. Mental algorithms are abstract specifications of the steps taken by procedures that run in the mind. Implementational issues concern the speed and reliability of these procedures. The algorithmic level can be explored only by studying across-task variation. This contrasts with psychology's dominant methodology of looking for within-task generalities, which is appropriate only for studying implementational issues.The implementation-algorithm distinction is related to a number of (...)
    Download  
     
    Export citation  
     
    Bookmark   38 citations  
  • The Complexity of Learning SUBSEQ(A).Stephen Fenner, William Gasarch & Brian Postow - 2009 - Journal of Symbolic Logic 74 (3):939-975.
    Higman essentially showed that if A is any language then SUBSEQ(A) is regular, where SUBSEQ(A) is the language of all subsequences of strings in A. Let s1, s2, s3, . . . be the standard lexicographic enumeration of all strings over some finite alphabet. We consider the following inductive inference problem: given A(s1), A(s2), A(s3), . . . . learn, in the limit, a DFA for SUBSEQU). We consider this model of learning and the variants of it that are usually (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Computational Complexity Theory and the Philosophy of Mathematics†.Walter Dean - 2019 - Philosophia Mathematica 27 (3):381-439.
    Computational complexity theory is a subfield of computer science originating in computability theory and the study of algorithms for solving practical mathematical problems. Amongst its aims is classifying problems by their degree of difficulty — i.e., how hard they are to solve computationally. This paper highlights the significance of complexity theory relative to questions traditionally asked by philosophers of mathematics while also attempting to isolate some new ones — e.g., about the notion of feasibility in mathematics, the $\mathbf{P} \neq \mathbf{NP}$ (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Three Dogmas of First-Order Logic and Some Evidence-Based Consequences for Constructive Mathematics of Differentiating Between Hilbertian Theism, Brouwerian Atheism and Finitary Agnosticism.Bhupinder Singh Anand - manuscript
    We show how removing faith-based beliefs in current philosophies of classical and constructive mathematics admits formal, evidence-based, definitions of constructive mathematics; of a constructively well-defined logic of a formal mathematical language; and of a constructively well-defined model of such a language. -/- We argue that, from an evidence-based perspective, classical approaches which follow Hilbert's formal definitions of quantification can be labelled `theistic'; whilst constructive approaches based on Brouwer's philosophy of Intuitionism can be labelled `atheistic'. -/- We then adopt what may (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • The Truth Assignments That Differentiate Human Reasoning From Mechanistic Reasoning: The Evidence-Based Argument for Lucas' Goedelian Thesis.Bhupinder Singh Anand - 2016 - Cognitive Systems Research 40:35-45.
    We consider the argument that Tarski's classic definitions permit an intelligence---whether human or mechanistic---to admit finitary evidence-based definitions of the satisfaction and truth of the atomic formulas of the first-order Peano Arithmetic PA over the domain N of the natural numbers in two, hitherto unsuspected and essentially different, ways: (1) in terms of classical algorithmic verifiabilty; and (2) in terms of finitary algorithmic computability. We then show that the two definitions correspond to two distinctly different assignments of satisfaction and truth (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Agent‐Based Computational Models and Generative Social Science.Joshua M. Epstein - 1999 - Complexity 4 (5):41-60.
    Download  
     
    Export citation  
     
    Bookmark   34 citations  
  • Reconciling Simplicity and Likelihood Principles in Perceptual Organization.Nick Chater - 1996 - Psychological Review 103 (3):566-581.
    Download  
     
    Export citation  
     
    Bookmark   28 citations  
  • Strict Finitism, Feasibility, and the Sorites.Walter Dean - 2018 - Review of Symbolic Logic 11 (2):295-346.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Field’s Logic of Truth.Vann McGee - 2010 - Philosophical Studies 147 (3):421-432.
    Download  
     
    Export citation  
     
    Bookmark   6 citations  
  • Models and Computability.W. Dean - 2014 - Philosophia Mathematica 22 (2):143-166.
    Computationalism holds that our grasp of notions like ‘computable function’ can be used to account for our putative ability to refer to the standard model of arithmetic. Tennenbaum's Theorem has been repeatedly invoked in service of this claim. I will argue that not only do the relevant class of arguments fail, but that the result itself is most naturally understood as having the opposite of a reference-fixing effect — i.e., rather than securing the determinacy of number-theoretic reference, Tennenbaum's Theorem points (...)
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Thinking May Be More Than Computing.Peter Kugel - 1986 - Cognition 22 (2):137-198.
    Download  
     
    Export citation  
     
    Bookmark   12 citations  
  • Physics of Brain-Mind Interaction.John C. Eccles - 1990 - Behavioral and Brain Sciences 13 (4):662-663.
    Download  
     
    Export citation  
     
    Bookmark  
  • Conjectures and Questions From Gerald Sacks's Degrees of Unsolvability.Richard A. Shore - 1997 - Archive for Mathematical Logic 36 (4-5):233-253.
    . We describe the important role that the conjectures and questions posed at the end of the two editions of Gerald Sacks's Degrees of Unsolvability have had in the development of recursion theory over the past thirty years.
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Necessities and Necessary Truths: A Prolegomenon to the Use of Modal Logic in the Analysis of Intensional Notions.V. Halbach & P. Welch - 2009 - Mind 118 (469):71-100.
    In philosophical logic necessity is usually conceived as a sentential operator rather than as a predicate. An intensional sentential operator does not allow one to express quantified statements such as 'There are necessary a posteriori propositions' or 'All laws of physics are necessary' in first-order logic in a straightforward way, while they are readily formalized if necessity is formalized by a predicate. Replacing the operator conception of necessity by the predicate conception, however, causes various problems and forces one to reject (...)
    Download  
     
    Export citation  
     
    Bookmark   11 citations  
  • 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 good measure of (...)
    Download  
     
    Export citation  
     
    Bookmark   8 citations  
  • Substitutional Quantification and Mathematics. [REVIEW]Charles Parsons - 1982 - British Journal for the Philosophy of Science 33 (4):409-421.
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Earman on Underdetermination and Empirical Indistinguishability.Igor Douven & Leon Horsten - 1998 - Erkenntnis 49 (3):303-320.
    Earman (1993) distinguishes three notions of empirical indistinguishability and offers a rigorous framework to investigate how each of these notions relates to the problem of underdetermination of theory choice. He uses some of the results obtained in this framework to argue for a version of scientific anti- realism. In the present paper we first criticize Earman's arguments for that position. Secondly, we propose and motivate a modification of Earman's framework and establish several results concerning some of the notions of indistinguishability (...)
    Download  
     
    Export citation  
     
    Bookmark   12 citations  
  • The Philosophy of Computer Science.Raymond Turner - 2013 - Stanford Encyclopedia of Philosophy.
    Download  
     
    Export citation  
     
    Bookmark   7 citations  
  • Kurt Gödel.Juliette Kennedy - 2008 - Stanford Encyclopedia of Philosophy.
    Download  
     
    Export citation  
     
    Bookmark  
  • Self-Verifying Axiom Systems, the Incompleteness Theorem and Related Reflection Principles.Dan E. Willard - 2001 - Journal of Symbolic Logic 66 (2):536-596.
    We will study several weak axiom systems that use the Subtraction and Division primitives (rather than Addition and Multiplication) to formally encode the theorems of Arithmetic. Provided such axiom systems do not recognize Multiplication as a total function, we will show that it is feasible for them to verify their Semantic Tableaux, Herbrand, and Cut-Free consistencies. If our axiom systems additionally do not recognize Addition as a total function, they will be capable of recognizing the consistency of their Hilbert-style deductive (...)
    Download  
     
    Export citation  
     
    Bookmark   9 citations  
  • Algorithmic Information Theory and Undecidability.Panu Raatikainen - 2000 - Synthese 123 (2):217-225.
    Chaitin’s incompleteness result related to random reals and the halting probability has been advertised as the ultimate and the strongest possible version of the incompleteness and undecidability theorems. It is argued that such claims are exaggerations.
    Download  
     
    Export citation  
     
    Bookmark   6 citations  
  • Role of the Frame Problem in Fodor's Modularity Thesis.Eric Dietrich & Chris Fields - 1996 - In Ken Ford & Zenon Pylyshyn (eds.), The Robot's Dilemma Revisited.
    It is shown that the Fodor's interpretation of the frame problem is the central indication that his version of the Modularity Thesis is incompatible with computationalism. Since computationalism is far more plausible than this thesis, the latter should be rejected.
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Deciding Arithmetic Using SAD Computers.Mark Hogarth - 2004 - British Journal for the Philosophy of Science 55 (4):681-691.
    Presented here is a new result concerning the computational power of so-called SADn computers, a class of Turing-machine-based computers that can perform some non-Turing computable feats by utilising the geometry of a particular kind of general relativistic spacetime. It is shown that SADn can decide n-quantifier arithmetic but not (n+1)-quantifier arithmetic, a result that reveals how neatly the SADn family maps into the Kleene arithmetical hierarchy. Introduction Axiomatising computers The power of SAD computers Remarks regarding the concept of computability.
    Download  
     
    Export citation  
     
    Bookmark   18 citations  
  • Computability in Quantum Mechanics.Wayne C. Myrvold - 1995 - In Werner De Pauli-Schimanovich, Eckehart Köhler & Friedrich Stadler (eds.), Vienna Circle Institute Yearbook. Kluwer Academic Publishers. pp. 33-46.
    In this paper, the issues of computability and constructivity in the mathematics of physics are discussed. The sorts of questions to be addressed are those which might be expressed, roughly, as: Are the mathematical foundations of our current theories unavoidably non-constructive: or, Are the laws of physics computable?
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Two Episodes in the Unification of Logic and Topology.E. R. Grosholz - 1985 - British Journal for the Philosophy of Science 36 (2):147-157.
    Download  
     
    Export citation  
     
    Bookmark   5 citations  
  • Models and Recursivity.Walter Dean - manuscript
    It is commonly held that the natural numbers sequence 0, 1, 2,... possesses a unique structure. Yet by a well known model theoretic argument, there exist non-standard models of the formal theory which is generally taken to axiomatize all of our practices and intentions pertaining to use of the term “natural number.” Despite the structural similarity of this argument to the influential set theoretic indeterminacy argument based on the downward L ̈owenheim-Skolem theorem, most theorists agree that the number theoretic version (...)
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Counterpossibles in Science: The Case of Relative Computability.Matthias Jenny - 2018 - Noûs 52 (3):530-560.
    I develop a theory of counterfactuals about relative computability, i.e. counterfactuals such as 'If the validity problem were algorithmically decidable, then the halting problem would also be algorithmically decidable,' which is true, and 'If the validity problem were algorithmically decidable, then arithmetical truth would also be algorithmically decidable,' which is false. These counterfactuals are counterpossibles, i.e. they have metaphysically impossible antecedents. They thus pose a challenge to the orthodoxy about counterfactuals, which would treat them as uniformly true. What’s more, I (...)
    Download  
     
    Export citation  
     
    Bookmark   11 citations