Search

We discuss the formalization, in the Matita Theorem Prover, of basic results on multi-tapes Turing machines, up to the existence of a (certified) Universal Machine, and propose it as a natural benchmark for comparing different interactive provers and assessing the state of the art in the mechanization of formal reasoning. The work is meant to be a preliminary step towards the creation of a formal repository in Complexity Theory, and is a small piece in our long-term Reverse Complexity program, aiming to a comfortable, machine independent axiomatization of the field.

In this paper, a robust and as simple as possible concept of a Petri net (PN) computer is proposed. It has a similar structure and behavior to weak sound priority workflow nets. It is shown that all recursive functions are PN computable and, vice-versa, PN computable functions are recursive. This shows that the PN computers we have proposed have exactly the power of Turing machines. Complexity classes of PN computable functions are defined, and the relationship between them and similar complexity classes defined by counter machines is investigated. Finally, the close relationship between PN computers and weak sound (priority) workflow nets is investigated.

International audience; Frustrated by another failed software installation? Wondering why you can't reproduce your colleagues' computations? This story will tell you why. It won't magically solve your problems, but it does point out a glimpse of hope for the future. It's one of those days in the life of a computational scientist. Your desktop computer is busy updating its operating system and doesn't have any time left for you. The installation of your favorite simulation software on the new supercomputer doesn't advance beyond an error message extending over 500 lines. And your data analysis hasn't made much progress either: the results change when you use more or fewer processors, which doesn't look right. You already asked Siri for advice, but as so often is the case, that conversation led absolutely nowhere. Computers are complex, frustrating machines. If only we could have simple ones that just did what we tell them to do! Maybe it's a good idea to go back to the basics. Ever heard of Turing machines? They were invented in 1937 by Alan Turing, 1 and they're as simple as computers can get. No keyboard, no screen, no hard disk-no operating system either, nor any voices pestering you. You write your instructions on a tape, put the tape into the machine, and push a button. The machine starts working, moving the tape back and forth. When it stops, you take out the tape again and read off the result. Computing couldn't be simpler! Turing invented the machine that was later named after him as a purely theoretical concept. There wasn't much real computing hardware available back then, but people eventually built physical realizations (www.legoturingmachine.org/lego-turing-machine, http://aturingmachine.com, and

A Markov–Post algorithm and a Turing machine, which have mutual upper bounds on time and space, are proven to be interchangeable up to a linear function of space and a polynomial of time for the Turing machine, respectively. No more than two-letter extensions of the exterior alphabet are used.

In this chapter I show, first, what modifications are needed in order to make the design of a Turing machine more suitable for being used as a model of human computation. The result of these modifications is a special kind of TM-inspired computational system, i.e. the Bidimensional Turing machine. Second, I introduce the notion of a Galilean model, namely, a concept of empirical adequacy for cognitive models (Giunti 1995) and I propose to consider Bidimensional Turing machines as a possible Galilean models.

In the paper we interpret the Church Turing thesis of Computation Algorithm and how it differs from the strong Church Turing thesis in the field of computation. Church Turing thesis can be classified as Strong Church Turing thesis and Normal Church Turing thesis. Church Turing hypothesis says “that a computing problem can be solved in any computer if and only if it can be solved on a very simple ‘machine’, named TURING MACHINE”. We introspect the difference in the model of computers that are developed on these two competitive algorithms. We will also be studying the physical realization of bits in a quantum computer with special mention to the commercial quantum computer systems offered at the moment. Our objective is to find out the relation of a quantum bit and the Strong Church Turing Thesis converging the gap between theoretical model and physical structure.

The Turing machine can be used for rigorous study of the computation theory. In theory the Turing machine can simulate modern computers, but the actual implementation would be very difficult. This paper proposes a framework of Turing machine developing system. This developing system has been used successfully to implement a special Turing machine that is capable of executing Java bytecode. Demonstrations of this paper have shown the effectiveness of adopting the Turing machine for practical computation. In addition, the developing system can be applied to demonstrate the principle and concept of Turing machines.

The articles in this issue span a remarkable range of topics that testify to the richness of Alan Turing's intellectual legacy in the modern conception of computation. There are deep connections with fundamental issues in physics, mathematics, artificial intelligence, philosophy and beyond. One group of articles studies the aspects of classical foundations of computation that show surprising connections to a wide range of topics of current concern. In particular, the basic concept of viewing programs as data, in which Turing anticipated the von Neumann architecture of the stored program computer, opens up a huge range of possibilities, which are still far from being completely explored or understood. — From mathematician Robert I. Soare [1], we have a major reappraisal of Turing's classical 1930s work on machine computation, and the balance between program and information. Quoting Feferman's reference to the oracle Turing machine as a ‘new idea that was to change the face of the general theory of computation’, Soare traces the historical and contemporary significance of the oracle machine over a range of fields. — The article by Jones & Simonsen [2] discusses the ramifications of the programs as data concept and considers general desirable features of models of computation. It discusses a recently proposed model, motivated by biology, the ‘blob’ model, and to what extent it meets these ideal features and how the remaining desiderata could be addressed. — The article by Marion [3] is motivated by applications of Kleene's second recursion theorem, which is the key mathematical fact expressing the power of the program-as-data concept, to modelling computer viruses. The key features of viruses are self-replication and mutation. The paper discusses a concrete computational model of these features in the form of self-modifying register machines. — The article by Dershowitz [4] discusses the classical Turing notion of universality, with a careful foundational consideration of the constraints that need to be imposed on the coding of programs and on pairing in order to avoid ‘cheating’, which would vitiate the analysis of computation, leading to a notion of ‘honest universality’. Another group of articles discusses various aspects of the connections between computation and physics. — The article by Dowek [5] discusses the physical Church–Turing thesis and the issue of non-deterministic computation represented in terms of effectively enumerable relations as an algorithmic basis for expressing non-deterministic physical theories. — Beggs and co-workers [6] investigate an abstract framework for interfacing algorithms and physical systems, with the notion of oracle again taking centre stage. There are basic motivational questions to this work, including: ‘How much information can be extracted from a physical process? How quickly can it obtained?’. — Hardy [7] describes a novel formulation for quantum mechanics that is based much more directly on operational concepts than on the traditional Hilbert-space formalism. This formalism makes extensive use of diagrammatic representations of ‘operator tensors’. It is close in spirit to computationally inspired formalisms. — Ekert et al. [8] show how Bell's theorem in the foundations of quantum mechanics leads to a fundamentally novel approach to the whole issue of cryptography, another central concern of Turing's scientific career. — Vazirani & Vidick [9] show that quantum mechanics can be used to produce a source of genuine randomness, with an accompanying kind of ‘Turing test’ that uses no-signalling properties of the device to certify that true randomness has been achieved. Again, there are connections with Bell's theorem in the foundations of quantum mechanics. Much of Turing's early work in logic is related to real computation, with subsequent anticipations of the important role of randomness. — Proof-mining delivers new information via the process of logically bringing out the constructive elements of proofs described in a natural language. Kohlenbach & Leustean [10] describe some recent developments in the context of Turing's seminal work on computable real numbers. — Montalban [11] reviews recent work applying the technical framework of classical computability to measure the complexity of relations over particular structures. The viewpoint developed in this article aims to make the area approachable to a wider community of researchers. — The article by Barmpalias & Dowe [12] arises from Wallace's work on information theory, with regard to his interest in the notion of a real preserving universality with respect to a prefix-free machine, and in particular the probability of this event. — Allender et al. [13] relate their work to Turing's interest in probabilistic computation, and to the role of random elements. The article is a useful addition to recent developments in the area of derandomization. A key element of the Turing legacy is his work on information and intelligent machines, and their philosophical, theoretical and practical dimensions. The articles that conclude this Theme Issue are diverse, innovative and sure to be provocative. — We start this part with a scene-setting philosophical paper on information and levels of abstraction, a key concept to Turing's extraction of meaningful questions from their more ill-defined everyday versions. Floridi [14] relates three main philosophical questions on the nature and role of information to what ‘promises to be one of the most exciting and beneficial areas of philosophical research of our time’. — Smolensky [15] starts out from the widespread assumption, going back to Turing, that thought is computation over ideas. This article presents a computational account of cognition, modelling the computation of symbolic mental functions with subsymbolic neural computation. — Focusing on computational learning theory, Case & Kotzing [16] pay tribute to ‘Alan Turing's wonderfully profound and influential ideas about mind and mechanism’, and proceed to analyse the problem of algorithmically learning a description for an infinite sequence presented via larger and larger initial segments of that sequence. — Seth Lloyd [17] contributes the final article in this remarkable collection, with the enticing title ‘A Turing test for free will’. According to this test, ‘a decision maker who passes this test will tend to believe that he, she or it possesses free will, whether the world is deterministic or not’. It is in the nature of centenaries that they present the celebrants with fast approaching deadlines of disturbing solidity. Even as we write this, we are thankful to our authors and anonymous reviewers, and to Suzanne Abbott, our encouraging and ever-patient editor at the Royal Society, for making this Turing Theme Issue possible. We are happy to see such an appropriate tribute to Alan Turing materialize, and can only wish to still be here to see what new developments the bi-centenary Theme Issue will bring!

The theory of analog computation aims at modeling computational systems that evolve in a continuous space. Unlike the situation with the discrete setting there is no unified theory of analog computation. There are several proposed theories, some of them seem quite orthogonal. Some theories can be considered as generalizations of the Turing machine theory and classical recursion theory. Among such are recursive analysis and Moore's class of recursive real functions. Recursive analysis was introduced by Turing (Proc Lond Math Soc 2(42):230---265, 1936), Grzegorczyk (Fundam Math 42:168---202, 1955), and Lacombe (Compt Rend l'Acad Sci Paris 241:151---153, 1955). Real computation in this context is viewed as effective (in the sense of Turing machine theory) convergence of sequences of rational numbers. In 1996 Moore introduced a function algebra that captures his notion of real computation; it consists of some basic functions and their closure under composition, integration and zero-finding. Though this class is inherently unphysical, much work have been directed at stratifying, restricting, and comparing it with other theories of real computation such as recursive analysis and the GPAC. In this article we give a detailed exposition of recursive analysis and Moore's class and the relationships between them.

