Computability Theory

E173643
academic discipline subfield of mathematical logic subfield of theoretical computer science

Computability Theory is a branch of theoretical computer science and mathematical logic that studies which problems can be solved by algorithms and how efficiently they can be computed.

Try in SPARQL Jump to: Surface forms Statements Referenced by

All labels observed (2)

Label Occurrences
Computability Theory canonical 2
Turing computability 2

Statements (54)

Predicate Object
instanceOf academic discipline ⓘ
subfield of mathematical logic ⓘ
subfield of theoretical computer science ⓘ
basedOn discrete mathematics ⓘ
formal logic ⓘ
fieldOfStudy Church–Turing thesis ⓘ
Gödel numbering ⓘ
Kolmogorov complexity ⓘ
Post correspondence problem ⓘ
Rice's theorem ⓘ
Turing degrees ⓘ
Turing machine ⓘ
surface form: Turing machines

Turing reducibility ⓘ
algorithmic randomness ⓘ
algorithmic solvability ⓘ
analytical hierarchy ⓘ
arithmetical hierarchy ⓘ
computability ⓘ
computable analysis ⓘ
computable functions ⓘ
computable structures ⓘ
computably enumerable sets ⓘ
decidability ⓘ
decision problems ⓘ
degrees of unsolvability ⓘ
effective enumerations ⓘ
effective procedures ⓘ
halting problem ⓘ
many-one reducibility ⓘ
non-computable functions ⓘ
oracle machines ⓘ
partial recursive functions ⓘ
primitive recursive functions ⓘ
recursion theorem ⓘ
recursive functions ⓘ
recursive sets ⓘ
recursively enumerable sets ⓘ
relative computability ⓘ
reverse mathematics ⓘ
semi-decidable problems ⓘ
undecidable problems ⓘ
hasKeyFigure Alan Turing ⓘ
Alonzo Church ⓘ
Emil Post ⓘ
Kurt Gödel ⓘ
Stephen Kleene ⓘ
relatedTo complexity theory ⓘ
proof theory ⓘ
set theory ⓘ
studies classification of problems by computability ⓘ
formal models of computation ⓘ
limits of algorithmic computation ⓘ
relationships between different models of computation ⓘ
which problems can be solved by algorithms ⓘ

Referenced by (4)

Full triples — surface form annotated when it differs from this entity's canonical label.

Introduction to the Theory of Computation → hasSection → Computability Theory ⓘ
Gödel numbering → relatedConcept → Computability Theory ⓘ
this entity surface form: Turing computability
Theoretical Computer Science → hasSubfield → Computability Theory ⓘ
Ackermann function → relatedConcept → Computability Theory ⓘ
this entity surface form: Turing computability