What Is a Turing Machine - Essay Example

TURING MACHINE Table of Contents Table of Contents 2 Introduction 3 Turing machines 3 Universal Turing machine 4 Structure 5 Performance comparison with real machines 6 Deterministic versus nondeterministic Turing machines 8 Recursive function with Turing Machine 8 Solubability and Unsolubability with Turing Machine 9 Problems with Turing Machine 9 Conclusion 10 References 11 Introduction A Turing machine is one kind of computer that is powerful however uncomplicated in structure. In addition, it is helpful in thinking regarding the limits and nature of computation and computability for the reason that its technique of computation is extremely simple as someone can visualize. Furthermore, significant theoretical outcomes regarding what can be calculated/computed that are articulated in the context of TM (Turing machines). Consequently the clearer to insight the similar outcomes presented in other expressions. A Turing machine can also be assumed like a theoretical device that is capable to operate symbols controlled by a strip of tape. In spite of its minimalism, a Turing machine could be modified to reproduce the logic of some computer algorithm, as well as this machine is mainly useful in illuminating the operations of a CPU within of a computer (Suber, 2002). This paper will present deep analysis of the different functionalities, operations, and uses of Turing machine. Turing machines According to Weisstein (2009) the concept of the Turing machine was initially presented by Alan Turing in 1937. He also invented the initial Turing machine that was presented like an idealized model intended for mathematical computation. A Turing machine composed of a line of cells acknowledged as a "tape" that can be moved back as well as forth. In a Turing machine there is an active component "head" that has a feature acknowledged as "state" that is capable to transform the attribute recognized as "color" of the active cell below it, and also a set of commands for how the head needs to be adjusted by the active cell as well as shift the tape. In addition, the machine can transform the color of the Turing machine active cell at any step. Also, it can transform the position of the head, and moving the tape one step towards right or left (Weisstein, Turing Machine, 2009; Sipser, 2005). Universal Turing machine Copeland (2000), discusses about Universal Turing Machine (UTM), which is a Turing machine that is capable to replicate other Turing machine. An additional mathematically-oriented description by a related "universal" nature was presented by Alonzo Church, whose effort on lambda calculus linked with Turing in a prescribed hypothesis of computation identified as the Church–Turing theory. The theory presents that a Turing machines certainly holds the informal view of useful technique in mathematics as well as in logic, and also offers an accurate explanation of a mechanical procedure or algorithm (Copeland, 2000). According to Aanderaa (2006), a universal Turing machine is capable to compute all kinds of recursive function, make a decision through some recursive language, and acknowledge every recursively enumerable language. The problems solvable through a universal Turing machine are just those problems resolved or solvable through an algorithm or an efficient technique of calculation, intended for some relational definition of those conditions. For these causes, a universal Turing machine provides a standard through which we can compare computational systems, and a system that is able to reproduce a universal Turing machine is identified as the Turing complete (Aanderaa, 2006). Structure Ken Schweller (2009) describes main structure of the Turing Machine. According to (Schweller, 2009), the Turing machine is the foundation of the contemporary theory of computability and computation; however, it was presented nine years earlier than the development of the initial electronic digital computer (Schweller, 2009; Cohen, 1996). According to Ken Schweller (2009), Turing Machine consists of: The Turing Machine itself An Input/ Output Tape A Rule List A Turing Machine itself is some type of mechanical black box that appears on the top of the tape and reads in signs one at a time by the help of write/read head. The Turing machine is constantly in a particular inner position designated through a number on the box. In Turing machine structure the Input/ Output Tape is similar to the roll of paper, and this paper roll is infinitely lengthy plus is prolonged similar to a scroll among two rollers consequently it be able to be wound backwards and forwards. The tape is separated into cells. These tape cells hold the output and input symbols and transform normally like a program is executing. In this structure, Rule List is intended to decide the Machines shift at some particular point (Schweller, 2009; Herken, 1995; Szepietowski, 1994). Working of Turing Machine In the operation of Turing-Machine the machine reads a symbol from the Input / Output Tape furthermore checks with its Rule List. After that machine carries out following actions: Turing-Machine transforms its inner state Turing-Machine writes a symbol on the tape or Turing-Machine shifts its R/W head left or right. The Turing-Machine tape is utilized to store data. As well, it is able to store a sequence of all transitions those are assembled in small programs as well as the head can execute sub-programs. At this stage it can be considered that Turing machine is following/emulating another one. In addition, as compared to modern computers, the Turing-Machine tape is the memory and the head is the microprocessor. Turing stated that this plain machine possibly will carry out all calculations that are outcomes of operations. In 1950, Turing stated that the mind is itself the outcomes of operations those are carried out at the neural level. Furthermore, this is the inventor of the artificial intelligence research and study (mapageweb, 2002; Hopcroft, Motwani, & Ullman, 2000). Performance comparison with real machines According to Velde (2004), Turing machines are not similar to simple automata. He states that Turing machines are more powerful as compared to the real machines. The main power of the Turing machines is that these machines are capable to execute the operations that a real machine can carry out. Almost all kinds of particular program executing on a particular machine and offering a finite sum of input are actually nothing but deterministic finite automata, as machine can execute simply finitely number of states. Turing machines are comparable to real machines that magically offer an infinite quantity of storage space. There are various different features that are discussed below: (Velde, 1993) & (Petersen, 2006). According to Petersen (2006), real machine’s less powerful models are too complex. In addition, the Turing machine offers less complex approach for describing an algorithm, for instance, it can take only few hundred states. On the other hand, the equivalent DFA of any given machine takes quadrillions (Petersen, 2006). Petersen (2006) stated that Turing machines are capable to illustrate algorithms at once over the entire kinds of the machines. In the explanation there are no limits on the memory they are having. There is an utmost to the amount of memory some machine has currently, however this limit be able to increase randomly in time. Statements regarding algorithms need to be timeless (Petersen, 2006). According to Velde (2004), Turing machines are capable to express algorithms without reference to some kind of machine-specific characteristics like that memory bound (Velde, 1993). According to Velde (2004) Turing machines make things easier with respect to the statement of algorithms. Algorithms executing on Turing corresponding abstract machines are typically additional broader than their corresponding running on real machines, for the reason that they have arbitrary-precision data-types accessible as well as by no means have to arrangement by unanticipated conditions like that running out of memory (Velde, 1993). Deterministic versus nondeterministic Turing machines Deterministic or normal Turing Machine consists of a guessing head. This head is a write-only head that is capable to write a guess at a problem solution on the Turing Machine tape initially, which is based on some arbitrary internal algorithm. Therefore, the regular Turing Machine then executes and offers "no" or "yes" to denote whether the solution is accurate (Szepietowski, 1994). On the other hand, a non-deterministic Turing Machine can resolve computational decision problems nature of non-deterministic polynomial time, in a number of computational steps that is a polynomial function of the volume of the input (Szepietowski, 1994). Recursive function with Turing Machine In Turing Machine the recursive function concept is the investigation of the functions that can be described by means of recursive methods. In other words, the primitive recursive functions are described as functions those can be shaped into the fundamental functions: by (Barker, 2004) The Zero Function: Z(x)= 0, for all x The Successor function: S(x)= x+1, for all x The ith projection over j arguments: pi,j(x0,…xj)= xi, for all xi, i, j Table 1 Recursive function source: (Barker, 2004) Composition: f(x1,…,xn) = g(h1(x1,…,xn),…, hm(x1,…,xn)), for all g,h1,…,hm Primitive Recursion: f(x,0) = g(x), for any g f(x,s(y)) = h(x,y,f(x,y)), for any h Minimization: h(x1,…,xn) = y, if f(x1, …,xn,y)=0 and ∀t Read More