Log in

Relevant bibliographies by topics / Turing machines / Journal articles

Journal articles on the topic 'Turing machines'

To see the other types of publications on this topic, follow the link: Turing machines.

Author: Grafiati

Published: 4 June 2021

Last updated: 29 July 2024

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 'Turing machines.'

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

Beggs, Edwin, José Félix Costa, Bruno Loff, and John V. Tucker. "Computational complexity with experiments as oracles." Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 464, no. 2098 (June 24, 2008): 2777–801. http://dx.doi.org/10.1098/rspa.2008.0085.

Full text

Abstract:

We discuss combining physical experiments with machine computations and introduce a form of analogue–digital (AD) Turing machine. We examine in detail a case study where an experimental procedure based on Newtonian kinematics is combined with a class of Turing machines. Three forms of AD machine are studied, in which physical parameters can be set exactly and approximately. Using non-uniform complexity theory, and some probability, we prove theorems that show that these machines can compute more than classical Turing machines.

APA, Harvard, Vancouver, ISO, and other styles

2

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

3

Baeten, Jos C. M., Bas Luttik, and Paul van Tilburg. "Reactive Turing machines." Information and Computation 231 (October 2013): 143–66. http://dx.doi.org/10.1016/j.ic.2013.08.010.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Lisovik, L. P. "Structured Turing Machines." Cybernetics and Systems Analysis 40, no. 2 (March 2004): 162–68. http://dx.doi.org/10.1023/b:casa.0000034441.56723.a4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Copeland, B. Jack. "Super Turing-machines." Complexity 4, no. 1 (September 1998): 30–32. http://dx.doi.org/10.1002/(sici)1099-0526(199809/10)4:1<30::aid-cplx9>3.0.co;2-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Burgin, Mark, and Eugene Eberbach. "Universality for Turing Machines, Inductive Turing Machines and Evolutionary Algorithms." Fundamenta Informaticae 91, no. 1 (2009): 53–77. http://dx.doi.org/10.3233/fi-2009-0033.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

CALUDE, CRISTIAN S., and LUDWIG STAIGER. "A note on accelerated Turing machines." Mathematical Structures in Computer Science 20, no. 6 (November 8, 2010): 1011–17. http://dx.doi.org/10.1017/s0960129510000344.

Full text

Abstract:

In this paper we prove that any Turing machine that uses only a finite computational space for every input cannot solve an uncomputable problem even when it runs in accelerated mode. We also propose two ways to define the language accepted by an accelerated Turing machine. Accordingly, the classes of languages accepted by accelerated Turing machines are the closure under Boolean operations of the sets Σ1 and Σ2.

APA, Harvard, Vancouver, ISO, and other styles

8

Cabessa, Jérémie, and Hava T. Siegelmann. "The Computational Power of Interactive Recurrent Neural Networks." Neural Computation 24, no. 4 (April 2012): 996–1019. http://dx.doi.org/10.1162/neco_a_00263.

Full text

Abstract:

In classical computation, rational- and real-weighted recurrent neural networks were shown to be respectively equivalent to and strictly more powerful than the standard Turing machine model. Here, we study the computational power of recurrent neural networks in a more biologically oriented computational framework, capturing the aspects of sequential interactivity and persistence of memory. In this context, we prove that so-called interactive rational- and real-weighted neural networks show the same computational powers as interactive Turing machines and interactive Turing machines with advice, respectively. A mathematical characterization of each of these computational powers is also provided. It follows from these results that interactive real-weighted neural networks can perform uncountably many more translations of information than interactive Turing machines, making them capable of super-Turing capabilities.

APA, Harvard, Vancouver, ISO, and other styles

9

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

10

Mélès, Baptiste. "Les langages de Turing." Intellectica. Revue de l'Association pour la Recherche Cognitive 72, no. 1 (2020): 81–110. http://dx.doi.org/10.3406/intel.2020.1947.

Full text

Abstract:

