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

803 found
Order:
1 — 50 / 803
Material to categorize
  1. Approximation to a Decision Procedure for the Halting Problem.Michael Anderson - 1968 - Notre Dame Journal of Formal Logic 9 (4):305-312.
  2. Active Logic Semantics for a Single Agent in a Static World.Michael Anderson, Walid Gomaa, John Grant & Don Perlis - manuscript
    Artificial Intelligence, in press. Abstract: For some time we have been developing, and have had significant practical success with, a time-sensitive, contradiction-tolerant logical reasoning engine called the active logic machine (ALMA). The current paper details a semantics for a general version of the underlying logical formalism, active logic. Central to active logic are special rules controlling the inheritance of beliefs in general (and of beliefs about the current time in particular), very tight controls on what can be derived from direct (...)
    Remove from this list  
     
    Export citation  
     
    My bibliography  
  3. Recursion Theory and Complexity: Proceedings of the Kazan '97 Workshop, Kazan, Russia, July 14-19, 1997.M. M. Arslanov & Steffen Lempp (eds.) - 1999 - W. De Gruyter.
  4. Computability and Analysis: The Legacy of Alan Turing.Jeremy Avigad & Vasco Brattka - unknown
    We discuss the legacy of Alan Turing and his impact on computability and analysis.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  5. The Complexity of Industrial Ecosystems: Classification and Computational Modelling.James S. Baldwin - 2011 - In Peter Allen, Steve Maguire & Bill McKelvey (eds.), The Sage Handbook of Complexity and Management. Sage Publications. pp. 299.
  6. Algorithmic Randomness and Measures of Complexity.George Barmpalias - forthcoming - Association for Symbolic Logic: The Bulletin of Symbolic Logic.
    We survey recent advances on the interface between computability theory and algorithmic randomness, with special attention on measures of relative complexity. We focus on (weak) reducibilities that measure (a) the initial segment complexity of reals and (b) the power of reals to compress strings, when they are used as oracles. The results are put into context and several connections are made with various central issues in modern algorithmic randomness and computability.
    Remove from this list   Direct download  
     
    Export citation  
     
    My bibliography   1 citation  
  7. How a Computer Should Think.Nuel Belnap - 1977 - In G. Ryle (ed.), Contemporary Aspects of Philosophy. Oriel Press.
    Remove from this list   Direct download  
     
    Export citation  
     
    My bibliography   44 citations  
  8. Computational Complexity Reduction and Interpretability Improvement of Distance-Based Decision Trees.Marcin Blachnik & Mirosław Kordos - 2012 - In Emilio Corchado, Vaclav Snasel, Ajith Abraham, Michał Woźniak, Manuel Grana & Sung-Bae Cho (eds.), Hybrid Artificial Intelligent Systems. Springer. pp. 288--297.
  9. Computational Complexity of Solving Equation Systems.Przemysław Broniek - unknown
    We present conclusions and open problems raising from studying solving equations over unary algebras. We suggest areas that are most promising for expanding our knowledge.
    Remove from this list   Direct download  
     
    Export citation  
     
    My bibliography  
  10. Fodor's New Theory of Computation and Information.J. Andrew Brook & Robert J. Stainton - unknown
    Remove from this list   Direct download  
    Translate
     
     
    Export citation  
     
    My bibliography  
  11. Computability in Europe 2011.Sam Buss, Benedikt Löwe, Dag Normann & Ivan Soskov - 2013 - Annals of Pure and Applied Logic 164 (5):509-510.
  12. Computable Symbolic Dynamics.Douglas Cenzer, S. Ali Dashti & Jonathan L. F. King - 2008 - Mathematical Logic Quarterly 54 (5):460-469.
    We investigate computable subshifts and the connection with effective symbolic dynamics. It is shown that a decidable Π01 class P is a subshift if and only if there exists a computable function F mapping 2ℕ to 2ℕ such that P is the set of itineraries of elements of 2ℕ. Π01 subshifts are constructed in 2ℕ and in 2ℤ which have no computable elements. We also consider the symbolic dynamics of maps on the unit interval.
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  13. On the Complexity of Finding Paths in a Two‐Dimensional Domain I: Shortest Paths.Arthur W. Chou & Ker-I. Ko - 2004 - Mathematical Logic Quarterly 50 (6):551-572.
    The computational complexity of finding a shortest path in a two-dimensional domain is studied in the Turing machine-based computational model and in the discrete complexity theory. This problem is studied with respect to two formulations of polynomial-time computable two-dimensional domains: domains with polynomialtime computable boundaries, and polynomial-time recognizable domains with polynomial-time computable distance functions. It is proved that the shortest path problem has the polynomial-space upper bound for domains of both type and type ; and it has a polynomial-space lower (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  14. Logic, Meaning, and Computation: Essays in Memory of Alonzo Church.Alonzo Church, C. Anthony Anderson & Michael Zelëny (eds.) - 2001 - Kluwer Academic Publishers.
    This volume began as a remembrance of Alonzo Church while he was still with us and is now finally complete. It contains papers by many well-known scholars, most of whom have been directly influenced by Church's own work. Often the emphasis is on foundational issues in logic, mathematics, computation, and philosophy - as was the case with Church's contributions, now universally recognized as having been of profound fundamental significance in those areas. The volume will be of interest to logicians, computer (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    My bibliography  
  15. Term Rewriting Theory for the Primitive Recursive Functions.E. A. Cichon & Andreas Weiermann - 1997 - Annals of Pure and Applied Logic 83 (3):199-223.
    The termination of rewrite systems for parameter recursion, simple nested recursion and unnested multiple recursion is shown by using monotone interpretations both on the ordinals below the first primitive recursively closed ordinal and on the natural numbers. We show that the resulting derivation lengths are primitive recursive. As a corollary we obtain transparent and illuminating proofs of the facts that the schemata of parameter recursion, simple nested recursion and unnested multiple recursion lead from primitive recursive functions to primitive recursive functions.
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  16. Introduction to Turing Categories.J. Robin B. Cockett & Pieter Jw Hofstra - 2008 - Annals of Pure and Applied Logic 156 (2):183-209.
    We give an introduction to Turing categories, which are a convenient setting for the categorical study of abstract notions of computability. The concept of a Turing category first appeared in the work of Longo and Moggi; later, Di Paolo and Heller introduced the closely related recursion categories. One of the purposes of Turing categories is that they may be used to develop categorical formulations of recursion theory, but they also include other notions of computation, such as models of combinatory logic (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  17. Variable Binding Term Operators.John Corcoran, William Hatcher & John Herring - 1972 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 18 (12):177-182.
    Chapin reviewed this 1972 ZEITSCHRIFT paper that proves the completeness theorem for the logic of variable-binding-term operators created by Corcoran and his student John Herring in the 1971 LOGIQUE ET ANALYSE paper in which the theorem was conjectured. This leveraging proof extends completeness of ordinary first-order logic to the extension with vbtos. Newton da Costa independently proved the same theorem about the same time using a Henkin-type proof. This 1972 paper builds on the 1971 “Notes on a Semantic Analysis of (...)
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  18. Physical Computation: A Mechanistic Account. [REVIEW]Joe Dewhurst - 2016 - Philosophical Psychology 29 (5):795-797.
    Physical Computation is the summation of Piccinini’s work on computation and mechanistic explanation over the past decade. It draws together material from papers published during that time, but also provides additional clarifications and restructuring that make this the definitive presentation of his mechanistic account of physical computation. This review will first give a brief summary of the account that Piccinini defends, followed by a chapter-by-chapter overview of the book, before finally discussing one aspect of the account in more critical detail.
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  19. Turing’s Algorithmic Lens: From Computability to Complexity Theory.Josep Díaz & Carme Torras - 2013 - Arbor 189 (764):a080.
  20. Nota Sobre Pluralidad Y Recursión: Ontosemántica Fregeana Para Un Analisis de Las Teorías.Amparo Diez - 1994 - Theoria 9 (2):193-202.
    In this note I discuss some topics recently analysed by C.U. Moulines in Pluralidad y recursión showing the interest of Frege’s ontosemantic theory for the study of scientific theories. I point out some misunderstandings in making use of fregean view by clarifying the basic notions of objectivity, sense, reference, concept, and object. It is not my aim here to solve the difficulties arising the possibility of identifying two theories as one. Nevertheless, I ofter some clues to achieve such an identity (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  21. Reducing Negative Complexity by a Computational Semiotic System.Gerd Doben-Henisch - 2007 - In R. Gudwin & J. Queiroz (eds.), Semiotics and Intelligent Systems Development. Idea Group. pp. 330.
  22. Information and Computation: Essays on Scientific and Philosophical Understanding of Foundations of Information and Computation.Gordana Dodig Crnkovic & Mark Burgin (eds.) - 2011 - World Scientific.
    Information is a basic structure of the world, while computation is a process of the dynamic change of information. This book provides a cutting-edge view of world's leading authorities in fields where information and computation play a central role. It sketches the contours of the future landscape for the development of our understanding of information and computation, their mutual relationship and the role in cognition, informatics, biology, artificial intelligence, and information technology. -/- This book is an utterly enjoyable and engaging (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  23. Significance of Models of Computation, From Turing Model to Natural Computation.Gordana Dodig-Crnkovic - 2011 - Minds and Machines 21 (2):301-322.
    The increased interactivity and connectivity of computational devices along with the spreading of computational tools and computational thinking across the fields, has changed our understanding of the nature of computing. In the course of this development computing models have been extended from the initial abstract symbol manipulating mechanisms of stand-alone, discrete sequential machines, to the models of natural computing in the physical world, generally concurrent asynchronous processes capable of modelling living systems, their informational structures and dynamics on both symbolic and (...)
    Remove from this list   Direct download (17 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  24. Effective Extensions of Linear Forms on a Recursive Vector Space Over a Recursive Field.R. G. Downey & Iraj Kalantari - 1985 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 31 (13):193-200.
  25. Computability and Computational Complexity.Patrick Doyle - 2003 - In L. Nadel (ed.), Encyclopedia of Cognitive Science. Nature Publishing Group.
  26. Pluralidad Y Recursión.Xabier Eizagirre & Javier Echeverria - 1993 - Theoria 8 (1):169-173.
  27. Algorithms in Modern Mathematics and Computer Science: Proceedings, Urgench, Uzbek Ssr, September 16-22, 1979.A. P. Ershov & Donald Ervin Knuth (eds.) - 1981 - Springer Verlag.
  28. "Turing's\ Oracle": From Absolute to Relative Computability and Back.Solomon Feferman - 1992 - In Javier Echeverria, Andoni Ibarra & Thomas Mormann (eds.), The Space of Mathematics: Philosophical, Epistemological, and Historical Explorations. De Gruyter. pp. 314--348.
  29. Computability in Europe 2010.Fernando Ferreira, Martin Hyland, Benedikt Löwe & Elvira Mayordomo - 2012 - Annals of Pure and Applied Logic 163 (6):621-622.
  30. 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 computer's behaviour), the (...)
    Remove from this list   Direct download (10 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  31. Completeness Properties of Heyting's Predicate Calculus with Respect to RE Models.Dov M. Gabbay - 1976 - Journal of Symbolic Logic 41 (1):81-94.
    Remove from this list   Direct download (6 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  32. Set Recursion and Πhalf-Logic.Jean-Yves Girard & Dag Normann - 1985 - Annals of Pure and Applied Logic 28 (3):255-286.
  33. Recursive Analysis.Rl Goodsteest - 1959 - In A. Heyting (ed.), Constructivity in Mathematics. Amsterdam: North-Holland Pub. Co.. pp. 37.
    Remove from this list  
     
    Export citation  
     
    My bibliography  
  34. Computers Don't Follow Instructions.Stevan Harnad - unknown
    Harnad accepts the picture of computation as formalism, so that any implementation of a program - thats any implementation - is as good as any other; in fact, in considering claims about the properties of computations, the nature of the implementing system - the interpreter - is invisible. Let me refer to this idea as 'Computationalism'. Almost all the criticism, claimed refutation by Searle's argument, and sharp contrasting of this idea with others, rests on the absoluteness of this separation between (...)
    Remove from this list   Direct download  
    Translate
     
     
    Export citation  
     
    My bibliography  
  35. Hybrid Elections Broaden Complexity‐Theoretic Resistance to Control.Edith Hemaspaandra, Lane A. Hemaspaandra & Jörg Rothe - 2009 - Mathematical Logic Quarterly 55 (4):397-424.
    Electoral control refers to attempts by an election's organizer to influence the outcome by adding/deleting/partitioning voters or candidates. The important paper of Bartholdi, Tovey, and Trick [1] that introduces control proposes computational complexity as a means of resisting control attempts: Look for election systems where the chair's task in seeking control is itself computationally infeasible.We introduce and study a method of combining two or more candidate-anonymous election schemes in such a way that the combined scheme possesses all the resistances to (...)
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  36. Reducing Negative Complexity by a Computational Semiotic System.Gerd Döben Henisch - 2007 - In R. Gudwin & J. Queiroz (eds.), Semiotics and Intelligent Systems Development. Idea Group.
  37. Strong Computability and Variants of the Uniform Halting Problem.Gabor T. Herman - 1971 - Mathematical Logic Quarterly 17 (1):115-131.
  38. Strong Computability and Variants of the Uniform Halting Problem.Gabor T. Herman - 1971 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 17 (1):115-131.
  39. Two Splitting Theorems for Beta-Recursion Theory.Steven Homer - 1980 - Annals of Mathematical Logic 18 (2):137-151.
  40. Plus‐1 Results for E‐Recursion.M. R. R. Hoole - 1986 - Mathematical Logic Quarterly 32 (25‐30):473-479.
  41. Sets Completely Creative Via Recursive Permutations.Bruce M. Horowitz - 1978 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 24 (25-30):445-452.
  42. Computable Shuffle Sums of Ordinals.Asher M. Kach - 2008 - Archive for Mathematical Logic 47 (3):211-219.
    The main result is that for sets ${S \subseteq \omega + 1}$ , the following are equivalent: The shuffle sum σ(S) is computable.The set S is a limit infimum set, i.e., there is a total computable function g(x, t) such that ${f(x) = \lim inf_t g(x, t)}$ enumerates S.The set S is a limitwise monotonic set relative to 0′, i.e., there is a total 0′-computable function ${\tilde{g}(x, t)}$ satisfying ${\tilde{g}(x, t) \leq \tilde{g}(x, t+1)}$ such that ${{\tilde{f}(x) = \lim_t \tilde{g}(x, t)}}$ (...)
    Remove from this list   Direct download (5 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  43. On Turing Degrees of Points in Computable Topology.Iraj Kalantari & Larry Welch - 2008 - Mathematical Logic Quarterly 54 (5):470-482.
    This paper continues our study of computable point-free topological spaces and the metamathematical points in them. For us, a point is the intersection of a sequence of basic open sets with compact and nested closures. We call such a sequence a sharp filter. A function fF from points to points is generated by a function F from basic open sets to basic open sets such that sharp filters map to sharp filters. We restrict our study to functions that have at (...)
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  44. Density and Baire Category in Recursive Topology.Iraj Kalantari & Larry Welch - 2004 - Mathematical Logic Quarterly 50 (45):381-391.
    We develop the concepts of recursively nowhere dense sets and sets that are recursively of first category and study closed sets of points in light of Baire's Category Theorem. Our theorems are primarily concerned with exdomains of recursive quantum functions and hence with avoidable points . An avoidance function is a recursive function which can be used to expel avoidable points from domains of recursive quantum functions. We define an avoidable set of points to be an arbitrary subset of the (...)
    Remove from this list   Direct download (5 more)  
     
    Export citation  
     
    My bibliography  
  45. Productive Sets and Constructively Nonpartial-Recursive Functions.Akira Kanda - 1988 - Archive for Mathematical Logic 27 (1):49-50.
  46. On Nested Simple Recursion.Ján Komara - 2011 - Archive for Mathematical Logic 50 (5-6):617-624.
    We give a novel proof that primitive recursive functions are closed under nested simple recursion. This new presentation is supplied with a detailed proof which can be easily formalized in small fragments of Peano Arithmetic.
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  47. Remarks on Church's Thesis and GOdel's Theorem.Stanisław Krajewski - 2006 - In A. Olszewski, J. Wole'nski & R. Janusz (eds.), Church's Thesis After Seventy Years. Ontos Verlag. pp. 1--269.
  48. Communication Complexity.Eyal Kushilevitz & Noam Nisan - 1997
  49. Elements of the Theory of Computation Harry R. Lewis, Christos H. Papadimitriou.Harry R. Lewis & Christos H. Papadimitriou - 1998
    Remove from this list  
     
    Export citation  
     
    My bibliography  
  50. Sequential Real Number Computation and Recursive Relations.J. Raymundo Marcial-Romero & M. Andrew Moshier - 2008 - Mathematical Logic Quarterly 54 (5):492-507.
    In the first author's thesis [10], a sequential language, LRT, for real number computation is investigated. That thesis includes a proof that all polynomials are programmable, but that work comes short of giving a complete characterization of the expressive power of the language even for first-order functions. The technical problem is that LRT is non-deterministic. So a natural characterization of its expressive power should be in terms of relations rather than in terms of functions. In [2], Brattka examines a formalization (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
1 — 50 / 803