Log in

Relevant bibliographies by topics / Universal quantum turing machine / Journal articles

Journal articles on the topic 'Universal quantum turing machine'

To see the other types of publications on this topic, follow the link: Universal quantum turing machine.

Author: Grafiati

Published: 10 December 2022

Last updated: 28 January 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Universal quantum turing machine.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Iriyama, Satoshi, Takayuki Miyadera, and Masanori Ohya. "Note on a universal quantum Turing machine." Physics Letters A 372, no. 31 (July 2008): 5120–22. http://dx.doi.org/10.1016/j.physleta.2008.05.069.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

AKL, SELIM G. "THREE COUNTEREXAMPLES TO DISPEL THE MYTH OF THE UNIVERSAL COMPUTER." Parallel Processing Letters 16, no. 03 (September 2006): 381–403. http://dx.doi.org/10.1142/s012962640600271x.

Full text

Abstract:

It is shown that the concept of a Universal Computer cannot be realized. Specifically, instances of a computable function [Formula: see text] are exhibited that cannot be computed on any machine [Formula: see text] that is capable of only a finite and fixed number of operations per step. This remains true even if the machine [Formula: see text] is endowed with an infinite memory and the ability to communicate with the outside world while it is attempting to compute [Formula: see text]. It also remains true if, in addition, [Formula: see text] is given an indefinite amount of time to compute [Formula: see text]. This result applies not only to idealized models of computation, such as the Turing Machine and the like, but also to all known general-purpose computers, including existing conventional computers (both sequential and parallel), as well as contemplated unconventional ones such as biological and quantum computers. Even accelerating machines (that is, machines that increase their speed at every step) cannot be universal.

APA, Harvard, Vancouver, ISO, and other styles

3

Muller, Markus. "Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity." IEEE Transactions on Information Theory 54, no. 2 (February 2008): 763–80. http://dx.doi.org/10.1109/tit.2007.913263.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Sarkar, Aritra, Zaid Al-Ars, and Koen Bertels. "Estimating Algorithmic Information Using Quantum Computing for Genomics Applications." Applied Sciences 11, no. 6 (March 17, 2021): 2696. http://dx.doi.org/10.3390/app11062696.

Full text

Abstract:

Inferring algorithmic structure in data is essential for discovering causal generative models. In this research, we present a quantum computing framework using the circuit model, for estimating algorithmic information metrics. The canonical computation model of the Turing machine is restricted in time and space resources, to make the target metrics computable under realistic assumptions. The universal prior distribution for the automata is obtained as a quantum superposition, which is further conditioned to estimate the metrics. Specific cases are explored where the quantum implementation offers polynomial advantage, in contrast to the exhaustive enumeration needed in the corresponding classical case. The unstructured output data and the computational irreducibility of Turing machines make this algorithm impossible to approximate using heuristics. Thus, exploring the space of program-output relations is one of the most promising problems for demonstrating quantum supremacy using Grover search that cannot be dequantized. Experimental use cases for quantum acceleration are developed for self-replicating programs and algorithmic complexity of short strings. With quantum computing hardware rapidly attaining technological maturity, we discuss how this framework will have significant advantage for various genomics applications in meta-biology, phylogenetic tree analysis, protein-protein interaction mapping and synthetic biology. This is the first time experimental algorithmic information theory is implemented using quantum computation. Our implementation on the Qiskit quantum programming platform is copy-left and is publicly available on GitHub.

APA, Harvard, Vancouver, ISO, and other styles

5

Rowlands, Sydney, and Peter Rowlands. "A universal rewrite system adapted for formal language theory, classical and quantum computing." Journal of Physics: Conference Series 2197, no. 1 (March 1, 2022): 012024. http://dx.doi.org/10.1088/1742-6596/2197/1/012024.

Full text

Abstract:

Abstract The meta-pattern of the universe, first formulated by Rowlands and Diaz [2002], is a universal rewrite system (URS). This universal pattern finds a formulation in formal language theory centred around the fundamental semantic unit of the zero word or the zero string: 0 = XoX# 0. This is realized successively in the computational procedures of Turing machines, Post machines and Finite machines with two pushdown stores.

APA, Harvard, Vancouver, ISO, and other styles

6

Currin, Andrew, Konstantin Korovin, Maria Ababi, Katherine Roper, Douglas B. Kell, Philip J. Day, and Ross D. King. "Computing exponentially faster: implementing a non-deterministic universal Turing machine using DNA." Journal of The Royal Society Interface 14, no. 128 (March 2017): 20160990. http://dx.doi.org/10.1098/rsif.2016.0990.

Full text

Abstract:

