Institutional Repository
| ALGORITHMIC RANDOMNESS AND MEASURES OF COMPLEXITY | |
| Barmpalias, George | |
| 2013 | |
| Source | BULLETIN OF SYMBOLIC LOGIC
 |
| ISSN | 1079-8986 |
| Volume | 19Issue:3Pages:318-350 |
| English Abstract | 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. |
| Indexed Type | SCI |
| Department | Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing 100190, Peoples R China. |
| Language | 英语 |
| WOS ID | WOS:000324845300002 |
| Citation statistics | |
| Content Type | 期刊论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/16914 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation 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. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment