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

doi:10.1016/j.tcs.2014.12.015

CSpace

	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
	2015-09-20
发表期刊	THEORETICAL COMPUTER SCIENCE
ISSN	0304-3975
卷号	598 页码:2-14
摘要	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.
关键词	Turing machines Unsharp quantum logic Computational power
DOI	10.1016/j.tcs.2014.12.015
语种	英语
资助项目	NSFC[61472412] ; NSFC[61073023] ; National Center for Mathematics and Interdisciplinary Sciences, CAS
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000361856400002
出版者	ELSEVIER SCIENCE BV
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/20898
专题	中国科学院数学与系统科学研究院
通讯作者	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.