How Complete Can a Computer be?

The idea of Turing completeness states that a computer should be able to simulate another and vice versa. This idea is closely related to lambda calculus. Originally Babbage’s analytical engine that he had envisioned could have technically been Turing complete. It was only later through the work of other great computer scientist like John von Neumann through the ENIAC and EDVAC did a theoretical physical manifestation of a Turing complete computer became a reality. To fully understand the concept though we need to dig through the history and the practicality of turing’s greatest creation.

To first get a complete idea on Turing completeness we need to focus on the machine that first envision the idea. The Turing machine was first envisioned by Alan Turing in  1936. He had described the machine as an “automatic” machine that could understand any algorithm. If anything the Turing machine in his mind was to only help fellow computer scientist with understanding the limits that a computer can have  with logical/mathematical computation. Turing gave  a full report of his discovery in 1948 in his groundbreaking essay Intelligent Machinery in which Turing described the machine like this: “…an unlimited memory capacity obtained in the form of an infinite tape marked out into squares, on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol and its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behaviour of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings.(Turing 1948, p. 61) A Turing machine is considered “universal” if said Turing machine can simulate and another Turing machine with that machines input.

So how does a Turing machine work. The physical manifestation of the Turing machine is just a device that writes either a 1 (for true) and a 0 (for false) on a length of theoretically infinite sums of tape. Overall the four necessary parts are: tape (obviously so that the computer has something to print the values on), the printing head (used to print the values on the tape), a state register, and a table or the instructions given to the Turing machine in order to carry out the algorithm that the programmer wants the machine to perform.

Does the universal Turing machine have any practicality to our day and age? The obvious answer is yes as it holds for all computer scientist a way to understand and adapt to the limits of computer logic to create something to help advance our society.

Sources:

http://en.wikipedia.org/wiki/Turing_machine

http://en.wikipedia.org/wiki/Universal_Turing_machine

Advertisements
  1. Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: