Results for 'Theory of Computation'

1000+ found
Order:
  1.  8
    Proceedings of the 1986 Conference on Theoretical Aspects of Reasoning about Knowledge: March 19-22, 1988, Monterey, California.Joseph Y. Halpern, International Business Machines Corporation, American Association of Artificial Intelligence, United States & Association for Computing Machinery - 1986
    Direct download  
     
    Export citation  
     
    Bookmark  
  2. Scientific Theories of Computational Systems in Model Checking.Nicola Angius & Guglielmo Tamburrini - 2011 - Minds and Machines 21 (2):323-336.
    Model checking, a prominent formal method used to predict and explain the behaviour of software and hardware systems, is examined on the basis of reflective work in the philosophy of science concerning the ontology of scientific theories and model-based reasoning. The empirical theories of computational systems that model checking techniques enable one to build are identified, in the light of the semantic conception of scientific theories, with families of models that are interconnected by simulation relations. And the mappings between these (...)
    Direct download (14 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  3. Section 2. Model Theory.Va Vardanyan, On Provability Resembling Computability, Proving Aa Voronkov & Constructive Logic - 1989 - In Jens Erik Fenstad, Ivan Timofeevich Frolov & Risto Hilpinen (eds.), Logic, Methodology, and Philosophy of Science Viii: Proceedings of the Eighth International Congress of Logic, Methodology, and Philosophy of Science, Moscow, 1987. Sole Distributors for the U.S.A. And Canada, Elsevier Science.
    No categories
     
    Export citation  
     
    Bookmark  
  4. A theory of computational implementation.Michael Rescorla - 2014 - Synthese 191 (6):1277-1307.
    I articulate and defend a new theory of what it is for a physical system to implement an abstract computational model. According to my descriptivist theory, a physical system implements a computational model just in case the model accurately describes the system. Specifically, the system must reliably transit between computational states in accord with mechanical instructions encoded by the model. I contrast my theory with an influential approach to computational implementation espoused by Chalmers, Putnam, and others. I (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   23 citations  
  5.  4
    Yates [1970], who obtained a low minimal degree as a corollary to his con.of Minimal Degrees Below - 1996 - In S. B. Cooper, T. A. Slaman & S. S. Wainer (eds.), Computability, enumerability, unsolvability: directions in recursion theory. New York: Cambridge University Press. pp. 81.
    Direct download  
     
    Export citation  
     
    Bookmark  
  6. Theory of recursive functions and effective computability.Hartley Rogers - 1987 - Cambridge: MIT Press.
  7.  7
    ALPUK91: Proceedings of the 3rd UK Annual Conference on Logic Programming, Edinburgh, 10–12 April 1991.Tim Duncan, C. S. Mellish, Geraint A. Wiggins & British Computer Society - 1992 - Springer.
    Since its conception nearly 20 years ago, Logic Programming - the idea of using logic as a programming language - has been developed to the point where it now plays an important role in areas such as database theory, artificial intelligence and software engineering. However, there are still many challenging research issues to be addressed and the UK branch of the Association for Logic Programming was set up to provide a forum where the flourishing research community could discuss important (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  8.  25
    A Pragmatic Theory of Computational Artefacts.Alessandro G. Buda & Giuseppe Primiero - 2024 - Minds and Machines 34 (1):139-170.
    Some computational phenomena rely essentially on pragmatic considerations, and seem to undermine the independence of the specification from the implementation. These include software development, deviant uses, esoteric languages and recent data-driven applications. To account for them, the interaction between pragmatics, epistemology and ontology in computational artefacts seems essential, indicating the need to recover the role of the language metaphor. We propose a User Levels (ULs) structure as a pragmatic complement to the Levels of Abstraction (LoAs)-based structure defining the ontology and (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  9. The Theory of Computability Developed in Terms of Satisfaction.James Cain - 1999 - Notre Dame Journal of Formal Logic 40 (4):515-532.
    The notion of computability is developed through the study of the behavior of a set of languages interpreted over the natural numbers which contain their own fully defined satisfaction predicate and whose only other vocabulary is limited to "0", individual variables, the successor function, the identity relation and operators for disjunction, conjunction, and existential quantification.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  10.  21
    Theory of Computation.George J. Tourlakis - 2012 - Hoboken, N.J.: Wiley.
    In addition, this book contains tools that, in principle, can search a set of algorithms to see whether a problem is solvable, or more specifically, if it can be solved by an algorithm whose computations are efficient.
    Direct download  
     
    Export citation  
     
    Bookmark  
  11.  40
    Handbook of computability theory.Edward R. Griffor (ed.) - 1999 - New York: Elsevier.
    The chapters of this volume all have their own level of presentation. The topics have been chosen based on the active research interest associated with them. Since the interest in some topics is older than that in others, some presentations contain fundamental definitions and basic results while others relate very little of the elementary theory behind them and aim directly toward an exposition of advanced results. Presentations of the latter sort are in some cases restricted to a short survey (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  12.  41
    Elements of the Theory of Computation.Harry R. Lewis & Christos H. Papadimitriou - 1984 - Journal of Symbolic Logic 49 (3):989-990.
    Direct download  
     
    Export citation  
     
    Bookmark   41 citations  
  13.  20
    Fodor's New Theory of Computation and Information.J. Andrew Brook & Robert J. Stainton - unknown
  14. Against Structuralist Theories of Computational Implementation.Michael Rescorla - 2013 - British Journal for the Philosophy of Science 64 (4):681-707.
    Under what conditions does a physical system implement or realize a computation? Structuralism about computational implementation, espoused by Chalmers and others, holds that a physical system realizes a computation just in case the system instantiates a pattern of causal organization isomorphic to the computation’s formal structure. I argue against structuralism through counter-examples drawn from computer science. On my opposing view, computational implementation sometimes requires instantiating semantic properties that outstrip any relevant pattern of causal organization. In developing my (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   16 citations  
  15. Computational Theories of Conscious Experience: Between a Rock and a Hard Place.Gary Bartlett - 2012 - Erkenntnis 76 (2):195-209.
    Very plausibly, nothing can be a genuine computing system unless it meets an input-sensitivity requirement. Otherwise all sorts of objects, such as rocks or pails of water, can count as performing computations, even such as might suffice for mentality—thus threatening computationalism about the mind with panpsychism. Maudlin in J Philos 86:407–432, ( 1989 ) and Bishop ( 2002a , b ) have argued, however, that such a requirement creates difficulties for computationalism about conscious experience, putting it in conflict with the (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  16. Uniformly reflexive structures: towards an abstract theory of computability.Eric Gerhardt Wagner - 1963 - [New York: [S.N.].
  17.  33
    Model theory of deduction: a unified computational approach.Bruno G. Bara, Monica Bucciarelli & Vincenzo Lombardo - 2001 - Cognitive Science 25 (6):839-901.
    One of the most debated questions in psychology and cognitive science is the nature and the functioning of the mental processes involved in deductive reasoning. However, all existing theories refer to a specific deductive domain, like syllogistic, propositional or relational reasoning.Our goal is to unify the main types of deductive reasoning into a single set of basic procedures. In particular, we bring together the microtheories developed from a mental models perspective in a single theory, for which we provide a (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  18.  22
    The theory of ceers computes true arithmetic.Uri Andrews, Noah Schweber & Andrea Sorbi - 2020 - Annals of Pure and Applied Logic 171 (8):102811.
    We show that the theory of the partial order of computably enumerable equivalence relations (ceers) under computable reduction is 1-equivalent to true arithmetic. We show the same result for the structure comprised of the dark ceers and the structure comprised of the light ceers. We also show the same for the structure of L-degrees in the dark, light, or complete structure. In each case, we show that there is an interpretable copy of (N, +, \times) .
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  19.  69
    Towards a general theory of computability.Richard Montague - 1960 - Synthese 12 (4):429 - 438.
  20.  9
    Elements of the Theory of Computation.Harry R. Lewis & Christos H. Papadimitriou - 1998 - Prentice-Hall.
    Offering an introduction to algorithms, this work considers automata in the context of their applications, NP-completeness, Turing machine notation and Chomsky normal form.
    Direct download  
     
    Export citation  
     
    Bookmark  
  21. Function Logic and the Theory of Computability.Jaakko Hintikka - 2013 - APA Newsletter on Philosophy and Computers 13 (1):10-19.
    An important link between model theory and proof theory is to construe a deductive disproof of S as an attempted construction of a countermodel to it. In the function logic outlined here, this idea is implemented in such a way that different kinds of individuals can be introduced into the countermodel in any order whatsoever. This imposes connections between the length of the branches of the tree that a disproof is and their number. If there are already n (...)
     
    Export citation  
     
    Bookmark   1 citation  
  22.  16
    Review: Zohar Manna, Mathematical Theory of Computation[REVIEW]Andrzej Blikle - 1979 - Journal of Symbolic Logic 44 (1):122-124.
  23.  7
    Towards a General Theory of Computability.Richard Montague - 1964 - Journal of Symbolic Logic 29 (1):63-64.
    Direct download  
     
    Export citation  
     
    Bookmark  
  24.  29
    Finite axiomatizability for equational theories of computable groupoids.Peter Perkins - 1989 - Journal of Symbolic Logic 54 (3):1018-1022.
  25.  29
    A New Approach to Computing Using Informons and Holons: Towards a Theory of Computing Science.F. David de la Peña, Juan A. Lara, David Lizcano, María Aurora Martínez & Juan Pazos - 2020 - Foundations of Science 25 (4):1173-1201.
    The state of computing science and, particularly, software engineering and knowledge engineering is generally considered immature. The best starting point for achieving a mature engineering discipline is a solid scientific theory, and the primary reason behind the immaturity in these fields is precisely that computing science still has no such agreed upon underlying theory. As theories in other fields of science do, this paper formally establishes the fundamental elements and postulates making up a first attempt at a (...) in this field, considering the features and peculiarities of computing science. The fundamental elements of this approach are informons and holons, and it is a general and comprehensive theory of software engineering and knowledge engineering that related disciplines (e.g., information systems) can particularise and/or extend to take benefit from it (Lakatos’ concepts of core theory and protective belt theories). (shrink)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  26. Computation and Functionalism: Syntactic Theory of Mind Revisited.Murat Aydede - 2005 - In Gurol Irzik & Guven Guzeldere (eds.), Boston Studies in the History and Philosophy of Science. Springer.
    I argue that Stich's Syntactic Theory of Mind (STM) and a naturalistic narrow content functionalism run on a Language of Though story have the same exact structure. I elaborate on the argument that narrow content functionalism is either irremediably holistic in a rather destructive sense, or else doesn't have the resources for individuating contents interpersonally. So I show that, contrary to his own advertisement, Stich's STM has exactly the same problems (like holism, vagueness, observer-relativity, etc.) that he claims plague (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  27. P≠NP, By accepting to make a shift in the Theory (Time as a fuzzy concept) The Structure of a Theory (TC*, Theory of Computation based on Fuzzy time).Farzad Didehvar - manuscript
    In a series of articles we try to show the need of a novel Theory for Theory of Computation based on considering time as a Fuzzy concept. Time is a central concept In Physics. First we were forced to consider some changes and modifications in the Theories of Physics. In the second step and throughout this article we show the positive Impact of this modification on Theory of Computation and Complexity Theory to rebuild it (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  28.  51
    Categoricity of computable infinitary theories.W. Calvert, S. S. Goncharov, J. F. Knight & Jessica Millar - 2009 - Archive for Mathematical Logic 48 (1):25-38.
    Computable structures of Scott rank ${\omega_1^{CK}}$ are an important boundary case for structural complexity. While every countable structure is determined, up to isomorphism, by a sentence of ${\mathcal{L}_{\omega_1 \omega}}$ , this sentence may not be computable. We give examples, in several familiar classes of structures, of computable structures with Scott rank ${\omega_1^{CK}}$ whose computable infinitary theories are each ${\aleph_0}$ -categorical. General conditions are given, covering many known methods for constructing computable structures with Scott rank ${\omega_1^{CK}}$ , which guarantee that the (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  29. Implications of computer science theory for the simulation hypothesis.David Wolpert - manuscript
    The simulation hypothesis has recently excited renewed interest, especially in the physics and philosophy communities. However, the hypothesis specifically concerns {computers} that simulate physical universes, which means that to properly investigate it we need to couple computer science theory with physics. Here I do this by exploiting the physical Church-Turing thesis. This allows me to introduce a preliminary investigation of some of the computer science theoretic aspects of the simulation hypothesis. In particular, building on Kleene's second recursion theorem, I (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  30. 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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  31.  3
    Fundamentals of computation theory: proceedings of the 1977 International FCT-Conference, Poznán-Kórnik, Poland, September 19-23, 1977.Marek Karpiński (ed.) - 1977 - New York: Springer Verlag.
  32.  28
    Zohar Manna. Mathematical theory of computation. McGraw-Hill Book Company, New York etc. 1974, x + 448 pp. [REVIEW]Andrzej Blikle - 1979 - Journal of Symbolic Logic 44 (1):122-124.
  33.  51
    Can Computational Goals Inform Theories of Vision?Barton L. Anderson - 2015 - Topics in Cognitive Science 7 (2):274-286.
    One of the most lasting contributions of Marr's posthumous book is his articulation of the different “levels of analysis” that are needed to understand vision. Although a variety of work has examined how these different levels are related, there is comparatively little examination of the assumptions on which his proposed levels rest, or the plausibility of the approach Marr articulated given those assumptions. Marr placed particular significance on computational level theory, which specifies the “goal” of a computation, its (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  34. An analysis of the criteria for evaluating adequate theories of computation.Nir Fresco - 2008 - Minds and Machines 18 (3):379-401.
    This paper deals with the question: What are the criteria that an adequate theory of computation has to meet? 1. Smith's answer: it has to meet the empirical criterion (i.e. doing justice to computational practice), the conceptual criterion (i.e. explaining all the underlying concepts) and the cognitive criterion (i.e. providing solid grounds for computationalism). 2. Piccinini's answer: it has to meet the objectivity criterion (i.e. identifying computation as a matter of fact), the explanation criterion (i.e. explaining the (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  35.  18
    Saturation and stability in the theory of computation over the reals.Olivier Chapuis & Pascal Koiran - 1999 - Annals of Pure and Applied Logic 99 (1-3):1-49.
    This paper was motivated by the following two questions which arise in the theory of complexity for computation over ordered rings in the now famous computational model introduced by Blum, Shub and Smale: 1. is the answer to the question P = ?NP the same in every real-closed field?2. if P ≠ NP for , does there exist a problem of which is NP but neither P nor NP-complete ?Some unclassical complexity classes arise naturally in the study of (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  36. Implications of computer science theory for the simulation hypothesis.David Wolpert - manuscript
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark  
  37. Computational Theory of Mind.Marcin Milkowski - 2013 - Internet Encyclopedia of Philosophy.
    The Computational Theory of Mind (CTM) holds that the mind is a computer and that cognition is the manipulation of representations. CTM is commonly viewed as the main hypothesis in cognitive science, with classical CTM (related to the Language of Thought Hypothesis) being the most popular variant. However, other computational accounts of the mind either reject LOTH or do not subscribe to RTM. CTM proponents argue that it clarifies how thought and content are causally relevant in the physical world, (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  38.  38
    Theory of quantum computation and philosophy of mathematics. Part I.Krzysztof Wójtowicz - 2009 - Logic and Logical Philosophy 18 (3-4):313-332.
    The aim of this paper is to present some basic notions of the theory of quantum computing and to compare them with the basic notions of the classical theory of computation. I am convinced, that the results of quantum computation theory (QCT) are not only interesting in themselves, but also should be taken into account in discussions concerning the nature of mathematical knowledge. The philosophical discussion will however be postponed to another paper. QCT seems not (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  39.  32
    Richard Montague. Towards a general theory of computability. Synthese, vol. 12 no. 4 , pp. 429–438.Martin Davis - 1964 - Journal of Symbolic Logic 29 (1):63-64.
  40.  37
    Theories of reasoning and the computational explanation of everyday inference.Mike Oaksford & Nick Chater - 1995 - Thinking and Reasoning 1 (2):121 – 152.
  41.  12
    Computational Constraints in Cognitive Theories of Forgetting.Ullrich K. H. Ecker & Stephan Lewandowsky - 2012 - Frontiers in Psychology 3.
  42.  9
    Models of computation and formal languages.Ralph Gregory Taylor - 1998 - New York: Oxford University Press.
    This unique book presents a comprehensive and rigorous treatment of the theory of computability which is introductory yet self-contained. It takes a novel approach by looking at the subject using computation models rather than a limitation orientation, and is the first book of its kind to include software. Accompanying software simulations of almost all computational models are available for use in conjunction with the text, and numerous examples are provided on disk in a user-friendly format. Its applications to (...)
    Direct download  
     
    Export citation  
     
    Bookmark   3 citations  
  43.  24
    Nicholas Pippenger, Theories of computability. Cambridge University Press, Cambridge, New York, and Oakleigh, Victoria, 1997, ix + 251 pp. [REVIEW]Hans Hüttel - 1999 - Journal of Symbolic Logic 64 (2):913-914.
  44.  16
    Review: Nicholas Pippenger, Theories of Computability. [REVIEW]Hans Huttel - 1999 - Journal of Symbolic Logic 64 (2):913-914.
  45.  9
    Komamiya Yasuo. Theory of computing relay-networks. Proceedings of the First Japan National Congress for Applied Mechanics 1951, Japan National Committee for Theoretical and Applied Mechanics, Science Council of Japan, Tokyo 1952, pp. 527–532. [REVIEW]Calvin C. Elgot - 1958 - Journal of Symbolic Logic 23 (3):366-366.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  46.  11
    Review: Yasuo Komamiya, Theory of Computing Relay-Networks. [REVIEW]Calvin C. Elgot - 1958 - Journal of Symbolic Logic 23 (3):366-366.
  47. Computational theories of object recognition.Shimon Edelman - 1997 - Trends in Cognitive Sciences 1 (8):296-304.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  48.  13
    Theory of fuzzy computation.Apostolos Syropoulos - 2014 - New York: Springer.
    The book provides the first full length exploration of fuzzy computability. It describes the notion of fuzziness and present the foundation of computability theory. It then presents the various approaches to fuzzy computability. This text provides a glimpse into the different approaches in this area, which is important for researchers in order to have a clear view of the field. It contains a detailed literature review and the author includes all proofs to make the presentation accessible. Ideas for future (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  49. Seeing and summing: Implications of computational theories of vision.Austen Clark - 1984 - Cognition and Brain Theory 7 (1):1-23.
    Marr's computational theory of stereopsis is shown to imply that human vision employs a system of representation which has all the properties of a number system. Claims for an internal number system and for neural computation should be taken literally. I show how these ideas withstand various skeptical attacks, and analyze the requirements for describing neural operations as computations. Neural encoding of numerals is shown to be distinct from our ability to measure visual physiology. The constructs in Marr's (...)
     
    Export citation  
     
    Bookmark  
  50.  12
    Handbook of computational social science: theory, case studies and ethics.Uwe Engel, Anabel Quan-Haase, Sunny Xun Liu & Lars Lyberg (eds.) - 2022 - New York, NY: Routledge, Taylor & Francis Group.
    The Handbook of Computational Social Science is a comprehensive reference source for scholars across multiple disciplines. It outlines key debates in the field, showcasing novel statistical modeling and machine learning methods, and draws from specific case studies to demonstrate the opportunities and challenges in CSS approaches. The Handbook is divided into two volumes written by outstanding, internationally renowned scholars in the field. This first volume focuses on the scope of computational social science, ethics, and case studies. It covers a range (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
1 — 50 / 1000