universality probability of a prefix-free machine

ISCAS OpenIR

	universality probability of a prefix-free machine
	Barmpalias George; Dowe David L.
	2012
发表期刊	Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences
ISSN	1364-503X
卷号	370 期号:1971 页码:3488-3511
摘要	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.
收录类别	EI ; SCI
关键词	Parallel Processing Systems
部门归属	(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
学科领域	Science & Technology - Other Topics
资助者	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
引用统计	被引频次：7[WOS] [WOS记录] [WOS相关记录]
内容类型	期刊论文
URI标识	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.