In this note, we consider constraints on the physical possibility of transfinite Turing machines that arise from how one models the continuous structure of space and time in one's best phys...

We reply to Hector Levesque's critique of the Turing Test and his proposal for "a new type of Turing Test", a Winograd Schema Test. We question whether the role of deception in the Turing Test is, as Levesque asserts, "a serious problem". We argue that the Levesque Test specifies the nature of intelligence in a way that Turing wished to avoid. We conclude that the Turing Test appeals to the collective judgment of humankind, a judgment that, in the case of AI, has yet to be rendered.

The complexity of the behaviour that some simple cellular automata (CA) can exhibit is clearly shown by a demonstration of universal computation. The ability to perform any calculation that a Turing machine can make. The construction of such a machine necessarily requires areas covered by repeating patterns for storage of data and programs as well as areas of variation encoding information on a more direct way producing an uneven texture when viewed at a distance. These textures together with the inherent symmetry of the design lead naturally to artistically pleasing images.

The focus of this paper is state diagrams that are used to represent state machines. Current diagrammatic representations of state machines are almost too compacted and do not completely depict their underlying semantics or clarify basic static structure and elementary dynamic features. The paper proposes using a new diagrammatic representation for state-based depictions. Advantages of the new diagrams include enhanced understanding of the related problems and exposure to new variations in viewing state machines and how to reflect about them. The proposed method is demonstrated through diagramming of a traffic light controller that has been represented in state and statechart diagrams. In addition, a Turing machine example is depicted by the new methodology.

