Definitions Flashcards
(14 cards)
What is Horn Clause?
A logical statement where at most one literal is not negated.
What is Transitive Relation?
A <= B AND B <= C -> A <= C
What is a Reflexive Relation?
A <= A
What is a Symmetric Relationship?
A <= B <-> B <= A
What is an Anti-Symmetric Relationship?
A <= B AND B <= A <-> A = B
What is an Equivalence Relation?
A relation that is Reflexive, Symmetric, and Transitive
What is a Pre-Order relationship?
A relation that is reflexive and transitive
What is a Partial-Order relationship?
A relation that is reflexive, anti-symmetric, and transitive
What is NP-Hard?
A language is NP-Hard if all problems in NP can be reduced to it.
What is NP-Complete?
A Language is NP-Complete if it is NP-Hard and in NP
What are the 7 equivalent statements of computability?
- A is recursively numerable
- A is Semi-Decidable
- A is a Type-0 Language
- A =TM(M) for a Turing Machine M
- Xa is computable
- A is the domain of a Computable Function
- A is the Co-Domain (range) of a computable function
What is the Special Halting Problem (K)?
The decision is whether the Turing Machine M will halt on a given input. This is shown to be undecidable using a representation of itself as input.
What is H0?
H0 is the Halting Problem on the empty tape. H0 is known to be undecidable.
What is Rice’s Theorem?
The statement that trying to analyse the functional behaviour of a TM is in general not possible
