中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
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
其他版本

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。