Si les machines de Turing sont réputées inutilisables, c'est parce qu''on prête souvent davantage attention à la rudimentaire description initiale proposée par leur inventeur qu'à son souci constant d'adapter la syntaxe de leur description aux objectifs poursuivis. Nous décrirons chacun des langages successivement adoptés par Turing en en explicitant la grammaire, en justifiant chaque innovation syntaxique et en confrontant aux déclarations d'intention de Turing sa pratique effective. L'exposition de ces langages sera également éclairée, à titre pédagogique, par la théorie moderne des langages de programmation. Nous verrons ainsi que Turing a proposé trois familles de langages pour décrire le fonctionnement de ses machines : d'abord tout une pyramide de langages explicatifs («tables complètes» et «tables abrégées»), voués à rendre intelligible au lecteur humain le fonctionnement des machines ; puis un langage calculatoire, seul véritable «langage de programmation», permettant notamment l'exécution d''une description de machine par une autre machine ; enfin un langage démonstratif, réservé au mathématicien pour la mise au jour de propriétés des nombres calculables.

APA, Harvard, Vancouver, ISO, and other styles

11

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

12

Bergstra, J. A., and C. A. Middelburg. "Simulating Turing machines on Maurer machines." Journal of Applied Logic 6, no. 1 (March 2008): 1–23. http://dx.doi.org/10.1016/j.jal.2007.04.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

SHARMA, AJEET K., and DEBASHISH CHOWDHURY. "TEMPLATE-DIRECTED BIOPOLYMERIZATION: TAPE-COPYING TURING MACHINES." Biophysical Reviews and Letters 07, no. 03n04 (December 2012): 135–75. http://dx.doi.org/10.1142/s1793048012300083.

Full text

Abstract:

DNA, RNA and proteins are among the most important macromolecules in a living cell. These molecules are polymerized by molecular machines. These natural nano-machines polymerize such macromolecules, adding one monomer at a time, using another linear polymer as the corresponding template. The machine utilizes input chemical energy to move along the template which also serves as a track for the movements of the machine. In the Alan Turing year 2012, it is worth pointing out that these machines are "tape-copying Turing machines". We review the operational mechanisms of the polymerizer machines and their collective behavior from the perspective of statistical physics, emphasizing their common features in spite of the crucial differences in their biological functions. We also draw the attention of the physics community to another class of modular machines that carry out a different type of template-directed polymerization. We hope this review will inspire new kinetic models for these modular machines.

APA, Harvard, Vancouver, ISO, and other styles

14

De Brito, Vasco Boavida, José Félix Costa, and Diogo Poças. "The Power of Machines That Control Experiments." International Journal of Foundations of Computer Science 33, no. 02 (February 2022): 91–118. http://dx.doi.org/10.1142/s0129054122500010.

Full text

Abstract:

We consider the experimenter (e.g. the experimental physicist) as a Turing machine — the digital component — and the experiment of measurement — the analog component — as an oracle to the Turing machine. The algorithm running in the machine abstracts the experimental method of measurement (encoding the recursive structure of experimental actions) chosen by the experimenter. In this paper we prove that the central analogue-digital complexity classes [Formula: see text], [Formula: see text] and [Formula: see text] can be characterized in terms of protocols to perform measurements controlled by standard Turing machines.

APA, Harvard, Vancouver, ISO, and other styles

15

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

16

Aleksander, Igor. "From Turing to Conscious Machines." Philosophies 7, no. 3 (May 29, 2022): 57. http://dx.doi.org/10.3390/philosophies7030057.

Full text

Abstract:

In the period between Turing’s 1950 “Computing Machinery and Intelligence” and the current considerable public exposure to the term “artificial intelligence (AI)”, Turing’s question “Can a machine think?” has become a topic of daily debate in the media, the home, and, indeed, the pub. However, “Can a machine think?” is sliding towards a more controversial issue: “Can a machine be conscious?” Of course, the two issues are linked. It is held here that consciousness is a pre-requisite to thought. In Turing’s imitation game, a conscious human player is replaced by a machine, which, in the first place, is assumed not to be conscious, and which may fool an interlocutor, as consciousness cannot be perceived from an individual’s speech or action. Here, the developing paradigm of machine consciousness is examined and combined with an extant analysis of living consciousness to argue that a conscious machine is feasible, and capable of thinking. The route to this utilizes learning in a “neural state machine”, which brings into play Turing’s view of neural “unorganized” machines. The conclusion is that a machine of the “unorganized” kind could have an artificial form of consciousness that resembles the natural form and that throws some light on its nature.