Given a strong bimonoid P, we introduce P-valued non-deterministic Turing machines (P-NTM), P-valued non-deterministic Turing machines with classical transition (P-NTMc), P-valued deterministic Turing machines (P-DTM) and P-valued non-deterministic Turing machines with the tape-head no remove (P-NTMS). We adapt depth-first and width-first methods for defining the weight of acceptance of languages recognized by Turning machines. And we study some basic properties of P-NTM, P-NTMc, P-NTMS. Moreover, We prove that variants of P-NTM with changing its P-valued initial function have the same power as P-NTM. These conclusions still hold for P-NTMc and P-NTMS.

The relationship between structure and function is explored via a system of labeled directed graph structures upon which a single elementary read/write rule is applied locally. Boundaries between static (information-carrying) and active (information-processing) objects, imposed by mandate of the rules or physics in earlier models, emerge instead as a result of a structure-function dynamic that is reflexive: objects may operate directly on their own structure. A representation of an arbitrary Turing machine is reproduced in terms of structural constraints by means of a simple mapping from tape squares and machine states to a uniform medium of nodes and links, establishing computation universality. Exploiting flexibility of the formulation, examples of other unconventional “self-computing” structures are demonstrated. A straightforward representation of a kinematic machine system based on the model devised by Laing is also reproduced in detail. Implications of the findings are discussed in terms of their relation to other formal models of computation and construction. It is argued that reflexivity of the structure-function relationship is a critical informational dynamic in biochemical systems, overlooked in previous models but well captured by the proposed formulation.

