ALGORITHMIC RANDOMNESS AND MEASURES OF COMPLEXITY

ISCAS OpenIR

	ALGORITHMIC RANDOMNESS AND MEASURES OF COMPLEXITY
	Barmpalias, George
	2013
发表期刊	BULLETIN OF SYMBOLIC LOGIC
ISSN	1079-8986
卷号	19 期号:3 页码:318-350
摘要	We survey recent advances on the interface between computability theory and algorithmic randomness, with special attention on measures of relative complexity. We focus on (weak) reducibilities that measure (a) the initial segment complexity of reals and (b) the power of reals to compress strings, when they are used as oracles. The results are put into context and several connections are made with various central issues in modern algorithmic randomness and computability.; We survey recent advances on the interface between computability theory and algorithmic randomness, with special attention on measures of relative complexity. We focus on (weak) reducibilities that measure (a) the initial segment complexity of reals and (b) the power of reals to compress strings, when they are used as oracles. The results are put into context and several connections are made with various central issues in modern algorithmic randomness and computability.
收录类别	SCI
部门归属	Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing 100190, Peoples R China.
语种	英语
WOS记录号	WOS:000324845300002
引用统计
内容类型	期刊论文
URI标识	http://ir.iscas.ac.cn/handle/311060/16914
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Barmpalias, George. ALGORITHMIC RANDOMNESS AND MEASURES OF COMPLEXITY[J]. BULLETIN OF SYMBOLIC LOGIC,2013,19(3):318-350.
APA	Barmpalias, George.(2013).ALGORITHMIC RANDOMNESS AND MEASURES OF COMPLEXITY.BULLETIN OF SYMBOLIC LOGIC,19(3),318-350.
MLA	Barmpalias, George."ALGORITHMIC RANDOMNESS AND MEASURES OF COMPLEXITY".BULLETIN OF SYMBOLIC LOGIC 19.3(2013):318-350.