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  
  • Recursively Enumerable Vector Spaces.G. Metakides - 1977 - Annals of Pure and Applied Logic 11 (2):147.
    Download  
     
    Export citation  
     
    Bookmark   51 citations  
  • 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  
  • Reduzierbarkeit von Berechenbaren Numerierungen von P1.Josef Falkinger - 1980 - Mathematical Logic Quarterly 26 (28-30):445-458.
    Download  
    Translate
     
     
    Export citation  
     
    Bookmark  
  • Tarski Hierarchies.Volker Halbach - 1995 - Erkenntnis 43 (3):339 - 367.
    The general notions of object- and metalanguage are discussed and as a special case of this relation an arbitrary first order language with an infinite model is expanded by a predicate symbol T0 which is interpreted as truth predicate for . Then the expanded language is again augmented by a new truth predicate T1 for the whole language plus T0. This process is iterated into the transfinite to obtain the Tarskian hierarchy of languages. It is shown that there are natural (...)
    Download  
     
    Export citation  
     
    Bookmark   6 citations  
  • 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  
  • Construction Theory, Self-Replication, and the Halting Problem.Hiroki Sayama - 2008 - Complexity 13 (5):16-22.
    Complexity is pleased to announce the installment of Prof Hiroki Sayama as its new Chief Editor. In this Editorial, Prof Sayama describes his feelings about his recent appointment, discusses some of the journal’s journey and relevance to current issues, and shares his vision and aspirations for its future.
    Download  
     
    Export citation  
     
    Bookmark  
  • 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  
  • Computing, Modelling, and Scientific Practice: Foundational Analyses and Limitations.Philippos Papayannopoulos - 2018 - Dissertation,
    This dissertation examines aspects of the interplay between computing and scientific practice. The appropriate foundational framework for such an endeavour is rather real computability than the classical computability theory. This is so because physical sciences, engineering, and applied mathematics mostly employ functions defined in continuous domains. But, contrary to the case of computation over natural numbers, there is no universally accepted framework for real computation; rather, there are two incompatible approaches --computable analysis and BSS model--, both claiming to formalise algorithmic (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Reverse Mathematics, Well-Quasi-Orders, and Noetherian Spaces.Emanuele Frittaion, Matthew Hendtlass, Alberto Marcone, Paul Shafer & Jeroen Van der Meeren - 2016 - Archive for Mathematical Logic 55 (3-4):431-459.
    A quasi-order Q induces two natural quasi-orders on P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{P}}$$\end{document}, but if Q is a well-quasi-order, then these quasi-orders need not necessarily be well-quasi-orders. Nevertheless, Goubault-Larrecq, pp. 453–462, 2007) showed that moving from a well-quasi-order Q to the quasi-orders on P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{P}}$$\end{document} preserves well-quasi-orderedness in a topological sense. Specifically, Goubault-Larrecq proved that the upper topologies of the induced quasi-orders on P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Topological Complexity of Locally Finite Ω-Languages.Olivier Finkel - 2008 - Archive for Mathematical Logic 47 (6):625-651.
    Locally finite omega languages were introduced by Ressayre [Formal languages defined by the underlying structure of their words. J Symb Log 53(4):1009–1026, 1988]. These languages are defined by local sentences and extend ω-languages accepted by Büchi automata or defined by monadic second order sentences. We investigate their topological complexity. All locally finite ω-languages are analytic sets, the class LOC ω of locally finite ω-languages meets all finite levels of the Borel hierarchy and there exist some locally finite ω-languages which are (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • What is Categorical Structuralism?Geoffrey Hellman - 2006 - In Johan van Benthem, Gerhard Heinzman, M. Rebushi & H. Visser (eds.), The Age of Alternative Logics. Springer. pp. 151--161.
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • 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  
  • Agent‐Based Computational Models and Generative Social Science.Joshua M. Epstein - 1999 - Complexity 4 (5):41-60.
    Download  
     
    Export citation  
     
    Bookmark   33 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  
  • 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  
  • 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  
  • 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  
  • Some Strongly Undecidable Natural Arithmetical Problems, with an Application to Intuitionistic Theories.Panu Raatikainen - 2003 - Journal of Symbolic Logic 68 (1):262-266.
    A natural problem from elementary arithmetic which is so strongly undecidable that it is not even Trial and Error decidable (in other words, not decidable in the limit) is presented. As a corollary, a natural, elementary arithmetical property which makes a difference between intuitionistic and classical theories is isolated.
    Download  
     
    Export citation  
     
    Bookmark  
  • Universal Computably Enumerable Equivalence Relations.Uri Andrews, Steffen Lempp, Joseph S. Miller, Keng Meng Ng, Luca San Mauro & Andrea Sorbi - 2014 - Journal of Symbolic Logic 79 (1):60-88.
    Download  
     
    Export citation  
     
    Bookmark   6 citations  
  • A Bounded Jump for the Bounded Turing Degrees.Bernard Anderson & Barbara Csima - 2014 - Notre Dame Journal of Formal Logic 55 (2):245-264.
    We define the bounded jump of $A$ by $A^{b}=\{x\in \omega \mid \exists i\leq x[\varphi_{i}\downarrow \wedge\Phi_{x}^{A\upharpoonright \!\!\!\upharpoonright \varphi_{i}}\downarrow ]\}$ and let $A^{nb}$ denote the $n$th bounded jump. We demonstrate several properties of the bounded jump, including the fact that it is strictly increasing and order-preserving on the bounded Turing degrees. We show that the bounded jump is related to the Ershov hierarchy. Indeed, for $n\geq2$ we have $X\leq_{bT}\emptyset ^{nb}\iff X$ is $\omega^{n}$-c.e. $\iff X\leq_{1}\emptyset ^{nb}$, extending the classical result that $X\leq_{bT}\emptyset '\iff (...)
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Cupping and Noncupping in the Enumeration Degrees of ∑20 Sets.S. Barry Cooper, Andrea Sorbi & Xiaoding Yi - 1996 - Annals of Pure and Applied Logic 82 (3):317-342.
    We prove the following three theorems on the enumeration degrees of ∑20 sets. Theorem A: There exists a nonzero noncuppable ∑20 enumeration degree. Theorem B: Every nonzero Δ20enumeration degree is cuppable to 0′e by an incomplete total enumeration degree. Theorem C: There exists a nonzero low Δ20 enumeration degree with the anticupping property.
    Download  
     
    Export citation  
     
    Bookmark   11 citations  
  • Constructive Logic and the Medvedev Lattice.Sebastiaan A. Terwijn - 2006 - Notre Dame Journal of Formal Logic 47 (1):73-82.
    We study the connection between factors of the Medvedev lattice and constructive logic. The algebraic properties of these factors determine logics lying in between intuitionistic propositional logic and the logic of the weak law of the excluded middle (also known as De Morgan, or Jankov, logic). We discuss the relation between the weak law of the excluded middle and the algebraic notion of join-reducibility. Finally we discuss autoreducible degrees.
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • Possible-Worlds Semantics for Modal Notions Conceived as Predicates.Volker Halbach, Hannes Leitgeb & Philip Welch - 2003 - Journal of Philosophical Logic 32 (2):179-223.
    If □ is conceived as an operator, i.e., an expression that gives applied to a formula another formula, the expressive power of the language is severely restricted when compared to a language where □ is conceived as a predicate, i.e., an expression that yields a formula if it is applied to a term. This consideration favours the predicate approach. The predicate view, however, is threatened mainly by two problems: Some obvious predicate systems are inconsistent, and possible-worlds semantics for predicates of (...)
    Download  
     
    Export citation  
     
    Bookmark   26 citations  
  • A Revenge-Immune Solution to the Semantic Paradoxes.Hartry Field - 2003 - Journal of Philosophical Logic 32 (2):139-177.
    The paper offers a solution to the semantic paradoxes, one in which we keep the unrestricted truth schema “True↔A”, and the object language can include its own metalanguage. Because of the first feature, classical logic must be restricted, but full classical reasoning applies in “ordinary” contexts, including standard set theory. The more general logic that replaces classical logic includes a principle of substitutivity of equivalents, which with the truth schema leads to the general intersubstitutivity of True with A within the (...)
    Download  
     
    Export citation  
     
    Bookmark   43 citations  
  • Vagueness and Formal Fuzzy Logic: Some Criticisms.Giangiacomo Gerla - 2017 - Logic and Logical Philosophy 26 (4).
    Download  
     
    Export citation  
     
    Bookmark  
  • Subsystems of Second-Order Arithmetic Between RCA0 and WKL0.Carl Mummert - 2008 - Archive for Mathematical Logic 47 (3):205-210.
    We study the Lindenbaum algebra ${\fancyscript{A}}$ (WKL o, RCA o) of sentences in the language of second-order arithmetic that imply RCA o and are provable from WKL o. We explore the relationship between ${\Sigma^1_1}$ sentences in ${\fancyscript{A}}$ (WKL o, RCA o) and ${\Pi^0_1}$ classes of subsets of ω. By applying a result of Binns and Simpson (Arch. Math. Logic 43(3), 399–414, 2004) about ${\Pi^0_1}$ classes, we give a specific embedding of the free distributive lattice with countably many generators into ${\fancyscript{A}}$ (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Axiomatizing Semantic Theories of Truth?Martin Fischer, Volker Halbach, Jönne Kriener & Johannes Stern - 2015 - Review of Symbolic Logic 8 (2):257-278.
    We discuss the interplay between the axiomatic and the semantic approach to truth. Often, semantic constructions have guided the development of axiomatic theories and certain axiomatic theories have been claimed to capture a semantic construction. We ask under which conditions an axiomatic theory captures a semantic construction. After discussing some potential criteria, we focus on the criterion of ℕ-categoricity and discuss its usefulness and limits.
    Download  
     
    Export citation  
     
    Bookmark   14 citations  
  • Neural Computation and the Computational Theory of Cognition.Gualtiero Piccinini & Sonya Bahar - 2013 - Cognitive Science 37 (3):453-488.
    We begin by distinguishing computationalism from a number of other theses that are sometimes conflated with it. We also distinguish between several important kinds of computation: computation in a generic sense, digital computation, and analog computation. Then, we defend a weak version of computationalism—neural processes are computations in the generic sense. After that, we reject on empirical grounds the common assimilation of neural computation to either analog or digital computation, concluding that neural computation is sui generis. Analog computation requires continuous (...)
    Download  
     
    Export citation  
     
    Bookmark   36 citations