Turing's notion of human computability is exactly right not only for obtaining a negative solution of Hilbert's Entscheidungsproblem that is conclusive, but also for achieving a precise characterization of formal systems that is needed for the general formulation of the incompleteness theorems. The broad intellectual context reaches back to Leibniz and requires a focus on mechanical procedures; these procedures are to be carried out by human computers without invoking higher cognitive capacities. The question whether there are strictly broader notions of effectiveness has of course been asked for both cognitive and physical processes. I address this question not in any general way, but rather by focusing on aspects of mathematical reasoning that transcend mechanical procedures. Section 1 discusses Godel's perspective on mechanical computability as articulated in his [193?], where he drew a dramatic conclusion from the undecidability of certain Diophantine propositions, namely, that mathematicians cannot be replaced by machines. That theme is taken up in the Gibbs Lecture of 1951; Godel argues there in greater detail that the human mind infinitely surpasses the powers of any finite machine. An analysis of the argument is presented in Section 2 under the heading Beyond calculation. Section 3 is entitled Beyond discipline and gives Turing's view of intelligent machinery; it is devoted to the seemingly sharp conflict between Godel's and Turing's views on mind. Their deeper disagreement really concerns the nature of machines, and I'll end with some brief remarks on (supra-) mechanical devices in Section 4.

We propose a construction of an accepting hybrid network of evolutionary processors (AHNEP) which behaves as a universal device in the class of all these devices. We first construct a Turing machine which can simulate any AHNEP and then an AHNEP which simulates the Turing machine. We think that this approach can be applied to other bio-inspired computing models which are computationally complete.

The concept of a structured Turing machine is introduced. Every Turing machine is demonstrated to be equivalent to some structured Turing machine. Various refinements of the problem of structurization are considered and, in particular, refinements in which any extension of the working alphabet being used is prohibited.

