Trakhtenbrot's theorem

Trakhtenbrot's theorem

In logic (usually computational) and finite model theory, Trakhtenbrot's theorem (due to Boris Trakhtenbrot) 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).

References

* Boolos, Burgess, Jeffrey. "Computability and Logic", Cambridge University Press, 2002.
* Simpson, S. "Theorems of Church and Trakhtenbrot". 2001. [http://www.math.psu.edu/simpson/courses/math457/trakh.pdf]


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Boris Trakhtenbrot — Boris Avraamovich Trakhtenbrot ( ru. Борис Авраамович Трахтенброт; born February 19, 1921 in Brichevo, Bessarabia)cite web|title=Russian Jewish Encyclopedia > Surnames starting with the letter T|url=http://jewishgen.org/belarus/rje t.htm] cite… …   Wikipedia

  • Gap theorem — See also Gap theorem (disambiguation) for other gap theorems in mathematics. In computational complexity theory the Gap theorem is a major theorem about the complexity of computable functions. [Lance Fortnow, Steve Homer,… …   Wikipedia

  • Cook–Levin theorem — In computational complexity theory, the Cook–Levin theorem, also known as Cook s theorem, states that the Boolean satisfiability problem is NP complete. That is, any problem in NP can be reduced in polynomial time by a deterministic Turing… …   Wikipedia

  • Трахтенброт, Борис Авраамович — Борис Авраамович Трахтенброт (также Борис Абрамович, англ. Boris (Boaz) Trachtenbrot, Trakhtenbrot, Trajtenbrot Trahtenbrot, ивр. בועז טרכטנברוט‎; род. 20 февраля 1921, Бричево Сорокского уезда, Бессарабия)  советский и израильский… …   Википедия

  • List of Russian mathematicians — Andrey Kolmogorov, a preeminent 20th century mathematician. This list of Russian mathematicians includes the famous mathematicians from the Russian Empire, the Soviet Union and the Russian Federation. This list is incomplete; you can help by …   Wikipedia

  • Трахтенброт — Трахтенброт, Борис Авраамович Борис Авраамович Трахтенброт (также Борис Абрамович, англ. Boris (Boaz) Trachtenbrot, Trakhtenbrot, Trajtenbrot Trahtenbrot, ивр …   Википедия

  • List of mathematical logic topics — Clicking on related changes shows a list of most recent edits of articles to which this page links. This page links to itself in order that recent changes to this page will also be included in related changes. This is a list of mathematical logic …   Wikipedia

  • List of mathematics articles (T) — NOTOC T T duality T group T group (mathematics) T integration T norm T norm fuzzy logics T schema T square (fractal) T symmetry T table T theory T.C. Mits T1 space Table of bases Table of Clebsch Gordan coefficients Table of divisors Table of Lie …   Wikipedia

  • Computational complexity theory — is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other. In this context, a… …   Wikipedia

  • Decidability (logic) — In logic, the term decidable refers to the decision problem, the question of the existence of an effective method for determining membership in a set of formulas. Logical systems such as propositional logic are decidable if membership in their… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”