+
Related Flashcards
Related Topics
Cards In This Set
| Front | Back |
|
What does it mean for a Turing Machine to halt?
|
A TM halts when it has no further instruction.
|
|
What does it mean for a function to be primitive recursive?
|
A function is primitive recursive if it can be defined using composition or the schema of primitive recursion:
f(0)=d f(n+1)=h(f(n),n) it includes the zero function, the successor function, and the projection functions |
|
What does it mean for a function to be partial recursive?
|
Can be defined like the primitive recursive functions with the u-operator.
|
|
What does it mean for a function to be recursive?
|
Recursive functions is the set of partial recursive functions that is total (ie: defined everywhere for all N.)
|
|
What does it mean for a theory to be decidable?
|
A theory is decidable if you can provide a yes or no answer for whether a sentence or formula something belongs or does not belong to it.
A set is decidable if it has a characteristic function that is recursive. |
|
What does it mean for a theory to be axiomatizable?
|
A theory T is axiomatizable if there is a decidable collection of wffs S such that T=the theory of S.
|
|
What does it mean for a theory to have non-standard models?
|
A model that is not isomorphic to the standard model.
|
|
What does it mean for a set to be recursive?
|
A set is recursive if its characteristic function is recursive (decidable)
|
|
What does it mean for a set to be recursively enumerable?
|
A recursively enumerable set is either empty or is in the range of some recursive function.
|
|
Describe or name a set that is recursive.
|
The set of all even numbers.
|
|
Name a set that is recursively enumerable.
|
The halting set.
The set of all natural numbers. The set of all even numbers. |
|
Are there sets that are recursively enumerable, but not recursive? If so, name one. If not, say why.
|
If a set is RE it is not necessarily recursive. The halting set is recursively enumberable but not recursive. It is the only exception.
The halting set says that we can enumerate all the Turing Machines but we can’t say whether they’re defined or not. |
|
Are there sets that are recursive, but not recursively enumerable? If so, name one. If not, say why.
|
No. Every recursive set is recursively enumerable. (note: can use we proved it in class as our reasoning)
|
|
What is soundness?
|
If gamma proves phi then gamma entails phi.
|
|
What is completeness?
|
For logic: If gamma entails phi then gamma proves phi. Semantic entailment implies syntactic derivability
For a theory: For any sentence A, either T proves A or T proves not A. |