We introduce the safe recursive set functions based on a Bellantoni–Cook style subclass of the primitive recursive set functions. We show that the functions computed by safe recursive set functions under a list encoding of finite strings by hereditarily finite sets are exactly the polynomial growth rate functions computed by alternating exponential time Turing machines with polynomially many alternations. We also show that the functions computed by safe recursive set functions under a more efficient binary tree encoding of finite strings by hereditarily finite sets are exactly the quasipolynomial growth rate functions computed by alternating quasipolynomial time Turing machines with polylogarithmic many alternations.We characterize the safe recursive set functions on arbitrary sets in definability-theoretic terms. In its strongest form, we show that a function on arbitrary sets is safe recursive if and only if it is uniformly definable in some polynomial level of a refinement of Jensen's J-hierarchy, relativized to the transitive closure of the function's arguments.We observe that safe recursive set functions on infinite binary strings are equivalent to functions computed by infinite-time Turing machines in time less than ωω. We also give a machine model for safe recursive set functions which is based on set-indexed parallel processors and the natural bound on running times.

(2002). Why Turing machine equivalence is (still) important in cognitive science: a reply to Eliasmith. Journal of Experimental & Theoretical Artificial Intelligence: Vol. 14, No. 1, pp. 9-12.

The properties of Turing's famous ‘universal machine’ has long sustained functionalist intuitions about the nature of cognition. This paper shows that there is a logical problem with standard functionalist arguments for multiple realizability. These arguments rely essentially on Turing's powerful insights regarding computation. In addressing a possible reply to this criticism, it is further argued that functionalism is not a useful approach for understanding what it is to have a mind. In particular, it is shown that the difficulties involved in distinguishing implementation from function make multiple realizability claims untestable and uninformative. As a result, it is concluded that the role of Turing machines in philosophy of mind needs to be reconsidered.

I use modal logic and transfinite set-theory to define metaphysical foundations for a general theory of computation. A possible universe is a certain kind of situation; a situation is a set of facts. An algorithm is a certain kind of inductively defined property. A machine is a series of situations that instantiates an algorithm in a certain way. There are finite as well as transfinite algorithms and machines of any degree of complexity (e.g., Turing and super-Turing machines and more). There are physically and metaphysically possible machines. There is an iterative hierarchy of logically possible machines in the iterative hierarchy of sets. Some algorithms are such that machines that instantiate them are minds. So there is an iterative hierarchy of finitely and transfinitely complex minds.

Turing's (1936) analysis of effective symbolic procedures is a model of conceptual clarity that plays an essential role in the philosophy of mathematics. Yet appeal is often made to the effectiveness of human procedures in other areas of philosophy. This paper addresses the question of whether Turing's analysis can be applied to a broader class of effective human procedures. We use Sieg's (1994) presentation of Turing's Thesis to argue against Cleland's (1995) objections to Turing machines and we evaluate her proposal to understand the effectiveness of procedures in terms of their reliability and precision. A number of conditions for effectiveness are identified and these are used to provide a general argument against the possibility of a Leibnizian decision procedure.

In this paper, we propose the ?-machine model for social machines. By introducing a cluster of "oracles" to a traditional Turing machine, the ?-machine is capable of describing the interaction between human participants and mechanical machines. We also give two examples of social machines, collective intelligence and rumor spreading, and demonstrate how the general ?-machine model could be used to simulate their computations.

In the technical literature of computer science, the concept of an effective procedure is closely associated with the notion of an instruction that precisely specifies an action. Turing machine instructions are held up as providing paragons of instructions that "precisely describe" or "well define" the actions they prescribe. Numerical algorithms and computer programs are judged effective just insofar as they are thought to be translatable into Turing machine programs. Nontechnical procedures (e.g., recipes, methods) are summarily dismissed as ineffective on the grounds that their instructions lack the requisite precision. But despite the pivotal role played by the notion of a precisely specified instruction in classifying procedures as effective and ineffective, little attention has been paid to the manner in which instructions "precisely specify" the actions they prescribe. It is the purpose of this paper to remedy this defect. The results are startling. The reputed exemplary precision of Turing machine instructions turns out to be a myth. Indeed, the most precise specifications of action are provided not by the procedures of theoretical computer science and mathematics (algorithms) but rather by the nontechnical procedures of everyday life. I close with a discussion of some of the rumifications of these conclusions for understanding and designing concrete computers and their programming languages.

