Institutional Repository
| universality probability of a prefix-free machine | |
| Barmpalias George; Dowe David L. | |
| 2012 | |
| Source | Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences
 |
| ISSN | 1364-503X |
| Volume | 370Issue:1971Pages:3488-3511 |
| English Abstract | We study the notion of universality probability of a universal prefix-free machine, as introduced by C. S. Wallace. We show that it is random relative to the third iterate of the halting problem and determine its Turing degree and its place in the arithmetical hierarchy of complexity. Furthermore, we give a computational characterization of the real numbers that are universality probabilities of universal prefix-free machines. This journal is © 2012 The Royal Society.; We study the notion of universality probability of a universal prefix-free machine, as introduced by C. S. Wallace. We show that it is random relative to the third iterate of the halting problem and determine its Turing degree and its place in the arithmetical hierarchy of complexity. Furthermore, we give a computational characterization of the real numbers that are universality probabilities of universal prefix-free machines. This journal is © 2012 The Royal Society. |
| Indexed Type | EI ; SCI |
| Keyword | Parallel Processing Systems |
| Department | (1) State Key Laboratory of Computer Science Institute of Software Chinese Academy of Sciences PO Box 8718 Beijing 100190 China; (2) School of Computer Science and Software Engineering Monash University Clayton School of I.T. Clayton VIC 3800 Australia |
| Subject | Science & Technology - Other Topics |
| Sponsorship | National Natural Science Foundation of China 611501-10168; Chinese Academy of Sciences 2010-Y2GB03; Network Algorithms and Digital Information of the Institute of Software, Chinese Academy of Sciences |
| Language | 英语 |
| WOS ID | WOS:000306172800013 |
| Citation statistics | |
| Content Type | 期刊论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/14926 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation GB/T 7714 | Barmpalias George,Dowe David L.. universality probability of a prefix-free machine[J]. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences,2012,370(1971):3488-3511. |
| APA | Barmpalias George,&Dowe David L..(2012).universality probability of a prefix-free machine.Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences,370(1971),3488-3511. |
| MLA | Barmpalias George,et al."universality probability of a prefix-free machine".Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 370.1971(2012):3488-3511. |
| 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