We want in this article to show the usefulness of Quantum Turing Machine(QTM)in a high-level didactic context as well as in theoretical studies.We use QTM to show its equivalence with quantum circuit model for Deutsch...We want in this article to show the usefulness of Quantum Turing Machine(QTM)in a high-level didactic context as well as in theoretical studies.We use QTM to show its equivalence with quantum circuit model for Deutsch and Deutsch-Jozsa algorithms.Further we introduce a strategy of translation from Quantum Circuit to Quantum Turing models by these examples.Moreover we illustrate some features of Quantum Computing such as superposition from a QTM point of view and starting with few simple examples very known in Quantum Circuit form.展开更多
A scheme that can realize homomorphic Turing- equivalent privacy-preserving computations is proposed, where the encoding of the Turing machine is independent of its inputs and running time. Several extended private in...A scheme that can realize homomorphic Turing- equivalent privacy-preserving computations is proposed, where the encoding of the Turing machine is independent of its inputs and running time. Several extended private information retrieval protocols based on fully homomorphic encryption are designed, so that the reading and writing of the tape of the Turing machine, as well as the evaluation of the transition function of the Turing machine, can be performed by the permitted Boolean circuits of fully homomorphic encryption schemes. This scheme overwhelms the Turing-machine-to- circuit conversion approach, which also implements the Turing-equivalent computation. The encoding of a Turing- machine-to-circuit conversion approach is dependent on both the input data and the worst-case runtime. The proposed scheme efficiently provides the confidentiality of both program and data of the delegator in the delegator-worker model of outsourced computation against semi-honest workers.展开更多
We have witnessed the tremendous momentum of the second spring of parallel computing in recent years. But, we should remember the low points of the field more than 20 years ago and review the lesson that has led to th...We have witnessed the tremendous momentum of the second spring of parallel computing in recent years. But, we should remember the low points of the field more than 20 years ago and review the lesson that has led to the question at that point whether ＂parallel computing will soon be relegated to the trash heap reserved for promising technologies that never quite make it＂ in an article entitled ＂the death of parallel computing＂ written by the late Ken Kennedy -- a prominent leader of parallel computing in the world. Facing the new era of parallel computing, we should learn from the robust history of sequential computation in the past 60 years. We should study the foundation established by the model of Tuhring machine （1936） and its profound impact in this history. To this end, this paper examines the disappointing state of the work in parallel Turing machine models in the past 50 years of parallel computing research. Lacking a solid yet intuitive parallel Turing machine model will continue to be a serious challenge in the future parallel computing. Our paper presents an attempt to address this challenge by presenting a proposal of a parallel Turing machine model. We also discuss why we start our work in this paper from a parallel Turing machine model instead of other choices.展开更多
Fuzzy Turing machines are the formal models of fuzzy algorithms or fuzzy computations. In this paper we give several different formulations of fuzzy Turing machine, which correspond to nondeterministic fuzzy Turing ma...Fuzzy Turing machines are the formal models of fuzzy algorithms or fuzzy computations. In this paper we give several different formulations of fuzzy Turing machine, which correspond to nondeterministic fuzzy Turing machine using max-＊ composition for some t-norm＊ （or NFTM＊, for short）, nondeterministic fuzzy Turing machine （or NFTM）, deterministic fuzzy Turing machine （or DFTM）, and multi-tape versions of fuzzy Turing machines. Some distinct results compared to those of ordinary Turing machines are obtained. First, it is shown that NFTM＊, NFTM, and DFTM are not necessarily equivalent in the power of recognizing fuzzy languages if the t-norm＊ does not satisfy finite generated condition, but are equivalent in the approximation sense. That is to say, we can approximate an NFTM＊ by some NFTM with any given accuracy; the related constructions are also presented. The level characterization of fuzzy recursively enumerable languages and fuzzy recursive languages are exploited by ordinary r.e. languages and recursive languages. Second, we show that universal fuzzy Turing machine exists in the approximated sense. There is a universal fuzzy Turing machine that can simulate any NFTM＊ on it with a given accuracy.展开更多
The Hamiltonian cycle problem(HCP),which is an NP-complete problem,consists of having a graph G with n nodes and m edges and finding the path that connects each node exactly once.In this paper we compare some algorith...The Hamiltonian cycle problem(HCP),which is an NP-complete problem,consists of having a graph G with n nodes and m edges and finding the path that connects each node exactly once.In this paper we compare some algorithms to solve a Hamiltonian cycle problem,using different models of computations and especially the probabilistic and quantum ones.Starting from the classical probabilistic approach of random walks,we take a step to the quantum direction by involving an ad hoc designed Quantum Turing Machine(QTM),which can be a useful conceptual project tool for quantum algorithms.Introducing several constraints to the graphs,our analysis leads to not-exponential speedup improvements to the best-known algorithms.In particular,the results are based on bounded degree graphs(graphs with nodes having a maximum number of edges)and graphs with the right limited number of nodes and edges to allow them to outperform the other algorithms.展开更多
We consider a subclass of quantum Turing machines (QTM), named stationary rotational quantum Turing machine (SR-QTM), which halts deterministically and has deterministic tape head position. A quantum state transition ...We consider a subclass of quantum Turing machines (QTM), named stationary rotational quantum Turing machine (SR-QTM), which halts deterministically and has deterministic tape head position. A quantum state transition diagram (QSTD) is proposed to describe SR-QTM. With QSTD, we construct a SR-QTM which is universal for all near-trivial transformations. This indicates there exists a QTM which is universal for the above subclass. Finally we show that SR-QTM is computational equivalent with ordinary QTM in the bounded error setting. It can be seen that SR-QTMs have deterministic tape head position and halt deterministically, and thus the halting scheme problem will not exist for this class of QTMs.展开更多
Policy被越来越多地应用于大型分布式系统的管理 .提出了一种基于逻辑的 Policy定义语言 L PDL ,定义了 L PDL的语法、运行模型和语义 ,为基于 Policy的网络管理提供了一种形式化的框架 .L PDL具有简单的语法规则和与图灵机等价的计算能...Policy被越来越多地应用于大型分布式系统的管理 .提出了一种基于逻辑的 Policy定义语言 L PDL ,定义了 L PDL的语法、运行模型和语义 ,为基于 Policy的网络管理提供了一种形式化的框架 .L PDL具有简单的语法规则和与图灵机等价的计算能力 ,管理人员可以根据实际需要 ,灵活地将系统的解释决策功能用 L PDL语言定义成Policy或封装在系统物理实现代码中 .最后给出了基于 L PDL 的网络管理模型及其原型实现和应用 ,表明 L PDL能很好满足网络管理动态发展的需要 .展开更多
文摘We want in this article to show the usefulness of Quantum Turing Machine(QTM)in a high-level didactic context as well as in theoretical studies.We use QTM to show its equivalence with quantum circuit model for Deutsch and Deutsch-Jozsa algorithms.Further we introduce a strategy of translation from Quantum Circuit to Quantum Turing models by these examples.Moreover we illustrate some features of Quantum Computing such as superposition from a QTM point of view and starting with few simple examples very known in Quantum Circuit form.
基金The National Basic Research Program of China(973Program)(No.2013CB338003)
文摘A scheme that can realize homomorphic Turing- equivalent privacy-preserving computations is proposed, where the encoding of the Turing machine is independent of its inputs and running time. Several extended private information retrieval protocols based on fully homomorphic encryption are designed, so that the reading and writing of the tape of the Turing machine, as well as the evaluation of the transition function of the Turing machine, can be performed by the permitted Boolean circuits of fully homomorphic encryption schemes. This scheme overwhelms the Turing-machine-to- circuit conversion approach, which also implements the Turing-equivalent computation. The encoding of a Turing- machine-to-circuit conversion approach is dependent on both the input data and the worst-case runtime. The proposed scheme efficiently provides the confidentiality of both program and data of the delegator in the delegator-worker model of outsourced computation against semi-honest workers.
文摘We have witnessed the tremendous momentum of the second spring of parallel computing in recent years. But, we should remember the low points of the field more than 20 years ago and review the lesson that has led to the question at that point whether ＂parallel computing will soon be relegated to the trash heap reserved for promising technologies that never quite make it＂ in an article entitled ＂the death of parallel computing＂ written by the late Ken Kennedy -- a prominent leader of parallel computing in the world. Facing the new era of parallel computing, we should learn from the robust history of sequential computation in the past 60 years. We should study the foundation established by the model of Tuhring machine （1936） and its profound impact in this history. To this end, this paper examines the disappointing state of the work in parallel Turing machine models in the past 50 years of parallel computing research. Lacking a solid yet intuitive parallel Turing machine model will continue to be a serious challenge in the future parallel computing. Our paper presents an attempt to address this challenge by presenting a proposal of a parallel Turing machine model. We also discuss why we start our work in this paper from a parallel Turing machine model instead of other choices.
基金the National Natural Science Foundation of China (Grant No.10571112)"TRAPOYT" of China and the National 973 Foundation Research Program (Grant No.2002CB312200)
文摘Fuzzy Turing machines are the formal models of fuzzy algorithms or fuzzy computations. In this paper we give several different formulations of fuzzy Turing machine, which correspond to nondeterministic fuzzy Turing machine using max-＊ composition for some t-norm＊ （or NFTM＊, for short）, nondeterministic fuzzy Turing machine （or NFTM）, deterministic fuzzy Turing machine （or DFTM）, and multi-tape versions of fuzzy Turing machines. Some distinct results compared to those of ordinary Turing machines are obtained. First, it is shown that NFTM＊, NFTM, and DFTM are not necessarily equivalent in the power of recognizing fuzzy languages if the t-norm＊ does not satisfy finite generated condition, but are equivalent in the approximation sense. That is to say, we can approximate an NFTM＊ by some NFTM with any given accuracy; the related constructions are also presented. The level characterization of fuzzy recursively enumerable languages and fuzzy recursive languages are exploited by ordinary r.e. languages and recursive languages. Second, we show that universal fuzzy Turing machine exists in the approximated sense. There is a universal fuzzy Turing machine that can simulate any NFTM＊ on it with a given accuracy.
基金the project PNRR-HPC,Big Data and Quantum Computing–CN1 Spoke 10,CUP I53C22000690001.
文摘The Hamiltonian cycle problem(HCP),which is an NP-complete problem,consists of having a graph G with n nodes and m edges and finding the path that connects each node exactly once.In this paper we compare some algorithms to solve a Hamiltonian cycle problem,using different models of computations and especially the probabilistic and quantum ones.Starting from the classical probabilistic approach of random walks,we take a step to the quantum direction by involving an ad hoc designed Quantum Turing Machine(QTM),which can be a useful conceptual project tool for quantum algorithms.Introducing several constraints to the graphs,our analysis leads to not-exponential speedup improvements to the best-known algorithms.In particular,the results are based on bounded degree graphs(graphs with nodes having a maximum number of edges)and graphs with the right limited number of nodes and edges to allow them to outperform the other algorithms.
基金supported by the National Natural Science Foundation of China (Grant No.61173157)the Strategy Pilot Project of Chinese Academy of Sciences (Grant No.project XDA06010702)IIE’s Cryptography Research Project
文摘We consider a subclass of quantum Turing machines (QTM), named stationary rotational quantum Turing machine (SR-QTM), which halts deterministically and has deterministic tape head position. A quantum state transition diagram (QSTD) is proposed to describe SR-QTM. With QSTD, we construct a SR-QTM which is universal for all near-trivial transformations. This indicates there exists a QTM which is universal for the above subclass. Finally we show that SR-QTM is computational equivalent with ordinary QTM in the bounded error setting. It can be seen that SR-QTMs have deterministic tape head position and halt deterministically, and thus the halting scheme problem will not exist for this class of QTMs.
文摘Policy被越来越多地应用于大型分布式系统的管理 .提出了一种基于逻辑的 Policy定义语言 L PDL ,定义了 L PDL的语法、运行模型和语义 ,为基于 Policy的网络管理提供了一种形式化的框架 .L PDL具有简单的语法规则和与图灵机等价的计算能力 ,管理人员可以根据实际需要 ,灵活地将系统的解释决策功能用 L PDL语言定义成Policy或封装在系统物理实现代码中 .最后给出了基于 L PDL 的网络管理模型及其原型实现和应用 ,表明 L PDL能很好满足网络管理动态发展的需要 .
