搜索结果: 1-2 共查到“数学 undecidability”相关记录2条 . 查询时间(0.078 秒)
Three Applications to Rational Relations of the High Undecidability of the Infinite Post Correspondence Problem in a Regular omega-Language
Decision problems infinite Post Correspondence Problem analytical hierarchy high undecidability infinitary rational relations
2011/10/10
Abstract: It was noticed by Harel in [Har86] that "one can define $\Sigma_1^1$-complete versions of the well-known Post Correspondence Problem". We first give a complete proof of this result, showing ...
Uniform Definability and Undecidability in Classes of Structures
Uniform Definability Undecidability Classes of Structures
2011/1/18
We present a concept of uniform encodability of theories and develop tools related to this concept. As an application we obtain general undecidability results which are uniform for large families of s...