blanketglossary

Computability theory

Definition

Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since expanded to include the study of generalized computability and definability. In these areas, computability theory overlaps with proof theory and effective descriptive set theory.

Related concepts

ACM Computing Classification System Abstract logic Ackermann function Ackermann set theory Admissible numbering Alan Mathison Turing Alan Turing Albert Muchnik Aleph number Alfred Tarski Algebraic logic Algorithm Algorithm design Algorithmic efficiency Algorithmic randomness Algorithmically random set Alonzo Church Alpha recursion theory Alphabet (formal languages)American Journal of Mathematics Analog computation Analog computer Analog electronics Analog signal processing Analysis of algorithms Analytical hierarchy Andrey Markov Jr.Anil Nerode Annals of Mathematics Application security Argument Arithmetic reducibility Arithmetical hierarchy Arithmetical reducibility Arity Artificial intelligence Artificial neural network Arun Sharma (computer scientist)Association for Symbolic Logic Atomic formula Atomic model (mathematical logic)Atomic sentence Augmented reality Automata theory Automated planning and scheduling Automated theorem proving Axiom Axiom of choice Axiom schema Axiomatic system Axiomatization of Boolean algebras Banach–Tarski paradox Bell System Technical Journal Bijection Binary operation Blum–Shub–Smale machine Boolean algebra Boolean algebras canonically defined Boolean function Bradford Book Bulletin of Symbolic Logic Bulletin of the American Mathematical Society Busy beaver Cambridge University Press Cantor's diagonal argument Cantor's paradox Cantor's theorem Cantor space Cardinality Carl Groos Jockusch Jr.Cartesian product Categorical theory Category (mathematics)Category of sets Category theory Chapman & Hall Church encoding Church–Turing thesis Class (set theory)Classical logic Codomain Communication protocol Compactness theorem Compiler construction Complement (set theory)Complete theory Computability Computability in Europe Computability logic Computable function Computable isomorphism Computable set Computably enumerable Computably enumerable set Computational biology Computational chemistry Computational complexity Computational complexity theory Computational engineering Computational geometry Computational intelligence Computational mathematics Computational physics Computational problem Computational social science Computer accessibility Computer animation Computer architecture Computer data storage Computer graphics Computer hardware Computer network Computer science Computer security Computer vision Computing Computing platform Concrete category Concurrency (computer science)Concurrent computing Conservative extension Consistency Constructible universe Construction of the real numbers Constructive set theory Continuum hypothesis Control flow Control theory Countable set Cris Moore Cross-validation (statistics)Cryptography Cyber-physical system Cyberwarfare Daniel Nathan Osherson Data mining Database Decidability (logic)Decision problem Decision support system Deductive system Definable set Degree of constructibility Dependability Diagram (mathematical logic)Differential equation Digital art Digital library Digital marketing Diophantine equation Discrete mathematics Distributed artificial intelligence Distributed computing Document management system Domain-specific language Domain of a function Dover Publications, Inc.Dynamical system E-commerce E. Mark Gold Educational technology Effective descriptive set theory Effective method Electronic design automation Electronic publishing Electronic voting Element (mathematics)Elementary diagram Elementary equivalence Elementary function arithmetic Elsevier Embedded system Emil Leon Post Emil Post Empty set Enterprise information system Enterprise software Entscheidungsproblem Enumeration Equiconsistency Equivalence relation Erlangen program Euclid's Elements Euclidean geometry Existential quantification Expression (mathematics)Extension by definitions Extension by new constant and function names Extensionality Fault tolerance Finitary relation Finite-valued logic Finite model theory Finite set First-order logic Fixed-point logic Forcing (mathematics)Form factor (design)Formal grammar Formal language Formal method Formal methods Formal proof Formal semantics (logic)Formal system Formation rule Foundations of geometry Foundations of mathematics Free logic Free variables and bound variables Friedberg numbering Function (mathematics)Functional predicate Fuzzy set General set theory Geographic information system Gerald Enoch Sacks Goodstein's theorem Graphics processing unit Green computing Grothendieck universe Ground expression Ground formula Group (mathematics)Gödel's completeness theorem Gödel's incompleteness theorem Gödel's incompleteness theorems Gödel numbering Halting problem Hardware acceleration Hardware security Hartley Rogers Jr.Harvey Friedman (mathematician)Health informatics Henry Gordon Rice Herbert Bruce Enderton Hereditary set Higher-order logic Hilbert's axioms Hilbert's tenth problem Hilbert system History of logic History of mathematical logic Human-centered computing Human–computer interaction Hyperarithmetical reducibility Hypersimple set Identity element Illinois Journal of Mathematics Image (mathematics)Image compression Inaccessible cardinal Incompleteness theorems Independence (mathematical logic)Industrial process control Inference Infinite-valued logic Infinite set Information and Control Information retrieval Information security Information system Information theory Inhabited set Injective function Integrated circuit Integrated development environment Interaction design Interpretation (logic)Interpretation (model theory)Interpretation function Interpreter (computing)Intersection (set theory)Intrusion detection system Isomorphism Jeffrey B. Remmel John R. Myhill Sr.Jon Barwise Journal of Symbolic Logic Julia Robinson Knowledge representation and reasoning Knuth's up-arrow notation Kolmogorov complexity Kripke's theory of truth Kripke–Platek set theory Kurt Gödel Lambda calculus Lance Jeremy Fortnow Large cardinal Lattice (order theory)Lemma (mathematics)Leo Anthony Harrington Library (computing)Limiting recursive Lindström's theorem List of Hilbert systems List of axioms List of computer size categories List of first-order theories List of formal systems List of mathematical theories List of set identities and relations List of statements independent of ZFC List of undecidable problems Logic Logic in computer science Logical biconditional Logical conjunction Logical connective Logical consequence Logical constant Logical disjunction Logical equality Logical equivalence Logical truth Logicism Löwenheim–Skolem theorem MIT Press Machine learning Many-one reduction Many-valued logic Map (mathematics)Martin Davis (mathematician)Material conditional MathSciNet Mathematical analysis Mathematical logic Mathematical object Mathematical optimization Mathematical software Mathematics Matiyasevich's theorem Maximal set Metalanguage Middleware Minimal axioms for Boolean algebra Mobile computing Model complete theory Model of computation Model theory Modeling language Monadic predicate calculus Monadic second-order logic Morse–Kelley set theory Multi-task learning Multimedia database Multiprocessing Multithreading (computer architecture)NP (complexity)Naive set theory Natural deduction Natural language processing Natural number Negation Network architecture Network performance Network scheduler Network security Network service Networking hardware New Foundations Nigel J. Cutland Non-Euclidean geometry Non-logical symbol Non-standard model Non-standard model of arithmetic North-Holland Numbering (computability theory)Numerical analysis Open formula Open source Operating system Operation (mathematics)Operations research Oracle Turing machine Ordinal analysis Ordinal number Outline of computer science Oxford University Press P (complexity)P versus NP problem Paradoxes of set theory Parallel computing Partial order Partition of a set Peano arithmetic Peano axioms Peripheral Philosophy of artificial intelligence Philosophy of mathematics Photograph manipulation Piergiorgio Odifreddi Post's problem Post's theorem Power set Powerset Predicate (mathematical logic)Predicate logic Predicate variable Prime model Primitive recursion Primitive recursive arithmetic Primitive recursive function Principia Mathematica Printed circuit board Probability Proceedings of the London Mathematical Society Proceedings of the National Academy of Sciences USA Processor (computing)Programming language Programming language theory Programming paradigm Programming team Programming tool Proof of impossibility Proof theory Proposition Propositional calculus Propositional formula Propositional variable Pyotr Novikov Quantifier (logic)Quantifier rank Quantum computing Randomized algorithm Real-time computing Recursion Recursion (computer science)Recursive set Recursively enumerable Recursively enumerable set Reduction (computability theory)Reduction (recursion theory)Reinforcement learning Relation (mathematics)Rendering (computer graphics)Requirements analysis Reverse mathematics Rice's theorem Richard Arnold Shore Richard M. Friedberg Robert I. Soare Robert Irving Soare Robinson arithmetic Rule of inference Russell's paradox Rózsa Péter S. Barry Cooper Samuel R. Buss Satisfiability Saturated model Schröder–Bernstein theorem Scott Aaronson Second-order arithmetic Second-order logic Security hacker Security service (telecommunication)Self-verifying theories Semantic theory of truth Semantics (computer science)Semantics of logic Semirecursive Sentence (mathematical logic)Sequent calculus Set (mathematics)Set theory Signature (logic)Simple set Singleton (mathematics)Skolem arithmetic Social computing Social software Software configuration management Software construction Software deployment Software design Software development Software development process Software engineering Software framework Software maintenance Software quality Software repository Solid modeling Solomon Feferman Soundness Spectrum of a sentence Spectrum of a theory Springer-Verlag Square of opposition Statistics Stephen Cole Kleene Stephen Kleene Steve Simpson (mathematician)Stochastic computing Strength (mathematical logic)String (formal languages)Structure (mathematical logic)Substitution (logic)Substructure (mathematics)Supertask Supervised learning Surjective function Syllogism Symbol (formal)Syntax (logic)System on a chip T-schema Tarski's axiomatization of the reals Tarski's axioms Tarski's indefinability theorem Tarski's theory of truth Tarski's undefinability theorem Tarski–Grothendieck set theory Tautology (logic)Term (logic)Term logic The Journal of Symbolic Logic Theodore Allen Slaman Theorem Theoretical Computer Science (journal)Theoretical computer science Theories of truth Theory (mathematical logic)Theory of computation Three-valued logic Tibor Radó Timeline of mathematical logic Total function Transactions of the American Mathematical Society Transcomputational problem Transfer principle Transitive set True arithmetic Truth predicate Truth table Truth table reduction Truth value Turing degree Turing jump Turing machine Turing reducible Turing reduction Type (model theory)Type theory Ubiquitous computing Ultrafilter (set theory)Ultraproduct Uncountable set Undecidable problem Uninterpreted function Union (set theory)Uniqueness quantification Universal Turing machine Universal quantification Universal set Universe (mathematics)University of Chicago Unsupervised learning Urelement Validity (logic)Variable (mathematics)Venn diagram Very-large-scale integration Video game Virtual machine Virtual reality Visualization (graphics)Von Neumann universe Von Neumann–Bernays–Gödel set theory Well-formed formula Well-ordering William Boone (mathematician)William Hugh Woodin Wireless sensor network Word problem for groups Word problem for semigroups Word processor World Wide Web Yuri Matiyasevich Yuri Vladimirovich Matiyasevich Yury Leonidovich Ershov Zermelo–Fraenkel set theory Μ-recursive function Μ operator

150 concepts already in your glossary