Reinhardt's strong mechanistic thesis, a formalization of “I know I am a Turing machine”, is shown to be consistent with Epistemic Arithmetic.

In the 1950s, Alan Turing proposed his influential test for machine intelligence, which involved a teletyped dialogue between a human player, a machine, and an interrogator. Two readings of Turing's rules for the test have been given. According to the standard reading of Turing's words, the goal of the interrogator was to discover which was the human being and which was the machine, while the goal of the machine was to be indistinguishable from a human being. According to the literal reading, the goal of the machine was to simulate a man imitating a woman, while the interrogator – unaware of the real purpose of the test – was attempting to determine which of the two contestants was the woman and which was the man. The present work offers a study of Turing's rules for the test in the context of his advocated purpose and his other texts. The conclusion is that there are several independent and mutually reinforcing lines of evidence that support the standard reading, while fitting the literal reading in Turing's work faces severe interpretative difficulties. So, the controversy over Turing's rules should be settled in favor of the standard reading.

Intuitively, a real number is recursive if we can get as accurate an approximation as we like, using a mechanical procedure such as a Turing machine. A real function is recursive if its value at a point x in its domain can be approximated effectively given an approximation to x . However, since there are only countably many Turing machines, there must be uncountably many non-recursive reals and functions. In this paper, we study some of these non-recursive reals and functions using a more recursion theoretic approach, via the degree of unsolvability. In particular, we are interested in reals and real functions that are relatively recursive in ∅′, where ∅′ is the jump of the recursive degree ∅′. Inspired by the Shoenfield Limit Lemma, we show that a real is ∅′-recursive if and only if it is the limit of a recursive sequence of rationals. We then give three characterizations of a ∅′-recursive function which are stated in terms of Turing machine, uniform convergence, and sequential computability with uniform continuity. A proof of their equivalence using a finite injury priority argument is given. With the new definitions, we can now give an upper bound to the difficulty of some uncomputable analysis operator such as differentiations and root findings.

Theory of Computation students frequently fail to appreciate the significance of the Church---Turing Thesis for one of two reasons. First, there is a tendency, on the part of students, to regard Church---Turing as tautologous and, consequently, devoid of important content. Second, there is a contrary impulse to view Church---Turing as unmotivated or even implausible. We describe our experience using simulation software in an effort to combat these two tendencies.

Turing's analysis of computation is a fundamental part of the background of cognitive science. In this paper it is argued that a re-interpretation of Turing's work is required to underpin theorizing about cognitive architecture. It is claimed that the symbol systems view of the mind, which is the conventional way of understanding how Turing's work impacts on cognitive science, is deeply flawed. There is an alternative interpretation that is more faithful to Turing's original insights, avoids the criticisms made of the symbol systems approach and is compatible with the growing interest in agent-environment interaction. It is argued that this interpretation should form the basis for theories of cognitive architecture.

In this paper we compare recursively enumerable subsets of Rq in two computing models over real numbers: the Blum-Shub-Smale machine and the oracle Turing machine. We prove that any Turing RE open subset of Rq is a BSS RE set, while a Turing RE closed set may not be a BSS RE set. As an application we show that the Julia set of any computable hyperbolic polynomial is decidable in the Turing computing model.

Purpose.The purpose of this paper is to study a class of the natural languages called the lattice-valued phrase structure languages, which can be generated by the lattice-valued type 0 grammars and recognized by the lattice-valued Turing machines.Design/Methodology/Approach.From the characteristic of natural language, this paper puts forward a new concept of the l-valued Turing machine. It can be used to characterize recognition, natural language processing, and dynamic characteristics.Findings.The mechanisms of both the generation of grammars for the lattice-valued type 0 grammar and the dynamic transformation of the lattice-valued Turing machines were given.Originality/Value.This paper gives a new approach to study a class of natural languages by using lattice-valued logic theory.

