Trakhtenbrot's theorem
From Wikipedia, the free encyclopedia
In logic (usually computational) and finite model theory, Trakhtenbrot's theorem states that the problem of validity in 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).
[edit] References
- Boolos, Burgess, Jeffrey. Computability and Logic, Cambridge University Press, 2002.
- Simpson, S. "Theorems of Church and Trachtenbrot". 2001.[1]
 |
This mathematical logic-related article is a stub. You can help Wikipedia by expanding it. |