The theory of computer science is based around universal Turing machines (UTMs): abstract machines able to execute all possible algorithms. Modern digital computers are physical embodiments of classical UTMs. For the most important class of problem in computer science, non-deterministic polynomial complete problems, non-deterministic UTMs (NUTMs) are theoretically exponentially faster than both classical UTMs and quantum mechanical UTMs (QUTMs). However, no attempt has previously been made to build an NUTM, and their construction has been regarded as impossible. Here, we demonstrate the first physical design of an NUTM. This design is based on Thue string rewriting systems, and thereby avoids the limitations of most previous DNA computing schemes: all the computation is local (simple edits to strings) so there is no need for communication, and there is no need to order operations. The design exploits DNA's ability to replicate to execute an exponential number of computational paths in P time. Each Thue rewriting step is embodied in a DNA edit implemented using a novel combination of polymerase chain reactions and site-directed mutagenesis. We demonstrate that the design works using both computational modelling and in vitro molecular biology experimentation: the design is thermodynamically favourable, microprogramming can be used to encode arbitrary Thue rules, all classes of Thue rule can be implemented, and non-deterministic rule implementation. In an NUTM, the resource limitation is space, which contrasts with classical UTMs and QUTMs where it is time. This fundamental difference enables an NUTM to trade space for time, which is significant for both theoretical computer science and physics. It is also of practical importance, for to quote Richard Feynman ‘there's plenty of room at the bottom’. This means that a desktop DNA NUTM could potentially utilize more processors than all the electronic computers in the world combined, and thereby outperform the world's current fastest supercomputer, while consuming a tiny fraction of its energy.

APA, Harvard, Vancouver, ISO, and other styles

7

Kurgaev, A. F., and S. N. Grygoryev. "The universal turing machine interpreter." Reports of the National Academy of Sciences of Ukraine, no. 10 (November 16, 2016): 28–34. http://dx.doi.org/10.15407/dopovidi2016.10.028.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

ROBINSON, RAPHAEL M. "MINSKY'S SMALL UNIVERSAL TURING MACHINE." International Journal of Mathematics 02, no. 05 (October 1991): 551–62. http://dx.doi.org/10.1142/s0129167x91000302.

Full text

Abstract:

Marvin L. Minsky constructed a 4-symbol 7-state universal Turing machine in 1962. It was first announced in a postscript to [2] and is also described in [3, Sec. 14.8]. This paper contains everything that is needed for an understanding of his machine, including a complete description of its operation. Minsky's machine remains one of the minimal known universal Turing machines. That is, there is no known such machine which decreases one parameter without increasing the other. However, Rogozhin [6], [7] has constructed seven universal machines with the following parameters: [Formula: see text] His 4-symbol 7-state machine is somewhat different from Minsky's, but all of his machines use a construction similar to that used by Minsky. The following corrections should be noted: First machine, for q 6 00Lq 1 read q 6 00Lq 7; second machine, for q 4 11Rq 4 read q 4 11Rq 10; last machine, for q 2 b 2 bLq 2 read [Formula: see text]. A generalized Turing machine with 4 symbols and 7 states, closely related to Minsky's, was constructed and used in [5].

APA, Harvard, Vancouver, ISO, and other styles

9

Copeland, B. Jack, and Richard Sylvan. "Beyond the universal Turing machine." Australasian Journal of Philosophy 77, no. 1 (March 1999): 46–66. http://dx.doi.org/10.1080/00048409912348801.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Crounse, K. R., and L. O. Chua. "The CNN Universal Machine is as universal as a Turing Machine." IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 43, no. 4 (April 1996): 353–55. http://dx.doi.org/10.1109/81.488819.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Siomau, Michael. "Undecidable, Unrecognizable, and Quantum Computing." Quantum Reports 2, no. 3 (July 1, 2020): 337–42. http://dx.doi.org/10.3390/quantum2030023.

Full text

Abstract:

Quantum computing allows us to solve some problems much faster than existing classical algorithms. Yet, the quantum computer has been believed to be no more powerful than the most general computing model—the Turing machine. Undecidable problems, such as the halting problem, and unrecognizable inputs, such as the real numbers, are beyond the theoretical limit of the Turing machine. I suggest a model for a quantum computer, which is less general than the Turing machine, but may solve the halting problem for any task programmable on it. Moreover, inputs unrecognizable by the Turing machine can be recognized by the model, thus breaking the theoretical limit for a computational task. A quantum computer is not just a successful design of the Turing machine as it is widely perceived now, but is a different, less general but more powerful model for computing, the practical realization of which may need different strategies than those in use now.

APA, Harvard, Vancouver, ISO, and other styles

12

Osherson, Daniel N., Michael Stob, and Scott Weinstein. "A universal inductive inference machine." Journal of Symbolic Logic 56, no. 2 (June 1991): 661–72. http://dx.doi.org/10.2307/2274708.

