Turing machine


Also found in: Dictionary, Thesaurus, Acronyms, Wikipedia.
Related to Turing machine: Alan Turing

Turing machine,

a mathematical model of a device that computes via a series of discrete steps and is not limited in use by a fixed maximum amount of data storage. Introduced by the British mathematician Alan TuringTuring, Alan Mathison,
1912–54, British mathematician and computer theorist. While studying at Cambridge he began work in predicate logic that led to a proof (1937) that some mathematical problems are not susceptible to solution by automated computation; in arriving at
..... Click the link for more information.
 in 1936, a Turing machine is a particularly simple computercomputer,
device capable of performing a series of arithmetic or logical operations. A computer is distinguished from a calculating machine, such as an electronic calculator, by being able to store a computer program (so that it can repeat its operations and make logical
..... Click the link for more information.
, one whose operations are limited to reading and writing symbols on tape, or moving along the tape to the left or to the right one symbol at a time. Its behavior at a given moment is determined by the symbol in the square currently being read and by the current state of the machine. The theoretical prototype of the electronic digital computer, Turing machines are one of the key abstractions used in modern computability theory, the study of what computers can and cannot do. Appropriate Turing machines have found application in the study of artificial intelligence, the structure of languages, and pattern recognition.
The Columbia Electronic Encyclopedia™ Copyright © 2013, Columbia University Press. Licensed from Columbia University Press. All rights reserved. www.cc.columbia.edu/cu/cup/
The following article is from The Great Soviet Encyclopedia (1979). It might be outdated or ideologically biased.

Turing Machine

 

the name applied to abstract, or conceptual, “computing machines” of a certain precisely described type that provide a precise version, suitable for the purposes of mathematical consideration, of the general intuitive idea of an algorithm. The concept of such a machine was formulated in the mid-1930’s by A. M. Turing as a result of his analysis of the actions of a person carrying out certain calculations, that is, successive transformations of complexes of symbols, in accordance with a previously developed plan.

It is convenient to regard a Turing machine as an automatically operating device that is capable of being in a finite number of internal states and is provided with an infinite external memory, a tape. Among the states are two special ones, the initial state and the final state. The tape is divided into squares and is unbounded to the right and to the left. Any symbol included in some previously given list may be written in each square of the tape (for uniformity it is assumed that a blank is written in an empty square). At every moment in time the Turing machine is in one of its states; in this state it scans a square of the tape by means of a special apparatus and reads the symbol written in that square. If the Turing machine is in a nonfinal state at a given moment in time, then at the next moment the machine executes one of the following operations: (1) it changes to a new state, which may be, for example, the final state or the same as the old state; (2) it replaces the old symbol in the square being scanned with a new symbol, which may be, for example, a blank or the same symbol as the old one; and (3) it shifts the tape one square to the left or right or holds the tape in place. Such a step of the Turing machine is completely determined by the machine’s state at a given moment and the symbol being read. A table that contains the full list of possible steps for a given Turing machine is called the program of the machine.

A complete description of a Turing machine at a given moment is given by its configuration, which is a specification of the following information for the given moment: (1) the actual symbols contained in the squares of the tape, (2) the square being read by the machine, and (3) the state of the machine.

If any configuration with a nonfinal state is taken as an initial configuration of a given Turing machine, then the operation of the machine will consist in the sequential step-by-step transformation of the initial configuration in accordance with the machine’s program until a configuration with a final state is attained. The latter configuration, if it exists, is considered the result of the operation of the given Turing machine on the initial configuration.

Strong arguments exist for considering that the concept of a Turing machine supplies an adequate precise formulation of the general concept of an algorithm, that is, that any algorithm can be modeled by a suitable Turing machine. This hypothesis is known in the theory of algorithms as Turing’s thesis. The theory of Turing machines provides a convenient working apparatus for many studies that require a precise definition of an algorithm. In particular, because of the naturalness of the steps executed by Turing machines, the machines have become the object of close attention in the theory of the complexity of algorithmic computations. In the course of the development of the theory of Turing machines, various generalizations of the machines have been considered, for example, Turing machines with a more general type of tape, machines with several tapes, and nondeterministic Turing machines.

REFERENCES

Kleene, S. C. Vvedenie v metamatematiku. Moscow, 1957. (Translated from English.)
Mendelson, E. Vvedenie v matematicheskuiu logiku. Moscow, 1971. (Translated from English.)

N. M. NAGORNYI

The Great Soviet Encyclopedia, 3rd Edition (1970-1979). © 2010 The Gale Group, Inc. All rights reserved.

Turing machine

[′tu̇r·iŋ mə‚shēn]
(computer science)
A mathematical idealization of a computing automation similar in some ways to real computing machines; used by mathematicians to define the concept of computability.
McGraw-Hill Dictionary of Scientific & Technical Terms, 6E, Copyright © 2003 by The McGraw-Hill Companies, Inc.

Turing Machine

(computability)
A hypothetical machine defined in 1935-6 by Alan Turing and used for computability theory proofs. It consists of an infinitely long "tape" with symbols (chosen from some finite set) written at regular intervals. A pointer marks the current position and the machine is in one of a finite set of "internal states". At each step the machine reads the symbol at the current position on the tape. For each combination of current state and symbol read, a program specifies the new state and either a symbol to write to the tape or a direction to move the pointer (left or right) or to halt.

In an alternative scheme, the machine writes a symbol to the tape *and* moves at each step. This can be encoded as a write state followed by a move state for the write-or-move machine. If the write-and-move machine is also given a distance to move then it can emulate an write-or-move program by using states with a distance of zero. A further variation is whether halting is an action like writing or moving or whether it is a special state.

Without loss of generality, the symbol set can be limited to just "0" and "1" and the machine can be restricted to start on the leftmost 1 of the leftmost string of 1s with strings of 1s being separated by a single 0. The tape may be infinite in one direction only, with the understanding that the machine will halt if it tries to move off the other end.

All computer instruction sets, high level languages and computer architectures, including parallel processors, can be shown to be equivalent to a Turing Machine and thus equivalent to each other in the sense that any problem that one can solve, any other can solve given sufficient time and memory.

Turing generalised the idea of the Turing Machine to a "Universal Turing Machine" which was programmed to read instructions, as well as data, off the tape, thus giving rise to the idea of a general-purpose programmable computing device. This idea still exists in modern computer design with low level microcode which directs the reading and decoding of higher level machine code instructions.

A busy beaver is one kind of Turing Machine program.

Dr. Hava Siegelmann of Technion reported in Science of 28 Apr 1995 that she has found a mathematically rigorous class of machines, based on ideas from chaos theory and neural networks, that are more powerful than Turing Machines. Sir Roger Penrose of Oxford University has argued that the brain can compute things that a Turing Machine cannot, which would mean that it would be impossible to create artificial intelligence. Dr. Siegelmann's work suggests that this is true only for conventional computers and may not cover neural networks.

See also Turing tar-pit, finite state machine.
This article is provided by FOLDOC - Free Online Dictionary of Computing (foldoc.org)

Turing machine

A mathematical model of computation. Named after English scientist Alan Turing, a Turing machine is a finite state machine that reads a tape divided into cells. The Turing machine examines the symbol in each cell and based on the machine's state and cell contents, changes the symbol or changes its state and moves the tape left or right. The machine does not follow instructions because the states and transitions are built into the machine for each problem to solve.

The Universal Turing Machine (UTM)
Turing also designed a machine known today as the "universal Turing machine." The UTM could simulate another Turing machine. The tape contained a description of another Turing machine and like today's computers could be programmed to perform any type of computation. See Turing test.
Copyright © 1981-2019 by The Computer Language Company Inc. All Rights reserved. THIS DEFINITION IS FOR PERSONAL USE ONLY. All other reproduction is strictly prohibited without permission from the publisher.
References in periodicals archive ?
The first step is to show how to construct a universal Turing machine, that is, a machine which, when given the standard description of any particular Turing machine, will mimic its behavior by producing the same outputs (pp.
As is described in the "Research Background" section, students could use three main heuristics for solving the questions of the exam: (a) constructing a Turing machine, (b) defining a reduction, and (c) using Rice theorem.
Acknowledging that there are deep issues involved,(10) standard practice in computability theory is to proceed on the assumption that the Church-Turing thesis is true, and to presume that results derived for Turing machines (or one of the other equivalent models of computation) apply to any realistic model of computation.
This computation can be carried out by a Turing machine, although explicitly writing such a machine would be a long boring exercise.
The hypothesis (aka Church's thesis) that the formal notion of computability by Turing machines corresponds to the intuitive notion of what is computable has been accepted as obviously true for 50 years.
As metioned above, the analysis is focused on execution time of evolutionary-estimated programming the Turing machine for solving sample problems implemented in Wolfram Mathematica and .NET Framework using F# programming language.
We use the halting problem of Turing machines on empty input as our undecidable problem.
Keywords: Alan Turing, Turing machine, Turing test, hypercomputing, computability, artificial intelligence
Alan Mathison Turing, the person who contributed immensely to the development of computer science by providing a formalization of the concepts of "algorithm" and "computation" with the "Turing Machine," which played a major role in the creation of the modern computer, died a tragic death in 1954 when he was 41.
To be precise, Simonsen (2006) has shown that there is no Turing machine which, given a decision algorithm for the language of some shift with decidable language, is able to compute the entropy of the shift with arbitrary precision.
The essays, inspired by a workshop on computable economics in Trento in October 2002, include such topics as complexity and information in modeling, the algorithmic and exchangeable aspects of induction, constructive and classical models for results in economics and game theory, the tools and concepts of computable economics, emergence and universal computation, research and development in computable production functions, examining computable knowledge and undecidability with a Turing machine metaphor applied to endogenous growth models, and rights and decentralized computation.
"Princeton mathematicians Alonzo Church and Alan Turing showed--roughly speaking--that any calculation involving bits and bytes can be done on an idealized computer known as a Turing machine....