APA, Harvard, Vancouver, ISO, and other styles

17

Warwick, Kevin, and Huma Shah. "The Turing Test." International Journal of Synthetic Emotions 5, no. 1 (January 2014): 31–45. http://dx.doi.org/10.4018/ijse.2014010105.

Full text

Abstract:

This paper appraises some of the prevailing ideas surrounding one of Turing's brilliant ideas, his imitation game experiment, and considers judge performance in assessing machine thinking in the light of practical Turing tests. The emphasis is not on philosophical aspects as to whether machines can think or not but rather on the nature of the discourses performed in the game. Here the authors are more concerned with the nature of human communication and attempts by machines to behave in the same way. In particular the authors look at some of the strategies that Turing suggested would not be good and he has been proved correct. Also authors look at the side track argument, that some have misguidedly introduced, regarding identifying the difference between females and males through such discourse.

APA, Harvard, Vancouver, ISO, and other styles

18

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

19

Hamkins, Joel David, and Andy Lewis. "Infinite time Turing machines." Journal of Symbolic Logic 65, no. 2 (June 2000): 567–604. http://dx.doi.org/10.2307/2586556.

Full text

Abstract:

AbstractWe extend in a natural way the operation of Turing machines to infinite ordinal time, and investigate the resulting supertask theory of computability and decidability on the reals. Every set. for example, is decidable by such machines, and the semi-decidable sets form a portion of the sets. Our oracle concept leads to a notion of relative computability for sets of reals and a rich degree structure, stratified by two natural jump operators.

APA, Harvard, Vancouver, ISO, and other styles

20

Zhang, Lan, Katsushi Inoue, Akira Ito, and Yue Wang. "Probabilistic rebound Turing machines." Theoretical Computer Science 270, no. 1-2 (January 2002): 739–60. http://dx.doi.org/10.1016/s0304-3975(01)00098-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Rogozhin, Yurii. "Small universal Turing machines." Theoretical Computer Science 168, no. 2 (November 1996): 215–40. http://dx.doi.org/10.1016/s0304-3975(96)00077-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Kudlek, Manfred. "Small deterministic Turing machines." Theoretical Computer Science 168, no. 2 (November 1996): 241–55. http://dx.doi.org/10.1016/s0304-3975(96)00078-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Rhodes, John, and Pedro V. Silva. "Turing machines and bimachines." Theoretical Computer Science 400, no. 1-3 (June 2008): 182–224. http://dx.doi.org/10.1016/j.tcs.2008.03.019.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Wegner, Peter, and Dina Goldin. "Computation beyond turing machines." Communications of the ACM 46, no. 4 (April 2003): 100–102. http://dx.doi.org/10.1145/641205.641235.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Keats, Jonathon. "Are we Turing machines?" New Scientist 231, no. 3080 (July 2016): 42. http://dx.doi.org/10.1016/s0262-4079(16)31198-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

OGIHARA, MITSUNORI. "ON SERIALIZABLE LANGUAGES." International Journal of Foundations of Computer Science 05, no. 03n04 (December 1994): 303–18. http://dx.doi.org/10.1142/s0129054194000177.

Full text

Abstract:

Cai and Furst introduced the notion of bottleneck Turing machines. Based on Barrington’s innovating technique, which is used to showed that polynomial-size branching programs have exactly the same power as NC1, Cai and Furst showed that the languages recognized by width-5 bottleneck Turing machines are exactly the same as those in PSPACE. In this paper, computational power of bottleneck Turing machines with widths fewer than 5 is investigated. It is shown that width-2 bottleneck Turing machines capture ⊕P// OptP , the class of sets recognized by ⊕P-machines with pre-computation in OptP. For languages recognized by bottleneck Turing machines with width-3 and width-4, some lower-bounds and upper-bounds are shown.

APA, Harvard, Vancouver, ISO, and other styles

27

ITO, AKIRA, KATSUSHI INOUE, ITSUO TAKANAMI, and YUE WANG. "THE EFFECT OF INKDOTS FOR TWO-DIMENSIONAL AUTOMATA." International Journal of Pattern Recognition and Artificial Intelligence 09, no. 05 (October 1995): 777–96. http://dx.doi.org/10.1142/s0218001495000328.

