This category needs an editor. We encourage you to help if you are qualified.
Volunteer, or read more about what this involves.
Related categories
Subcategories:
423 found
Search inside:
(import / add options)   Sort by:
1 — 50 / 423
Material to categorize
  1. Michael Anderson (1968). Approximation to a Decision Procedure for the Halting Problem. Notre Dame Journal of Formal Logic 9 (4):305-312.
    Remove from this list | Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  2. Michael Anderson, Walid Gomaa, John Grant & Don Perlis, Active Logic Semantics for a Single Agent in a Static World.
    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 |
     
    My bibliography  
     
    Export citation  
  3. James S. Baldwin (2011). The Complexity of Industrial Ecosystems: Classification and Computational Modelling. In Peter Allen, Steve Maguire & Bill McKelvey (eds.), The Sage Handbook of Complexity and Management. Sage. 299.
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  4. George Barmpalias (forthcoming). Algorithmic Randomness and Measures of Complexity. 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  
     
    My bibliography  
     
    Export citation  
  5. Nuel Belnap (1977). How a Computer Should Think. In G. Ryle (ed.), Contemporary Aspects of Philosophy. Oriel Press Ltd..
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  6. Marcin Blachnik & Mirosław Kordos (2012). Computational Complexity Reduction and Interpretability Improvement of Distance-Based Decision Trees. In Emilio Corchado, Vaclav Snasel, Ajith Abraham, Michał Woźniak, Manuel Grana & Sung-Bae Cho (eds.), Hybrid Artificial Intelligent Systems. Springer. 288--297.
    Remove from this list | Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  7. J. Andrew Brook & Robert J. Stainton, Fodor's New Theory of Computation and Information.
    Remove from this list |
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  8. Sam Buss, Benedikt Löwe, Dag Normann & Ivan Soskov (2013). Computability in Europe 2011. Annals of Pure and Applied Logic 164 (5):509-510.
    Remove from this list | Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  9. Douglas Cenzer, S. Ali Dashti & Jonathan L. F. King (2008). Computable Symbolic Dynamics. 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 (3 more)  
     
    My bibliography  
     
    Export citation  
  10. Douglas Cenzer, S. Ali Dashti & Jonathan L. F. King (2008). Computable Symbolic Dynamics. Mathematical Logic Quarterly 54 (5):460-469.
    Remove from this list | Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  11. Arthur W. Chou & Ker‐I. Ko (2004). On the Complexity of Finding Paths in a Two‐Dimensional Domain I: Shortest Paths. 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 (4 more)  
     
    My bibliography  
     
    Export citation  
  12. Alonzo Church, C. Anthony Anderson & Michael Zelëny (eds.) (2001). Logic, Meaning, and Computation: Essays in Memory of Alonzo Church. 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  
     
    My bibliography  
     
    Export citation  
  13. E. A. Cichon & Andreas Weiermann (1997). Term Rewriting Theory for the Primitive Recursive Functions. 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)  
     
    My bibliography  
     
    Export citation  
  14. Gerd Doben-Henisch (2007). Reducing Negative Complexity by a Computational Semiotic System. In R. Gudwin & J. Queiroz (eds.), Semiotics and Intelligent Systems Development. Idea Group Inc.. 330.
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  15. Gordana Dodig-Crnkovic (2011). Significance of Models of Computation, From Turing Model to Natural Computation. 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 (16 more)  
     
    My bibliography  
     
    Export citation  
  16. R. G. Downey & Iraj Kalantari (1985). Effective Extensions of Linear Forms on a Recursive Vector Space Over a Recursive Field. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 31 (13):193-200.
    Remove from this list | Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  17. Patrick Doyle (2003). Computability and Computational Complexity. In L. Nadel (ed.), Encyclopedia of Cognitive Science. Nature Publishing Group.
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  18. A. P. Ershov & Donald Ervin Knuth (eds.) (1981). Algorithms in Modern Mathematics and Computer Science: Proceedings, Urgench, Uzbek Ssr, September 16-22, 1979. Springer-Verlag.
  19. Solomon Feferman (1992). Turing's\ Oracle": From Absolute to Relative Computability and Back. In Javier Echeverria, Andoni Ibarra & Thomas Mormann (eds.), The Space of Mathematics. De Gruyter. 314--348.
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  20. Fernando Ferreira, Martin Hyland, Benedikt Löwe & Elvira Mayordomo (2012). Computability in Europe 2010. Annals of Pure and Applied Logic 163 (6):621-622.
    Remove from this list | Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  21. Nir Fresco (2008). An Analysis of the Criteria for Evaluating Adequate Theories of Computation. Minds and Machines 18 (3):379-401.
  22. Dov M. Gabbay (1976). Completeness Properties of Heyting's Predicate Calculus with Respect to RE Models. Journal of Symbolic Logic 41 (1):81-94.
    Remove from this list | Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  23. Jean-Yves Girard & Dag Normann (1985). Set Recursion and Πhalf-Logic. Annals of Pure and Applied Logic 28 (3):255-286.
    Remove from this list | Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  24. Rl Goodsteest (1959). Recursive Analysis. In A. Heyting (ed.), Constructivity in Mathematics. Amsterdam, North-Holland Pub. Co.. 37.
    Remove from this list |
     
    My bibliography  
     
    Export citation  
  25. Stevan Harnad, Computers Don't Follow Instructions.
    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 |
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  26. Edith Hemaspaandra, Lane A. Hemaspaandra & Jörg Rothe (2009). Hybrid Elections Broaden Complexity‐Theoretic Resistance to Control. 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)  
     
    My bibliography  
     
    Export citation  
  27. Gerd Döben Henisch (2007). Reducing Negative Complexity by a Computational Semiotic System. In R. Gudwin & J. Queiroz (eds.), Semiotics and Intelligent Systems Development. Idea Group Inc..
    Remove from this list |
     
    My bibliography  
     
    Export citation  
  28. Gabor T. Herman (1971). Strong Computability and Variants of the Uniform Halting Problem. Mathematical Logic Quarterly 17 (1):115-131.
    Remove from this list | Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  29. Steven Homer (1980). Two Splitting Theorems for Beta-Recursion Theory. Annals of Mathematical Logic 18 (2):137-151.
    Remove from this list | Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  30. M. R. R. Hoole (1986). Plus‐1 Results for E‐Recursion. Mathematical Logic Quarterly 32 (25‐30):473-479.
    Remove from this list | Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  31. Asher M. Kach (2008). Computable Shuffle Sums of Ordinals. 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)  
     
    My bibliography  
     
    Export citation  
  32. Iraj Kalantari & Larry Welch (2008). On Turing Degrees of Points in Computable Topology. 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)  
     
    My bibliography  
     
    Export citation  
  33. Iraj Kalantari & Larry Welch (2004). Density and Baire Category in Recursive Topology. Mathematical Logic Quarterly 50 (4‐5):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)  
     
    My bibliography  
     
    Export citation  
  34. Akira Kanda (1988). Productive Sets and Constructively Nonpartial-Recursive Functions. Archive for Mathematical Logic 27 (1):49-50.
    Remove from this list | Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  35. Ján Komara (2011). On Nested Simple Recursion. 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)  
     
    My bibliography  
     
    Export citation  
  36. Stanisław Krajewski (2006). Remarks on Church's Thesis and GOdel's Theorem. In A. Olszewski, J. Wole'nski & R. Janusz (eds.), Church's Thesis After Seventy Years. Ontos Verlag. 1--269.
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  37. Harry R. Lewis & Christos H. Papadimitriou (1998). Elements of the Theory of Computation Harry R. Lewis, Christos H. Papadimitriou.
    Remove from this list |
     
    My bibliography  
     
    Export citation  
  38. J. Raymundo Marcial‐Romero & M. Andrew Moshier (2008). Sequential Real Number Computation and Recursive Relations. 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 (2 more)  
     
    My bibliography  
     
    Export citation  
  39. de Brecht Matthew (2014). Levels of Discontinuity, Limit-Computability, and Jump Operators. In Dieter Spreen, Hannes Diener & Vasco Brattka (eds.), Logic, Computation, Hierarchies. De Gruyter. 79-108.
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  40. G. L. McColm (1989). Some Restrictions on Simple Fixed Points of the Integers. Journal of Symbolic Logic 54 (4):1324-1345.
    A function is recursive (in given operations) if its values are computed explicitly and uniformly in terms of other "previously computed" values of itself and (perhaps) other "simultaneously computed" recursive functions. Here, "explicitly" includes definition by cases. We investigate those recursive functions on the structure $\mathbf{N} = \langle \omega, 0, \operatorname{succ,pred}\rangle$ that are computed in terms of themselves only, without other simultaneously computed recursive functions.
    Remove from this list | Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  41. Timothy H. McNicholl (2013). Computing Links and Accessing Arcs. Mathematical Logic Quarterly 59 (1‐2):101-107.
    Sufficient conditions are given for the computation of an arc that accesses a point on the boundary of an open subset of the plane from a point within the set. The existence of a not-computably-accessible but computable point on a computably compact arc is also demonstrated.
    Remove from this list | Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  42. Klaus Meer (1995). On the Relations Between Discrete and Continuous Complexity Theory. Mathematical Logic Quarterly 41 (2):281-286.
    Relations between discrete and continuous complexity models are considered. The present paper is devoted to combine both models. In particular we analyze the 3-Satisfiability problem. The existence of fast decision procedures for this problem over the reals is examined based on certain conditions on the discrete setting. Moreover we study the behaviour of exponential time computations over the reals depending on the real complexity of 3-Satisfiability. This will be done using tools from complexity theory over the integers.
    Remove from this list | Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  43. Jerzy Mycka (2006). Analog Computation and Church's Thesis. In A. Olszewski, J. Wole'nski & R. Janusz (eds.), Church's Thesis After Seventy Years. Ontos Verlag. 1--331.
  44. Dag Normann (2002). Representation Theorems for Transfinite Computability and Definability. Archive for Mathematical Logic 41 (8):721-741.
    Remove from this list | Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  45. Víctor A. Ocasio-González (2012). Turing Computable Embeddings and Coding Families of Sets. In S. Barry Cooper (ed.), How the World Computes. 539--548.
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  46. Isabel Oitavem (2011). A Recursion-Theoretic Approach to NP. Annals of Pure and Applied Logic 162 (8):661-666.
    An implicit characterization of the class NP is given, without using any minimization scheme. This is the first purely recursion-theoretic formulation of NP.
    Remove from this list | Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  47. Toby Ord, Hypercomputation: Computing More Than the Turing Machine.
    In this report I provide an introduction to the burgeoning field of hypercomputation – the study of machines that can compute more than Turing machines. I take an extensive survey of many of the key concepts in the field, tying together the disparate ideas and presenting them in a structure which allows comparisons of the many approaches and results. To this I add several new results and draw out some interesting consequences of hypercomputation for several different disciplines.
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  48. Geoffrey E. Ostrin & Stanley S. Wainer (2005). Elementary Arithmetic. Annals of Pure and Applied Logic 133 (1):275-292.
    There is a very simple way in which the safe/normal variable discipline of Bellantoni–Cook recursion [S. Bellantoni, S. Cook, A new recursion theoretic characterization of the polytime functions, Computational Complexity 2 97–110] can be imposed on arithmetical theories like PA: quantify over safes and induct on normals. This weakens the theory severely, so that the provably recursive functions become more realistically computable . Earlier results of D. Leivant [Intrinsic theories and computational complexity, in: D. Leivant , Logic and Computational Complexity, (...)
    Remove from this list | Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  49. James Owings, William Gasarch & Georgia Martin (2002). Max and Min Limiters. Archive for Mathematical Logic 41 (5):483-495.
    If and the function is partial recursive, it is easily seen that A is recursive. In this paper, we weaken this hypothesis in various ways (and similarly for ``min'' in place of ``max'') and investigate what effect this has on the complexity of A. We discover a sharp contrast between retraceable and co-retraceable sets, and we characterize sets which are the union of a recursive set and a co-r.e., retraceable set. Most of our proofs are noneffective. Several open questions are (...)
    Remove from this list | Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  50. J. M. P. (1965). Formal Systems and Recursive Functions. [REVIEW] Review of Metaphysics 19 (1):161-162.
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
1 — 50 / 423