Computing power of Turing machines in the framework of unsharp quantum logic

doi:10.1016/j.tcs.2014.12.015

CORC > 计算技术研究所 > 中国科学院计算技术研究所 > 中国科学院计算技术研究所期刊论文 > 英文

	Computing power of Turing machines in the framework of unsharp quantum logic
	Shang, Yun 1,2; Lu, Xian 3,4; Lu, Raqian 1,2,5
刊名	THEORETICAL COMPUTER SCIENCE
	2015-09-20
卷号	598 页码:2-14
关键词	Turing machines Unsharp quantum logic Computational power
ISSN号	0304-3975
DOI	10.1016/j.tcs.2014.12.015
英文摘要	We present recursion theoretical characterizations of the computational power of Turing machines in the framework of unsharp quantum logic. For unsharp quantum logic, let a lattice ordered quantum multiple valued (QMV) algebra be its truth value lattice. When lattice ordered QMV algebras satisfy a locally finite condition (that is, every non-zero element has a finite order) and its meet operation, A, is computable, we prove that Sigma(0)(1) boolean OR Pi(0)(1) subset of L-d(T) (epsilon, Sigma) (or L-W(T) (epsilon,Sigma)) subset of Pi(0)(2), where L-d(T) (epsilon, Sigma) (respectively L-W(T) (epsilon, Sigma)) denotes the class of languages accepted by these Turing machines in the depth-first method (respectively the width-first method). For sharp quantum logic, similar results are obtained for a general orthomodular truth value lattice. (C) 2014 Elsevier B.V. All rights reserved.
资助项目	NSFC[61472412] ; NSFC[61073023] ; National Center for Mathematics and Interdisciplinary Sciences, CAS
WOS研究方向	Computer Science
语种	英语
出版者	ELSEVIER SCIENCE BV
WOS记录号	WOS:000361856400002
内容类型	期刊论文
源URL	[http://119.78.100.204/handle/2XEOYT63/9305]
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Shang, Yun
作者单位	1.Chinese Acad Sci, AMSS, Inst Math, Beijing 100190, Peoples R China 2.Chinese Acad Sci, AMSS, NCMIS, Beijing 100190, Peoples R China 3.Tsinghua Univ, State Key Lab Lowdimens Quantum Phys, Beijing, Peoples R China 4.Tsinghua Univ, Dept Phys, Beijing, Peoples R China 5.Chinese Acad Sci, Inst Comp Technol, CAS Key Lab IIP, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Shang, Yun,Lu, Xian,Lu, Raqian. Computing power of Turing machines in the framework of unsharp quantum logic[J]. THEORETICAL COMPUTER SCIENCE,2015,598:2-14.
APA	Shang, Yun,Lu, Xian,&Lu, Raqian.(2015).Computing power of Turing machines in the framework of unsharp quantum logic.THEORETICAL COMPUTER SCIENCE,598,2-14.
MLA	Shang, Yun,et al."Computing power of Turing machines in the framework of unsharp quantum logic".THEORETICAL COMPUTER SCIENCE 598(2015):2-14.