Full text

Abstract:

Recently, related to the open problem of whether deterministic and nondeterministic space (especially lower-level) complexity classes are separated, the inkdot Turing machine was introduced. An inkdot machine is a conventional Turing machine capable of dropping an inkdot on a given input tape for a landmark, but not to pick it up nor further erase it. In this paper, we introduce a finite state version of the inkdot machine as a weak recognizer of the properties of digital pictures, rather than a Turing machine supplied with a one-dimensional working tape. We first investigate the sufficient spaces of three-way Turing machines to simulate two-dimensional inkdot finite automaton, as preliminary results. Next, we investigate the basic properties of two-dimensional inkdot automaton, i.e. the hierarchy based on the number of inkdots and the relationship of two-dimensional inkdot automata to other conventional two-dimensional automata. Finally, we investigate the recognizability of connected pictures of two-dimensional inkdot finite machines.

APA, Harvard, Vancouver, ISO, and other styles

28

Liagkou, Vasiliki, Panayotis E. Nastou, Paul Spirakis, and Yannis C. Stamatiou. "How Hard Is It to Detect Surveillance? A Formal Study of Panopticons and Their Detectability Problem." Cryptography 6, no. 3 (August 20, 2022): 42. http://dx.doi.org/10.3390/cryptography6030042.

Full text

Abstract:

The Panopticon (which means “watcher of everything”) is a well-known prison structure of continuous surveillance and discipline studied by Bentham in 1785. Today, where persistent, massive scale, surveillance is immensely facilitated by new technologies, the term Panopticon vaguely characterizes institutions with a power to acquire and process, undetectably, personal information. In this paper we propose a theoretical framework for studying Panopticons and their detectability status. We show, based on the Theory of Computation, that detecting Panopticons, modelled either as a simple Turing Machine or as an Oracle Turing Machine, is an undecidable problem. Furthermore, we show that for each sufficiently expressive formal system, we can effectively construct a Turing Machine for which it is impossible to prove, within the formal system, its Panopticon status. Finally, we discuss how Panopticons can be physically detected by the heat they dissipate each time they acquire, effortlessly, information in the form of an oracle and we investigate their detectability status with respect to a more powerful computational model than classical Turing Machines, the Infinite Time Turing Machines (ITTMs).

APA, Harvard, Vancouver, ISO, and other styles

29

GRÄDEL, ERICH. "ON THE NOTION OF LINEAR TIME COMPUTABILITY." International Journal of Foundations of Computer Science 01, no. 03 (September 1990): 295–307. http://dx.doi.org/10.1142/s0129054190000217.

Full text

Abstract:

To capture the informal concept of linear time computability, we propose and discuss the class TIME(n1+), consisting of all functions which are computable by a Successor RAM with exponent at most one; the exponent of a function is the infimum of all rational numbers r such that the function is computable in time O(nr). This class properly contains the class NLT (“Nearly Linear Time”)—proposed by Gurevich and Shelah—which contains all functions computable by a Successor RAM in time O(n(log n)k) for some k∈N. Both classes are very robust under changes of the underlying machine model: using the same time bounds they can be defined by Random Access Computers, Storage Modification Machines, Kolmogorov algorithms, Random Access Turing machines etc.; this distinguishes them from similar classes defined by ordinary Turing machines. However, we show that TIME(n1+) can be defined e.g. by multi-dimensional Turing machines or by Turing machines which can jump; this is probably not true for NLT. Furthermore we consider two notions of completeness for TIME(n1+) and construct complete problems. These problems are based on restrictions of Gurevich’s function logic for P.

APA, Harvard, Vancouver, ISO, and other styles

30

HARVÁTH, GÉZA, KATSUSHI INOUE, AKIRA ITO, and YUE WANG. "CLOSURE PROPERTY OF PROBABILISTIC TURING MACHINES AND ALTERNATING TURING MACHINES WITH SUBLOGARITHMIC SPACES." International Journal of Foundations of Computer Science 12, no. 03 (June 2001): 397–409. http://dx.doi.org/10.1142/s0129054101000552.