Full text

Abstract:

AbstractA paradigm of scientific discovery is defined within a first-order logical framework. It is shown that within this paradigm there exists a formal scientist that is Turing computable and universal in the sense that it solves every problem that any scientist can solve. It is also shown that universal scientists exist for no regular logics that extend first-order logic and satisfy the Löwenheim-Skolem condition.

APA, Harvard, Vancouver, ISO, and other styles

13

Miyadera, Takayuki, and Masanori Ohya. "On Halting Process of Quantum Turing Machine." Open Systems & Information Dynamics 12, no. 03 (September 2005): 261–64. http://dx.doi.org/10.1007/s11080-005-0923-2.

Full text

Abstract:

We prove that there is no algorithm to tell whether an arbitrarily constructed Quantum Turing Machine has same time steps for different branches of computation. We, hence, cannot avoid the notion of halting to be probabilistic in Quantum Turing Machine.

APA, Harvard, Vancouver, ISO, and other styles

14

Rowlands, Sydney, and Peter Rowlands. "The universal rewrite system coded." Journal of Physics: Conference Series 2197, no. 1 (March 1, 2022): 012023. http://dx.doi.org/10.1088/1742-6596/2197/1/012023.

Full text

Abstract:

Abstract The universal rewrite system (URS), first formulated by Rowlands and Diaz [2002], which may well be the meta-pattern driving the systems of the physical universe, has been realized, in the companion paper, in the deterministic Turing machine and other devices foundational to computational theory. Here, we show that we can extend the results to actual coding of a given finite section of the fundamentally infinite system. We also apply the principle of the URS to the universal Turing machine and to variable finite automata over an infinite alphabet, and explain its use in cryptography and the decision problem.

APA, Harvard, Vancouver, ISO, and other styles

15

Iriyama, Satoshi, and Masanori Ohya. "Language Classes Defined by Generalized Quantum Turing Machine." Open Systems & Information Dynamics 15, no. 04 (December 2008): 383–96. http://dx.doi.org/10.1142/s1230161208000262.

Full text

Abstract:

Ohya and Volovich proposed a quantum algorithm with chaotic amplification to solve the SAT problem, which went beyond the notion of the usual quantum algorithm. In this paper, we generalize quantum Turing machines by rewriting the usual quantum Turing automaton in terms of a channel transformation. Moreover, we define some computational classes of generalized quantum Turing machines and show that we can describe the Ohya-Volovich (OV) SAT algorithm with completely positive channels.

APA, Harvard, Vancouver, ISO, and other styles

16

MARGENSTERN, MAURICE, and LIOUDMILA PAVLOTSKAÏA. "ON THE OPTIMAL NUMBER OF INSTRUCTIONS FOR UNIVERSAL TURING MACHINES CONNECTED WITH A FINITE AUTOMATON." International Journal of Algebra and Computation 13, no. 02 (April 2003): 133–202. http://dx.doi.org/10.1142/s0218196703001262.

Full text

Abstract:

In this paper, a new computation system is defined by coupling a finite automaton with a deterministic Turing machine with one head and one tape that is infinite in one direction only. In a first part of the paper, it is shown that there is a Turing machine with five instructions for which it is possible to devise a finite automaton such that the resulting computation is able to simulate any Turing machine. In a second part of the paper it is shown that if the Turing machine has at most four instructions, whatever the finite automaton is, the halting of the resulting computation is always decidable.

APA, Harvard, Vancouver, ISO, and other styles

17

Chua, L. O., T. Roska, and P. L. Venetianer. "The CNN is universal as the Turing machine." IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 40, no. 4 (April 1993): 289–91. http://dx.doi.org/10.1109/81.224308.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Kidwell, P. "The universal turing machine: a half-century survey." IEEE Annals of the History of Computing 18, no. 4 (October 1996): 73. http://dx.doi.org/10.1109/mahc.1996.539927.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Turski, Wlad. "The universal turing machine: A half-century survey." Science of Computer Programming 13, no. 2-3 (May 1990): 267–70. http://dx.doi.org/10.1016/0167-6423(90)90075-o.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Cole, Charles. "The universal turing machine: A half-century survey." Information Processing & Management 32, no. 5 (September 1996): 640–41. http://dx.doi.org/10.1016/0306-4573(96)82605-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Molina, Abel, and John Watrous. "Revisiting the simulation of quantum Turing machines by quantum circuits." Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 475, no. 2226 (June 2019): 20180767. http://dx.doi.org/10.1098/rspa.2018.0767.

Full text

Abstract:

