Translation of Quantum Circuits into Quantum Turing Machines for Deutsch and Deutsch-Jozsa Problems

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.

Approximation and universality of fuzzy Turing machines

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.

Parallel Turing Machine, a Proposal

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.

Comparison among Classical,Probabilistic and Quantum Algorithms for Hamiltonian Cycle Problem

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.

High Energy Physics and Cosmology as Computation

The present paper is basically written as a non-apologetic strong defence of the thesis that computation is part and parcel of a physical theory and by no means a mere numerical evaluation of the prediction of a theory which comes towards the end. Various general considerations as well as specific examples are given to illustrate and support our arguments. These examples range from the practical aspect to almost esoteric considerations but at the end, everything converges towards a unity of theory and computation presented in the form of modern fractal logic and transfinite quantum field theory in a Cantorian spacetime. It is true that all our examples are taken from physics but our discussion is applicable in equal measure to a much wider aspect of life.

Dimensional Complexity and Algorithmic Efficiency

This paper uses the concept of algorithmic efficiency to present a unified theory of intelligence. Intelligence is defined informally, formally, and computationally. We introduce the concept of dimensional complexity in algorithmic efficiency and deduce that an optimally efficient algorithm has zero time complexity, zero space complexity, and an infinite dimensional complexity. This algorithm is used to generate the number line.