Computing and Information Technology Interactive Digital Educational Library


Planet Math Computer Science  >
Planet Math Computer Science Collection >

Please use this identifier to cite or link to this item:

Title: Turing machine
Issue Date: 3-Mar-2005
Publisher: PlanetMath
Abstract: A ... Turing machine is an imaginary computing machine invented by Alan Turing to describe what it means to compute something. The ... of a Turing machine is a box with a tape and a tape head. The tape consists of an infinite number of cells stretching in both directions, with the tape head always located over exactly one of these cells. Each cell has one of a finite number of symbols written on it. The machine has a finite set of states, and with every move the machine can change states, change the symbol written on the current cell, and move one space left or right. The machine has a program which specifies each move based on the current state and the symbol under the current cell. The machine stops when it reaches a combination of state and symbol for which no move is defined. One state is the start state, which the machine is in at the beginning of a computation. A Turing machine may be viewed as computing either a partial function or a relation. When viewed as a function, the tape begins with a set of symbols which are the input, and when the machine halts, whatever is on the tape is the output. For instance it is not difficult to write a program which doubles a binary number, so input of ... (with
Appears in Collections:Planet Math Computer Science Collection

Files in This Item:

File SizeFormat

All items in DSpace are protected by copyright, with all rights reserved.


Valid XHTML 1.0! DSpace Software Copyright © 2002-2006 MIT and Hewlett-Packard - Feedback