Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Trakhtenbrot's_theorem> ?p ?o. }
Showing items 1 to 16 of
16
with 100 items per page.
- Trakhtenbrot's_theorem abstract "In Logic, finite model theory, and Computability Theory, Trakhtenbrot's theorem (due to Boris Trakhtenbrot) states that the problem of validity in First-order logic (FO) on the class of all finite models is undecidable. In fact, the class of valid sentences over finite models is not recursively enumerable (though it is co-recursively enumerable).It is considered a very important result, since it implies that the completeness theorem (that is fundamental to FO) does not hold in the finite case. Also it seems counter intuitive that being valid over all structures is 'easier' than over just the finite ones.The Theorem was first published in 1950: "The Impossibility of an Algorithm for the Decidability Problem on Finite Classes".".
- Trakhtenbrot's_theorem wikiPageExternalLink trakh.pdf.
- Trakhtenbrot's_theorem wikiPageID "4232656".
- Trakhtenbrot's_theorem wikiPageRevisionID "590751401".
- Trakhtenbrot's_theorem hasPhotoCollection Trakhtenbrot's_theorem.
- Trakhtenbrot's_theorem subject Category:Computability_theory.
- Trakhtenbrot's_theorem subject Category:Finite_model_theory.
- Trakhtenbrot's_theorem comment "In Logic, finite model theory, and Computability Theory, Trakhtenbrot's theorem (due to Boris Trakhtenbrot) states that the problem of validity in First-order logic (FO) on the class of all finite models is undecidable. In fact, the class of valid sentences over finite models is not recursively enumerable (though it is co-recursively enumerable).It is considered a very important result, since it implies that the completeness theorem (that is fundamental to FO) does not hold in the finite case.".
- Trakhtenbrot's_theorem label "Satz von Trachtenbrot".
- Trakhtenbrot's_theorem label "Trakhtenbrot's theorem".
- Trakhtenbrot's_theorem sameAs Satz_von_Trachtenbrot.
- Trakhtenbrot's_theorem sameAs m.0br9_c.
- Trakhtenbrot's_theorem sameAs Q10965882.
- Trakhtenbrot's_theorem sameAs Q10965882.
- Trakhtenbrot's_theorem wasDerivedFrom Trakhtenbrot's_theorem?oldid=590751401.
- Trakhtenbrot's_theorem isPrimaryTopicOf Trakhtenbrot's_theorem.