What is an Turing Machines?

Answer 1

The Turing Machine is a hypothetical computer used by Alan Turing in his paper "On Computable Numbers" in his proof of the "Halting Problem" to show that there are some set of problems that no computer can solve, even if it has infinite memory and infinite time.

The basic Turing Machine has a data memory composed of an infinitely long "tape" composed of "cells", each containing one symbol from a finite set of symbols. A "head" is positioned on one cell and can read its current symbol, write a new symbol, step forward/backward one cell. The control system contains a "program memory", a mechanism to remember which instruction in the program memory it is on, a mechanism to decode the symbol read from the current cell and select the corresponding sub-instruction of the current instruction to execute, a mechanism to decode that sub-instruction and instruct the head what new symbol to write then which direction to step, and either select which instruction to use next or halt if the problem is complete. Part of Turing's paper "On Computable Numbers" was another proof that showed that a Turing Machine is equivalent to any computer based on "finite state machines" that can ever be built. All modern computers are based on finite state machines, and thus have the same ultimate limits Turing showed his Turing machine to have.

No true Turing Machine has ever been built, because no infinite data memory can be built. Besides a real Turing Machine would always be slow.

Answer 2

Alan Turing visualized a "state machine" that was capable of basic computing. He never actually built his Turing Machine but people have paid homage to him by creating modern examples of the machine that he immagined. A state machine is a device which is controlled by the "current state" and a set of instructions which determines the "next state". In other words, a prototype for the computers of today.

Answer 3

A Turing Machine is theoretical device of significance in computer science. It has a tape which extends infinitely in both directions and a recording head which can read and write one symbol at a time on the tape. The number of symbols it can read and write is finite. The head can also move in either direction on the tape one step at a time. The machine also a finite set of rules and a memory. Each rule takes the current symbol on the tape in combination with what is in the memory and from that says what symbol should be written, what the new content of the memory should be, and which direction the head should move. The device is significant because it is believed that any problem which can be solved by any computer can also be solved by a Turing Machine. Thus, a Turing Machine is considered a sort of minimalist computer. Also, devices or computational systems which are believed to be capable of solving these generalized problems are said to be "Turing Complete".