scientific article

zbMath0577.03018MaRDI QIDQ3698786

George Tourlakis

Publication date: 1984

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

ComplexityRecursivenessMachinesrecursive functionsunsolvabilityGödel's incompleteness theoremcreativityNondeterminismChurch's Thesisrecursion theoremsReducibilityproductivenessArithmetizationEffective enumerabilityRelativized computability

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations (03-01) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Turing machines and related notions (03D10) Theory of numerations, effectively presented structures (03D45) Computability and recursion theory (03Dxx)

Related Items

Weights for total division orderings on strings ⋮ Termination of rewriting ⋮ McNaughton families of languages. ⋮ Unnamed Item ⋮ Bounded linear logic: A modular approach to polynomial-time computability ⋮ A Formalization of Polytime Functions ⋮ The influence of domain interpretations on computational models ⋮ An inductive number-theoretic characterization of NP