In this paper we sketch an ACL2-checked proof that a simple but unbounded Von Neumann machine model is Turing Complete, i.e., can do anything a Turing machine can do. The project formally revisits the roots of computer science. It requires re-familiarizing oneself with the definitive model of computation from the 1930s, dealing with a simple “modern” machine model, thinking carefully about the formal statement of an important theorem and the specification of both total and partial programs, writing a verifying compiler, including implementing an X86-like call/return protocol and implementing computed jumps, codifying a code proof strategy, and a little “creative” reasoning about the non-termination of two machines.

In this paper, the problem of applying changes to software at runtime is con- sidered. The computability theory is used in order to develop a more general and programming-language-independent model of computation with support for runtime changes. Various types of runtime changes were defined in terms of computable functions and Turing machines. The properties of such functions and machines were used to prove that arbitrary runtime changes on Turing machines are impossible in general cases. A method of Turing machine decom- position into subtasks was presented and runtime changes were defined through transformations of the subtask graph. Requirements for the possible changes were considered with regard to the possibility of subtask execution during such changes. Finally, a runtime change model of computation was defined by exten- sion of the Universal Turing Machine.

A new definition of universal Turing machines is introduced which allows to obtain universal Turing machines with a very small number of program instructions. Here such a program with only seventeen instructions is supplied.

In this paper I discuss the topics of mechanism and algorithmicity. I emphasise that a characterisation of algorithmicity such as the Turing machine is iterative; and I argue that if the human mind can solve problems that no Turing machine can, the mind must depend on some non-iterative principle — in fact, Cantor's second principle of generation, a principle of the actual infinite rather than the potential infinite of Turing machines. But as there has been theorisation that all physical systems can be represented by Turing machines, I investigate claims that seem to contradict this: specifically, claims that there are noncomputable phenomena. One conclusion I reach is that if it is believed that the human mind is more than a Turing machine, a belief in a kind of Cartesian dualist gulf between the mental and the physical is concomitant.

We formalise results from computability theory in the theorem prover Isabelle/HOL. Following the textbook by Boolos et al, we formalise Turing machines and relate them to abacus machines and recursive functions. We "tie the know" between these three computational models by formalising a universal function and obtaining from it a universal Turing machine by our verified translation from recursive functions to abacus programs and from abacus programs to Turing machine programs. Hoare-style reasoning techniques allow us to reason about concrete Turing machine and abacus programs.

The classical Turing machine model has defects in centralized control, sequential and determinate execution. So it is difficult to describe the computing in parallel environments and interactive systems. In this paper, we introduce several ideas for the extension of the classical Turing machine model, including three aspects: the input and output, process of state transformation and transformation rules. Focused on two aspects of scheduling method and the interaction model, we compare the differences in state control rules between the classical Turing machine model and the Internet model, then trying to extend the classical Turing machine model with the help of the network model. Finally, we introduce the role of virtualization in the implementation of the network Turing machine model. Keywords-classical Turing machine model; unified scheduling; state transformation; network Turing machine model; virtualization

Alan Turing’s pioneering work on computability, and his ideas on morphological computing support Andrew Hodges’ view of Turing as a natural philosopher. Turing’s natural philosophy differs importantly from Galileo’s view that the book of nature is written in the language of mathematics (The Assayer, 1623). Computing is more than a language used to describe nature as computation produces real time physical behaviors. This article presents the framework of Natural info-computationalism as a contemporary natural philosophy that builds on the legacy of Turing’s computationalism. The use of info-computational conceptualizations, models and tools makes possible for the first time in history modeling of complex self-organizing adaptive systems, including basic characteristics and functions of living systems, intelligence, and cognition.

