Flashcards
Logic VIII
Cards in this deck (14)
- 1Church's ThesisThe class of effectively computable functions is the set of recursive functions
- 2A function f is effectively computatbleiff there is a finite list of (maximally specific) instructions that, in principle, make it possible to determine f for any argument.
- 3Basic Recursive FunctionsZero Function
Successor Function
Projection Functions - 4Primitive Recursive FunctionsAny function obtainable from the basic recursive functions via Composition or Primitive Recursion
- 5A partial function f is effectively computableiff there is a finite list of explicit instructions s.t f can be found for the argument in the domain of f, but otherwise the search can continue indefinitely
- 6Halting ProblemNo function to stop under certain circumstances
- 7Recursive functionAny function definable from basic recursive functions via composition, primitive recursion and minimization
- 8A set A \(\subset\) N is effectively decidableiff there's an effectively computable algorithm that, applied to n in a finite amount of time, gives the correct answer.
- 9The characteristic function of a set A \(\subset\) N, \(\chi_A\)(x)equals one if x is in A and 0 otherwise
- 10A set or relation is recursive (or recursively decidable)iff its characteristic function is recursive
- 11A set or relation is primitive recursiveiff its characteristic function is primitive recursive
- 12Definition by CasesSee notes
- 13Closure Properties for Recursive Relations TheoremSee notes
- 14Closure Properties for Semi-Recursive RelationsSee notes