Full text

Abstract:

This paper first shows that (1) the class of languages recognized by o(log n) space-bounded two-way Monte Carlo Turing machines is not closed under concatenation, Kleene closure, and length-preserving homomorphism, and (2) the class of languages recognized by o(log log n) space-bounded two-way unbounded error probabilistic Turing machines is not closed under each of the above operations. We then show that the class of languages accepted by S(n) space-bounded two-way alternating Turing machines is not closed under each of the above operations for log log n ≤ S(n) ≤ o(log n).

APA, Harvard, Vancouver, ISO, and other styles

31

ITO, AKIRA, KATSUSHI INOUE, ITSUO TAKANAMI, and YASUYOSHI INAGAKI. "CONSTANT LEAF-SIZE HIERARCHY OF TWO-DIMENSIONAL ALTERNATING TURING MACHINES." International Journal of Pattern Recognition and Artificial Intelligence 08, no. 02 (April 1994): 509–24. http://dx.doi.org/10.1142/s0218001494000267.

Full text

Abstract:

“Leaf-size” (or “branching”) is the minimum number of leaves of some accepting computation trees of alternating devices. For example, one leaf corresponds to nondeterministic computation. In this paper, we investigate the effect of constant leaves of two-dimensional alternating Turing machines, and show the following facts: (1) For any function L(m, n), k leaf- and L(m, n) space-bounded two-dimensional alternating Turing machines which have only universal states are equivalent to the same space bounded deterministic Turing machines for any integer k≥1, where m (n) is the number of rows (columns) of the rectangular input tapes. (2) For square input tapes, k+1 leaf- and o(log m) space-bounded two-dimensional alternating Turing machines are more powerful than k leaf-bounded ones for each k≥1. (3) The necessary and sufficient space for three-way deterministic Turing machines to simulate k leaf-bounded two-dimensional alternating finite automata is nk+1, where we restrict the space function of three-way deterministic Turing machines to depend only on the number of columns of the given input tapes.

APA, Harvard, Vancouver, ISO, and other styles

32

Welch, P. D. "Eventually infinite time Turing machine degrees: infinite time decidable reals." Journal of Symbolic Logic 65, no. 3 (September 2000): 1193–203. http://dx.doi.org/10.2307/2586695.

Full text

Abstract:

AbstractWe characterise explicitly the decidable predicates on integers of Infinite Time Turing machines, in terms of admissibility theory and the constructible hierarchy. We do this by pinning down ζ, the least ordinal not the length of any eventual output of an Infinite Time Turing machine (halting or otherwise); using this the Infinite Time Turing Degrees are considered, and it is shown how the jump operator coincides with the production of mastercodes for the constructible hierarchy; further that the natural ordinals associated with the jump operator satisfy a Spector criterion, and correspond to the Lζ-stables. It also implies that the machines devised are “Σ2 Complete” amongst all such other possible machines. It is shown that least upper bounds of an “eventual jump” hierarchy exist on an initial segment.

APA, Harvard, Vancouver, ISO, and other styles

33

Beggs, Edwin, José Félix Costa, Bruno Loff, and J. V. Tucker. "Computational complexity with experiments as oracles. II. Upper bounds." Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 465, no. 2105 (February 25, 2009): 1453–65. http://dx.doi.org/10.1098/rspa.2008.0412.

Full text

Abstract:

Earlier, to explore the idea of combining physical experiments with algorithms, we introduced a new form of analogue–digital (AD) Turing machine. We examined in detail a case study where an experimental procedure, based on Newtonian kinematics, is used as an oracle with classes of Turing machines. The physical cost of oracle calls was counted and three forms of AD queries were studied, in which physical parameters can be set exactly and approximately. Here, in this sequel, we complete the classification of the computational power of these AD Turing machines and determine precisely what they can compute, using non-uniform complexity classes and probabilities.

APA, Harvard, Vancouver, ISO, and other styles

34

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

35

