Independence results in computer science?

DOI10.1016/0022-0000(81)90013-1zbMath0474.68046OpenAlexW2050457879MaRDI QIDQ1158957

S. H. Smith

Publication date: 1981

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://docs.lib.purdue.edu/cstech/264

zbMATH Keywords

weak theories of arithmetic

Mathematics Subject Classification ID

Abstract data types; algebraic specification (68Q65) Applications of computability and recursion theory (03D80) General topics in the theory of software (68N01)

Related Items

How to prove representation-independent independence results, Learnability: Admissible, co-finite, and hypersimple languages, A note on A.E. h-complex functions, Corrigendum to ``Independence results in computer science?, Incompleteness Theorems, Large Cardinals, and Automata Over Finite Words, Incompleteness Theorems, Large Cardinals, and Automata over Finite Words, Polynomial time computations in models of ET

Cites Work

• Complexity classes of provable recursive functions
• The forcing companions of number theories
• Forcing, arithmetic, division rings
• Algebraic properties of number theories
• Arithmetical hierarchy and complexity of computation
• Undecidable theories
• Retraceable Sets
• On the Simplicity of Busy Beaver Sets
• Optimization Among Provably Equivalent Programs
• On “provable” analogs of and
• Some independence results for Peano arithmetic
• Theory of Provable Recursive Functions
• Linear orderings under one-one reducibility
• Toward a Theory of Enumerations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item