搜索结果: 1-8 共查到“Computability”相关记录8条 . 查询时间(0.046 秒)
On the computability-theoretic complexity of trivial, strongly minimal models
computability-theoretic strongly minimal models
2015/9/28
We show the existence of a trivial, strongly minimal (and thus
uncountably categorical) theory for which the prime model is computable and
each of the other countable models computes 0
00. This res...
Game arguments in computability theory and algorithmic information theory
Game arguments computability theory algorithmic information theory Logic
2012/4/17
We provide some examples showing how game-theoretic arguments can be used in computability theory and algorithmic information theory: unique numbering theorem (Friedberg), the gap between conditional ...
Lower Bounds for Testing Computability by Small Width OBDDs
Lower Bounds for Testing Computability OBDDs
2012/12/4
We consider the problem of testing whether a function f : {0, 1}n → {0, 1} is computable by a read-once, width-2 ordered binary decision diagram (OBDD), also known as a branching program. This problem...
A subset of {1,2,3,...}^n whose non-computability leads to the existence of a Diophantine equation whose solvability is logically undecidable
Hilbert’s Tenth Problem logically undecidable Diophantine equation Logic
2011/9/22
Abstract: Let B(n)={(x_1,...,x_n) \in {1,2,3,...}^n: for each positive integers y_1,...,y_n the conjunction
(\forall i,j,k \in {1,...,n} (x_i+x_j=x_k ==> y_i+y_j=y_k)) AND
\forall i,j,k \in {1,......
A computability challenge: asymptotic bounds and isolated error-correcting codes
asymptotic bounds isolated error-correcting codes Information Theory
2011/9/16
Abstract: Consider the set of all error--correcting block codes over a fixed alphabet with $q$ letters. It determines a recursively enumerable set of points in the unit square with coordinates $(R,\de...
Brolin-Lyubich measure R of a rational endomorphism R : ˆC !ˆC with deg R 2 is the unique invariant measure of maximal entropy hR =htop(R) = log d.
Superefficiency from the Vantage Point of Computability
Asymptotic efficiency computable estimators superefficiency
2010/4/30
In 1952 Lucien Le Cam announced his celebrated result
that, for regular univariate statistical models, sets of points of superefficiency
have Lebesgue measure zero. After reviewing the turbulent
hi...
Secure Computability of Functions in the IT setting with Dishonest Majority and Applications to Long-Term Security
long-term security information-theoretic security corrupted majority
2009/6/5
It is well known that general secure function evaluation (SFE) with information-theoretical (IT) security is
infeasible in presence of a corrupted majority in the standard model. On the other hand, t...