Based on the definition of single-tape Fuzzy Non-deterministic Turing Machine (FNTM), this article discussed in details the process of FNTM accepting language and researched the computational complexity of fuzzy Turing Machine (TM) accepting ?-cut language by using the Deterministic Turing Machine (DTM) to simulate its process, thus drawing the conclusion that the judgment of FNTM accepting ?-cut language is a matter of the NP-completeness, and that it is not essentially helpful to adjust the membership degree in facing the time complexity problem when simulating the process of FNTM accepting the language.

Various methods exists in the litearture for denoting the configuration of a Turing Machine. A key difference is whether the head position is indicated by some integer (mathematical representation) or is specified by writing the machine state next to the scanned tape symbol (intrinsic representation). From a mathematical perspective this will make no difference. However, since Turing Machines are primarily used for proving undecidability and/or hardness results these representations do matter. Based on a number of applications we show that the intrinsic representation should be preferred.

We discuss the formalization, in the Matita Theorem Prover, of a few, basic results on Turing Machines, up to the existence of a (certified) Universal Machine. The work is meant to be a preliminary step towards the creation of a formal repository in Complexity Theory, and is a small piece in our Reverse Complexity program, aiming to a comfortable, machine independent axiomatization of the field.

We enhance the notion of a computation of the classical theory of computing with the notion of interaction. In this way, we enhance a Turing machine as a model of computation to a Reactive Turing Machine that is an abstract model of a computer as it is used nowadays, always interacting with the user and the world.

We construct a universal reversible Turing machine (URTM) from first principles. We take a strict approach to the semantics of reversible Turing machines (RTMs), under which they can compute exactly all injective, computable functions, but not non-injective ones. The natural notion of universality for RTMs is RTM-universality, where programs are considered part of both input and output of a URTM. The machine described here is the first URTM which does not depend on reversibilizing any existing universal machine. The interpretive overhead of the URTM is limited to a (program dependent) constant factor slowdown, with no other complexity-wise cost wrt time and space. The URTM is also able to function as an inverse interpreter for RTMs at no asymptotic cost, simply by reversing the string representing the interpreted machine.

Received: 18 November 2010 / Accepted: 9 March 2011 (c) The Author(s) 2011. This article is published with open access at Springerlink.com The issue of adequacy of the Turing Test (TT) is addressed. The concept of Turing Interrogative Game (TIG) is introduced. We show that if some conditions hold, then each machine, even a thinking one, loses a certain TIG and thus an instance of TT. If, however, the conditions do not hold, the success of a machine need not constitute a convincing argument for the claim that the machine thinks.

Here we continue the study of bio-Turing machines introduced in [2] and further investigated in [17]. We introduce a restricted model of bio-Turing machine and we investigate its computational power, a hierarchy of languages accepted, and deterministic and nondeterministic variants. A comprehensive example illustrating the modelling power of the introduced machine ends the paper.

In the “correct” definition of randomized space-bounded computation, the machine has access to a random coin. The coin can be flipped at will, but outcomes of previous coin flips cannot be recalled unless they are saved in the machine's limited memory. In contrast to this read-once mechanism of accessing the random source, one may consider Turing machines which have access to a random tape. Here, the random bits may be multiply accessed by the machine. In this note we show a very concrete sense in which multiple access to the random bits is better than read-once access to them: Every language accepted with bounded 2-sided error by a read-once-randomized logspace machine, can be accepted with zero error by a randomized logspace machine having multiple access to the random bits. Finally, we characterize the clsss of languates that can be accepted with two-sided error by randomized logspace machines with multiple access to the random bits as exactly the class of languages that are in logspace to almost every oracle.

In the light of the relation between the input and the output of the qualitative mapping units, this paper will give a Homomorphism relation between the Turing machine and the qualitative mapping unit, thus further prove the Homomorphism relation between the non-attribute-feedback multi-layer networks. Recursive function and Lambda Calculus are also reconstructed based on attitude theory.