Marion, Bill. "Turing Machines and Computational Complexity." American Mathematical Monthly 101, no. 1 (January 1994): 61. http://dx.doi.org/10.2307/2325127.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Yenimazman, Deniz. "Political Theology and Turing Machines." Internationales Jahrbuch für Medienphilosophie 7, no. 1 (December 10, 2021): 161–78. http://dx.doi.org/10.1515/jbmp-2021-0009.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Neary, Turlough, and Damien Woods. "Four Small Universal Turing Machines." Fundamenta Informaticae 91, no. 1 (2009): 123–44. http://dx.doi.org/10.3233/fi-2009-0036.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Raghavan, Rama, H. Ramesh, Marian Gheorghe, and Shankara Narayanan Krishna. "On Restricted Bio-Turing Machines." Fundamenta Informaticae 110, no. 1-4 (2011): 309–20. http://dx.doi.org/10.3233/fi-2011-545.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Durand-Lose, Jérôme. "Small Turing universal signal machines." Electronic Proceedings in Theoretical Computer Science 1 (June 25, 2009): 70–80. http://dx.doi.org/10.4204/eptcs.1.7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Bartha, Miklós. "Turing Automata and Graph Machines." Electronic Proceedings in Theoretical Computer Science 26 (June 9, 2010): 19–31. http://dx.doi.org/10.4204/eptcs.26.3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

WRIGHT, CRISPIN. "Intuitionists Are Not (Turing) Machines." Philosophia Mathematica 3, no. 1 (1995): 86–102. http://dx.doi.org/10.1093/philmat/3.1.86.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Marion, Bill. "Turing Machines and Computational Complexity." American Mathematical Monthly 101, no. 1 (January 1994): 61–65. http://dx.doi.org/10.1080/00029890.1994.11996907.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Neary, Turlough, and Damien Woods. "Small fast universal Turing machines." Theoretical Computer Science 362, no. 1-3 (October 2006): 171–95. http://dx.doi.org/10.1016/j.tcs.2006.06.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Diaz, Nestor. "Behavior Classification for Turing Machines." Complex Systems 26, no. 3 (October 15, 2017): 283–94. http://dx.doi.org/10.25088/complexsystems.26.3.283.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Berrisford, G. "Reconciling OO with Turing machines." Computer Journal 37, no. 10 (October 1, 1994): 888–906. http://dx.doi.org/10.1093/comjnl/37.10.888.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Ito, Takao, Makoto Sakamoto, Hiroshi Furutani, Michio Kono, and Satoshi Ikeda. "Three-dimensional parallel Turing machines." Artificial Life and Robotics 13, no. 1 (December 2008): 364–67. http://dx.doi.org/10.1007/s10015-008-0500-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Finkel, Olivier, and Dominique Lecomte. "Decision problems for Turing machines." Information Processing Letters 109, no. 23-24 (November 2009): 1223–26. http://dx.doi.org/10.1016/j.ipl.2009.09.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Benioff, Paul. "Models of Quantum Turing Machines." Fortschritte der Physik 46, no. 4-5 (June 1998): 423–41. http://dx.doi.org/10.1002/(sici)1521-3978(199806)46:4/5<423::aid-prop423>3.0.co;2-g.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Manea, Florin. "On Turing Machines Deciding According to the Shortest Computations." Axioms 10, no. 4 (November 13, 2021): 304. http://dx.doi.org/10.3390/axioms10040304.

Full text

Abstract:

In this paper we propose and analyse from the computational complexity point of view several new variants of nondeterministic Turing machines. In the first such variant, a machine accepts a given input word if and only if one of its shortest possible computations on that word is accepting; on the other hand, the machine rejects the input word when all the shortest computations performed by the machine on that word are rejecting. We are able to show that the class of languages decided in polynomial time by such machines is PNP[log]. When we consider machines that decide a word according to the decision taken by the lexicographically first shortest computation, we obtain a new characterization of PNP. A series of other ways of deciding a language with respect to the shortest computations of a Turing machine are also discussed.

APA, Harvard, Vancouver, ISO, and other styles

50

Inoue, Katsushi, Akira Ito, and Itsuo Takanami. "A relationship between nondeterministic Turing machines and 1-inkdot turing machines with small space." Information Processing Letters 43, no. 4 (September 1992): 225–27. http://dx.doi.org/10.1016/0020-0190(92)90205-a.

Full text

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!