Yao's 1995 publication ‘Quantum circuit complexity’ in Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science , pp. 352–361, proved that quantum Turing machines and quantum circuits are polynomially equivalent computational models: t ≥ n steps of a quantum Turing machine running on an input of length n can be simulated by a uniformly generated family of quantum circuits with size quadratic in t , and a polynomial-time uniformly generated family of quantum circuits can be simulated by a quantum Turing machine running in polynomial time. We revisit the simulation of quantum Turing machines with uniformly generated quantum circuits, which is the more challenging of the two simulation tasks, and present a variation on the simulation method employed by Yao together with an analysis of it. This analysis reveals that the simulation of quantum Turing machines can be performed by quantum circuits having depth linear in t , rather than quadratic depth, and can be extended to variants of quantum Turing machines, such as ones having multi-dimensional tapes. Our analysis is based on an extension of method described by Arright, Nesme and Werner in 2011 in Journal of Computer and System Sciences 77 , 372–378. ( doi:10.1016/j.jcss.2010.05.004 ), that allows for the localization of causal unitary evolutions.

APA, Harvard, Vancouver, ISO, and other styles

22

Simonović, Svetomir. "On capabilities of quantum-mechanical computer models." Tehnika 77, no. 3 (2022): 337–44. http://dx.doi.org/10.5937/tehnika2203337s.

Full text

Abstract:

The work includes the analyses of the theoretical capabilities of quantum-mechanical versus classical computer models in terms of their universality, their application domain, their efficacy in solving the problems and their technological feasibility. The concepts of deterministic Turing machine, probabilistic Turing machine and quantum-mechanical Turing machine are exposed. The concept of basic information unit of quantum-mechanical computer modelqubit is introduced and the qubit is represented through the use of Bloch sphere. The use of Dirac's bra-ket notation in description of quantum-mechanical state is explained, and the notation is used to form state equation of a quantummechanical Turing machine cell. Especially, consequences of quantum parallelism, quantum interference and wave function collapse are studied in respect to capabilities of quantum-mechanical computer models. The interrelationship between classes of problems that can be efficiently solved by quantum mechanical and/or classical computer models is displayed.

APA, Harvard, Vancouver, ISO, and other styles

23

Wang, Dong-Sheng. "A local model of quantum Turing machines." Quantum Information and Computation 20, no. 3&4 (March 2020): 213–29. http://dx.doi.org/10.26421/qic20.3-4-3.

Full text

Abstract:

The model of local Turing machines is introduced, including classical and quantum ones, in the framework of matrix-product states. The locality refers to the fact that at any instance of the computation the heads of a Turing machine have definite locations. The local Turing machines are shown to be equivalent to the corresponding circuit models and standard models of Turing machines by simulation methods. This work reveals the fundamental connection between tensor-network states and information processing.

APA, Harvard, Vancouver, ISO, and other styles

24

Dolev, Shlomi, Juan A. Garay, Niv Gilboa, Vladimir Kolesnikov, and Muni Venkateswarlu Kumaramangalam. "Perennial secure multi-party computation of universal Turing machine." Theoretical Computer Science 769 (May 2019): 43–62. http://dx.doi.org/10.1016/j.tcs.2018.10.012.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Welch, Philip. "Characterisations of variant transfinite computational models: Infinite time Turing, ordinal time Turing, and Blum–Shub–Smale machines." Computability 10, no. 2 (April 16, 2021): 159–80. http://dx.doi.org/10.3233/com-200301.

Full text

Abstract:

We consider how changes in transfinite machine architecture can sometimes alter substantially their capabilities. We approach the subject by answering three open problems touching on: firstly differing halting time considerations for machines with multiple as opposed to single heads, secondly space requirements, and lastly limit rules. We: 1) use admissibility theory, Σ 2 -codes and Π 3 -reflection properties in the constructible hierarchy to classify the halting times of ITTMs with multiple independent heads; the same for Ordinal Turing Machines which have On length tapes; 2) determine which admissible lengths of tapes for transfinite time machines with long tapes allow the machine to address each of their cells – a question raised by B. Rin; 3) characterise exactly the strength and behaviour of transfinitely acting Blum–Shub–Smale machines using a Liminf rule on their registers – thereby establishing there is a universal such machine. This is in contradistinction to the machine using a ‘continuity’ rule which fails to be universal.

APA, Harvard, Vancouver, ISO, and other styles

26

Yashchyk, Oleksandr B. "МАШИНА ТЮРІНГА ЯК УНІВЕРСАЛЬНИЙ ВИКОНАВЕЦЬ АЛГОРИТМІВ ТА ЇЇ ЗАСТОСУВАННЯ В ПРОЦЕСІ ПОГЛИБЛЕНОГО ВИВЧЕННЯ АЛГОРИТМІЗАЦІЇ І ОСНОВ ПРОГРАМУВАННЯ СТАРШОКЛАСНИКАМИ." Information Technologies and Learning Tools 52, no. 2 (May 3, 2016): 10. http://dx.doi.org/10.33407/itlt.v52i2.1365.

