Publication:3320351

zbMath0536.03021MaRDI QIDQ3320351

Nigel J. Cutland

Publication date: 1983

zbMATH Keywords

computability; Gödel's incompleteness theorem; partial recursive functions; register machines; undecidable problems; Kleene's recursion theorems; universal programs

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03D35: Undecidability and degrees of sets of sentences

03-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations

03B25: Decidability of theories and sets of sentences

03D15: Complexity of computation (including implicit computational complexity)

03D20: Recursive functions and relations, subrecursive hierarchies

03D25: Recursively (computably) enumerable sets and degrees

03D10: Turing machines and related notions

03D60: Computability and recursion theory on ordinals, admissible sets, etc.

Related Items

Degree of unsolvability of the completeness problem in algebras of recursive functions, Specification of abstract dynamic-data types: A temporal logic approach