User:IssaRice/Computability and logic/

Index of pages in this directory:

• IssaRice/Computability and logic/
• Bounded computation trick
• Characteristic function of a semirecursive set
• Characterization of recursively enumerable sets
• Comparison of concepts in computability theory
• Comparison of intuitive notions of computability and proof
• Computability of the uncountable
• Decrement command in loop programs
• Diagonalization lemma
• Diagonalization lemma (Yanofsky method)
• Diagonalization out of a class
• Eliezer Yudkowsky's Löb's theorem puzzle
• Entscheidungsproblem
• Expresses versus captures
• First graph principle using a semirecursive relation
• Function versus algorithm
• Gödel's completeness theorem
• Index and program
• Intended interpretation versus all interpretations
• Intuitiveness and simplicity tradeoff
• K (set of natural numbers)
• K is recursively enumerable
• Least search operator
• List of possibilities for completeness and decidability
• Logic versus theory
• Model as the representation and as that which is represented
• Models symbol
• Motivation for encoding
• Property table of theories of arithmetic
• Rogers fixed point theorem using Sipser's notation
• Semantic completeness
• Sipser's quine in Python
• Some important distinctions and equivalences in introductory mathematical logic
• Summary table of sets in computability
• S–m–n theorem
• Theory
• Uniformity