universality probability of a prefix-free machine
文献类型：期刊论文
| 作者 | Barmpalias George ; Dowe David L. |
| 刊名 | Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences
 |
| 出版日期 | 2012 |
| 卷号 | 370期号:1971页码:3488-3511 |
| 关键词 | Parallel processing systems |
| ISSN号 | 1364-503X |
| 中文摘要 | 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. |
| 学科主题 | Science & Technology - Other Topics |
| 收录类别 | EI ; SCI |
| 资助信息 | 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 |
| 语种 | 英语 |
| WOS记录号 | WOS:000306172800013 |
| 公开日期 | 2013-09-17 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/14926]  |
| 专题 | 软件研究所_软件所图书馆_期刊论文 |
| 推荐引用方式 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. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。