Full text

Abstract:

The article discusses the importance of studying the notion of algorithm and its formal specification using Turing machines. In the article it was identified the basic hypothesis of the theory of algorithms for Turing as well as reviewed scientific research of modern scientists devoted to this issue and found the main principles of the Turing machine as an abstract mathematical model. The process of forming information competencies components, information culture and students` logical thinking development with the inclusion of the topic “Study and Application of Turing machine as Universal Algorithm Executor” in the course of Informatics was analyzed.

APA, Harvard, Vancouver, ISO, and other styles

27

Pradhan, Tribikram. "Enhancement of Turing Machine to Universal Turing Machine to Halt for Recursive Enumerable Language and its JFLAP Simulation." International Journal of Hybrid Information Technology 8, no. 1 (January 31, 2015): 193–202. http://dx.doi.org/10.14257/ijhit.2015.8.1.17.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Iriyama, Satoshi, and Masanori Ohya. "On Generalized Quantum Turing Machine and Its Applications." Open Systems & Information Dynamics 16, no. 02n03 (September 2009): 195–204. http://dx.doi.org/10.1142/s1230161209000141.

Full text

Abstract:

Ohya and Volovich discussed a quantum algorithm for the SAT problem with a chaos amplification process (OMV SAT algorithm) and showed that the number of steps it performed was polynomial in input size. In this paper, we define a generalized quantum Turing machine (GQTM) and related computational complexity. Then we show that there exists a GQTM which recognizes the SAT problem in polynomial time. Moreover, we discuss the problem of finding the quantum algorithm for a partial recursive function.

APA, Harvard, Vancouver, ISO, and other styles

29

Barmpalias, George, and David L. Dowe. "Universality probability of a prefix-free machine." Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 370, no. 1971 (July 28, 2012): 3488–511. http://dx.doi.org/10.1098/rsta.2011.0319.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

30

Mackenzie, Adrian. "Undecidability: The History and Time of the Universal Turing Machine." Configurations 4, no. 3 (1996): 359–79. http://dx.doi.org/10.1353/con.1996.0020.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Miszczak, J. "Models of quantum computation and quantum programming languages." Bulletin of the Polish Academy of Sciences: Technical Sciences 59, no. 3 (September 1, 2011): 305–24. http://dx.doi.org/10.2478/v10175-011-0039-5.

Full text

Abstract:

Models of quantum computation and quantum programming languagesThe goal of the presented paper is to provide an introduction to the basic computational models used in quantum information theory. We review various models of quantum Turing machine, quantum circuits and quantum random access machine (QRAM) along with their classical counterparts. We also provide an introduction to quantum programming languages, which are developed using the QRAM model. We review the syntax of several existing quantum programming languages and discuss their features and limitations.

APA, Harvard, Vancouver, ISO, and other styles

32

CALUDE, CRISTIAN S., and MICHAEL J. DINNEEN. "EXACT APPROXIMATIONS OF OMEGA NUMBERS." International Journal of Bifurcation and Chaos 17, no. 06 (June 2007): 1937–54. http://dx.doi.org/10.1142/s0218127407018130.

Full text

Abstract:

A Chaitin Omega number is the halting probability of a universal prefix-free Turing machine. Every Omega number is simultaneously computably enumerable (the limit of a computable, increasing, converging sequence of rationals), and algorithmically random (its binary expansion is an algorithmic random sequence), hence uncomputable. The value of an Omega number is highly machine-dependent. In general, no more than finitely many scattered bits of the binary expansion of an Omega number can be exactly computed; but, in some cases, it is possible to prove that no bit can be computed. In this paper, we will simplify and improve both the method and correctness of the proof proposed in an earlier paper, and we will compute the exact approximations of two Omega numbers of the same prefix-free Turing machine, which is universal when used with data in base 16 or base 2: we compute 43 exact bits for the base 16 machine and 40 exact bits for the base 2 machine.

APA, Harvard, Vancouver, ISO, and other styles

33

ROGERS, CAROLINE, and VLATKO VEDRAL. "THE SECOND QUANTIZED QUANTUM TURING MACHINE AND KOLMOGOROV COMPLEXITY." Modern Physics Letters B 22, no. 12 (May 20, 2008): 1203–10. http://dx.doi.org/10.1142/s021798490801464x.

Full text

Abstract:

The Kolmogorov complexity of a physical state is the minimal physical resources required to reproduce that state. We define a second quantized quantum Turing machine and use it to define second quantized Kolmogorov complexity. There are two advantages to our approach — our measure of the second quantized Kolmogorov complexity is closer to physical reality and unlike other quantum Kolmogorov complexities, it is continuous. We give examples where the second quantized and quantum Kolmogorov complexity differ.

APA, Harvard, Vancouver, ISO, and other styles

34

Liang, Min, and Li Yang. "On a class of quantum Turing machine halting deterministically." Science China Physics, Mechanics and Astronomy 56, no. 5 (April 19, 2013): 941–46. http://dx.doi.org/10.1007/s11433-013-5048-y.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Chiara, Maria Luisa Dalla, Roberto Giuntini, Giuseppe Sergioli, and Roberto Leporini. "Abstract quantum computing machines and quantum computational logics." International Journal of Quantum Information 14, no. 04 (June 2016): 1640019. http://dx.doi.org/10.1142/s0219749916400190.

Full text

Abstract:

Classical and quantum parallelism are deeply different, although it is sometimes claimed that quantum Turing machines are nothing but special examples of classical probabilistic machines. We introduce the concepts of deterministic state machine, classical probabilistic state machine and quantum state machine. On this basis, we discuss the question: To what extent can quantum state machines be simulated by classical probabilistic state machines? Each state machine is devoted to a single task determined by its program. Real computers, however, behave differently, being able to solve different kinds of problems. This capacity can be modeled, in the quantum case, by the mathematical notion of abstract quantum computing machine, whose different programs determine different quantum state machines. The computations of abstract quantum computing machines can be linguistically described by the formulas of a particular form of quantum logic, termed quantum computational logic.

APA, Harvard, Vancouver, ISO, and other styles

36

Martins-Ferreira, Nelson, Nuno Alves, and Geoffrey R. Mitchell. "Towards a Conceptual Notion for a Universal Printing Machine." Applied Mechanics and Materials 890 (April 2019): 61–69. http://dx.doi.org/10.4028/www.scientific.net/amm.890.61.

Full text

Abstract:

This work is concerned with 3D printing. It's main goal is to establish a conceptualsetting in which the theory of 3D printing can be developed. Following the analogy that aUniversal Turing Machine, in a veryprecise and specific way, computes everything that is computable, we propose to the development for the notion of a Universal PrintingMachine. It is an abstract notion that will simulate any 3d printer, either in existence or to be invented. In theory, it canproduce anything which can be printed. In other words, we areproposing to develop a theoretical model of a 3d printer which will serveas a reference to the current and future developments in the area.

APA, Harvard, Vancouver, ISO, and other styles

37

Dan-Dan, Lv, Lu Hong, Yu Ya-Fei, Feng Xun-Li, and Zhang Zhi-Ming. "Universal Quantum Cloning Machine in Circuit Quantum Electrodynamics." Chinese Physics Letters 27, no. 2 (February 2010): 020302. http://dx.doi.org/10.1088/0256-307x/27/2/020302.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

CALUDE, CRISTIAN S., and LUDWIG STAIGER. "On universal computably enumerable prefix codes." Mathematical Structures in Computer Science 19, no. 1 (February 2009): 45–57. http://dx.doi.org/10.1017/s0960129508007238.

Full text

Abstract:

We study computably enumerable (c.e.) prefix codes that are capable of coding all positive integers in an optimal way up to a fixed constant: these codes will be called universal. We prove various characterisations of these codes, including the following one: a c.e. prefix code is universal if and only if it contains the domain of a universal self-delimiting Turing machine. Finally, we study various properties of these codes from the points of view of computability, maximality and density.

APA, Harvard, Vancouver, ISO, and other styles

39

Iriyama, Satoshi, and Masanori Ohya. "Quantum turing machine and brain model represented by Fock space." International Journal of Quantum Information 14, no. 04 (June 2016): 1640008. http://dx.doi.org/10.1142/s0219749916400086.

Full text

Abstract:

The adaptive dynamics is known as a new mathematics to treat with a complex phenomena, for example, chaos, quantum algorithm and psychological phenomena. In this paper, we briefly review the notion of the adaptive dynamics, and explain the definition of the generalized Turing machine (GTM) and recognition process represented by the Fock space. Moreover, we show that there exists the quantum channel which is described by the GKSL master equation to achieve the Chaos Amplifier used in [M. Ohya and I. V. Volovich, J. Opt. B 5(6) (2003) 639., M. Ohya and I. V. Volovich, Rep. Math. Phys. 52(1) (2003) 25.]

APA, Harvard, Vancouver, ISO, and other styles

40

Qiu, Daowen. "Non-optimal universal quantum deleting machine." Physics Letters A 301, no. 3-4 (August 2002): 112–16. http://dx.doi.org/10.1016/s0375-9601(02)00990-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Dai, Songsong. "Fuzzy Kolmogorov Complexity Based on a Classical Description." Entropy 22, no. 1 (January 4, 2020): 66. http://dx.doi.org/10.3390/e22010066.

Full text

Abstract:

In this paper, we give a definition for fuzzy Kolmogorov complexity. In the classical setting, the Kolmogorov complexity of a single finite string is the length of the shortest program that produces this string. We define the fuzzy Kolmogorov complexity as the minimum classical description length of a finite-valued fuzzy language through a universal finite-valued fuzzy Turing machine that produces the desired fuzzy language. The classical Kolmogorov complexity is extended to the fuzzy domain retaining classical descriptions. We show that our definition is robust, that is to say, the complexity of a finite-valued fuzzy language does not depend on the underlying finite-valued fuzzy Turing machine.

APA, Harvard, Vancouver, ISO, and other styles

42

Shapiro, Ehud. "A mechanical Turing machine: blueprint for a biomolecular computer." Interface Focus 2, no. 4 (March 21, 2012): 497–503. http://dx.doi.org/10.1098/rsfs.2011.0118.

Full text

Abstract:

We describe a working mechanical device that embodies the theoretical computing machine of Alan Turing, and as such is a universal programmable computer. The device operates on three-dimensional building blocks by applying mechanical analogues of polymer elongation, cleavage and ligation, movement along a polymer, and control by molecular recognition unleashing allosteric conformational changes. Logically, the device is not more complicated than biomolecular machines of the living cell, and all its operations are part of the standard repertoire of these machines; hence, a biomolecular embodiment of the device is not infeasible. If implemented, such a biomolecular device may operate in vivo , interacting with its biochemical environment in a program-controlled manner. In particular, it may ‘compute’ synthetic biopolymers and release them into its environment in response to input from the environment, a capability that may have broad pharmaceutical and biological applications.

APA, Harvard, Vancouver, ISO, and other styles

43

Stacewicz, Paweł. "Analogicity in Computer Science. Methodological Analysis." Studies in Logic, Grammar and Rhetoric 63, no. 1 (September 1, 2020): 69–86. http://dx.doi.org/10.2478/slgr-2020-0028.

Full text

Abstract:

AbstractAnalogicity in computer science is understood in two, not mutually exclusive ways: 1) with regard to the continuity feature (of data or computations), 2) with regard to the analogousness feature (i.e. similarity between certain natural processes and computations). Continuous computations are the subject of three methodological questions considered in the paper: 1a) to what extent do their theoretical models go beyond the model of the universal Turing machine (defining digital computations), 1b) is their computational power greater than that of the universal Turing machine, 1c) under what conditions are continuous computations realizable in practice? The analogue-analogical computations lead to two other issues: 2a) in what sense and to what extent their accuracy depends on the adequacy of certain theories of empirical sciences, 2b) are there analogue-analogical computations in nature that are also continuous? The above issues are an important element of the philosophical discussion on the limitations of contemporary computer science.

APA, Harvard, Vancouver, ISO, and other styles

44

SCHMIDHUBER, JÜRGEN. "HIERARCHIES OF GENERALIZED KOLMOGOROV COMPLEXITIES AND NONENUMERABLE UNIVERSAL MEASURES COMPUTABLE IN THE LIMIT." International Journal of Foundations of Computer Science 13, no. 04 (August 2002): 587–612. http://dx.doi.org/10.1142/s0129054102001291.

Full text

Abstract:

The traditional theory of Kolmogorov complexity and algorithmic probability focuses on monotone Turing machines with one-way write-only output tape. This naturally leads to the universal enumerable Solomonoff-Levin measure. Here we introduce more general, nonenumerable but cumulatively enumerable measures (CEMs) derived from Turing machines with lexicographically nondecreasing output and random input, and even more general approximable measures and distributions computable in the limit. We obtain a natural hierarchy of generalizations of algorithmic probability and Kolmogorov complexity, suggesting that the "true" information content of some (possibly infinite) bitstring x is the size of the shortest nonhalting program that converges to x and nothing but x on a Turing machine that can edit its previous outputs. Among other things we show that there are objects computable in the limit yet more random than Chaitin's "number of wisdom" Omega, that any approximable measure of x is small for any x lacking a short description, that there is no universal approximable distribution, that there is a universal CEM, and that any nonenumerable CEM of x is small for any x lacking a short enumerating program. We briefly mention consequences for universes sampled from such priors.

APA, Harvard, Vancouver, ISO, and other styles

45

DUBACQ, JEAN-CHRISTOPHE. "HOW TO SIMULATE TURING MACHINES BY INVERTIBLE ONE-DIMENSIONAL CELLULAR AUTOMATA." International Journal of Foundations of Computer Science 06, no. 04 (December 1995): 395–402. http://dx.doi.org/10.1142/s0129054195000202.

Full text

Abstract:

The issue of testing invertibility of cellular automata has been often discussed. Constructing invertible automata is very useful for simulating invertible dynamical systems, based on local rules. The computation universality of cellular automata has long been positively resolved, and by showing that any cellular automaton could be simulated by an invertible one having a superior dimension, Toffoli proved that invertible cellular automaton of dimension d≥2 were computation-universal. Morita proved that any invertible Turing Machine could be simulated by a one-dimensional invertible cellular automaton, which proved computation-universality of invertible cellular automata. This article shows how to simulate any Turing Machine by an invertible cellular automaton with no loss of time and gives, as a corollary, an easier proof of this result.

APA, Harvard, Vancouver, ISO, and other styles

46

Whyman, Richard. "Physical Computational Complexity and First-order Logic." Fundamenta Informaticae 181, no. 2-3 (August 4, 2021): 129–61. http://dx.doi.org/10.3233/fi-2021-2054.

Full text

Abstract:

We present the concept of a theory machine, which is an atemporal computational formalism that is deployable within an arbitrary logical system. Theory machines are intended to capture computation on an arbitrary system, both physical and unphysical, including quantum computers, Blum-Shub-Smale machines, and infinite time Turing machines. We demonstrate that for finite problems, the computational power of any device characterisable by a finite first-order theory machine is equivalent to that of a Turing machine. Whereas for infinite problems, their computational power is equivalent to that of a type-2 machine. We then develop a concept of complexity for theory machines, and prove that the class of problems decidable by a finite first order theory machine with polynomial resources is equal to 𝒩𝒫 ∩ co-𝒩𝒫.

APA, Harvard, Vancouver, ISO, and other styles

47

Smillie, K. "Turing and the universal machine: the making of the modern computer [Book Review]." IEEE Annals of the History of Computing 24, no. 2 (April 2002): 95. http://dx.doi.org/10.1109/mahc.2002.1010075.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Rendell, Paul W. "The Quadratic Assignment Problem in Code Optimization for a Simple Universal Turing Machine." Complex Systems 20, no. 1 (March 15, 2011): 1–22. http://dx.doi.org/10.25088/complexsystems.20.1.1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Mereghetti, Carlo, and Beatrice Palano. "Guest Column." ACM SIGACT News 52, no. 3 (October 17, 2021): 38–59. http://dx.doi.org/10.1145/3494656.3494666.

Full text

Abstract:

Quantum computing is a prolific research area, halfway between physics and computer science [27, 29, 52]. Most likely, its origins may be dated back to 70's, when some works on quantum information began to appear (see, e.g., [34, 37]). In early 80's, R.P. Feynman suggested that the computational power of quantum mechanical processes might be beyond that of traditional computation models [25]. Almost at the same time, P. Benioff already proved that such processes are at least as powerful as Turing machines [9]. In 1985, D. Deutsch [22] proposed the notion of a quantum Turing machine as a physically realizable model for a quantum computer. From the point of view of structural complexity, E. Bernstein and U. Vazirani introduced in [20] the class BQP of problems solvable in polynomial time on quantum Turing machines, focusing attention on relations with the corresponding deterministic and probabilistic classes P and BPP, respectively. Several works in the literature explored classical issues in complexity theory from the quantum paradigm perspective (see, e.g., [7, 60, 61]).

APA, Harvard, Vancouver, ISO, and other styles

50

O'Connell, Henry, and Michael Fitzgerald. "Did Alan Turing have Asperger's syndrome?" Irish Journal of Psychological Medicine 20, no. 1 (March 2003): 28–31. http://dx.doi.org/10.1017/s0790966700007503.

Full text

Abstract:

Alan Turing was born in Paddington, London on June 23, 1912 . His family were middle-class and well-off. He was fascinated with science from an early age and showed precocious talent, especially in the areas of chemistry and mathematics. He attended Sherbourne Public School and then King's College, Cambridge where he studied mathematics. His areas of interest at Cambridge were probability theory and mathematical logic. It was at Cambridge that he first conceptualised the Universal Turing Machine, an idea that was to evolve into the modern theory of computing. He has been referred to as the father of the computer.He worked on a cipher machine at Princeton University between 1936 and 1938. He worked for the British Government during World War II with the Government Code and Cipher School at Bletchley Park. He was ultimately the key player in deciphering the German 'Enigma' code used by its submarines during the war. After the war he took up a post in Manchester University where he continued to work on ideas of artificial intelligence. He was arrested and charged for homosexual activity in 1952 and underwent a course of oestrogen therapy. He committed suicide in 1954.He was regarded as being socially aloof and eccentric by colleagues and friends. He was interested in mathematics, chemistry and logic from an early age, to the exclusion of other activities. This paper attempts to establish whether he fulfilled the criteria for Asperger's syndrome.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!