|
The mathematical foundations of modern computer science began to be laid by Kurt Gödel with his incompleteness theorem (1931). In this theorem, he showed that there were limits to what could be proved and disproved within a formal system. This led to work by Gödel and others to define and describe these formal systems, including concepts such as mu-recursive functions and lambda-definable functions .[citation needed] 1936 was a key year for computer science. Alan Turing and Alonzo Church independently, and also together, introduced the formalization of an algorithm, with limits on what can be computed, and a "purely mechanical" model for computing .[citation needed] These topics are covered by what is now called the Church–Turing thesis, a hypothesis about the nature of mechanical calculation devices, such as electronic computers. The thesis claims that any calculation that is possible can be performed by an algorithm running on a computer, provided that sufficient time and storage space are available .[citation needed] In 1937, Alan Turing introduced his idea of what are now referred to as Turing Machines, and, anticipating the modern stored program computer, described what became known as the Universal Turing machine. These Turing machines were designed to formally determine, mathematically, what can be computed, taking into account limitations on computing ability. If a Turing machine can complete the task, it is considered Turing computable.[17] Turing machines are not physical objects, but mathematical ones. They show if and how any given algorithm can be computed. Turing machines are state machines, where a state represents a position in a graph. State machines use various states, or graph positions, to determine the outcome of the algorithm. To accomplish this, a theoretical one-dimensional tape is said to be divided into an infinite number of cells. Each cell contains a binary digit, 1 or 0. As the read/write head of the machine scans in the subsequent value in the cell, it uses this value to determine what state to transition to next. To accomplish this, the machine follows an input of rules, usually in the form of tables, that contain logic similar to: if the machine is in state A and a 0 is read in, the machine is going to go to the next state, say, state B. The rules that the machines must follow are considered the program. These Turing machines helped define the logic behind modern computer science. Memory in modern computers is represented by the infinite tape, and the bus of the machine is represented by the read/write head.[17] Turing focused heavily on designing a machine that could determine what can be computed. Turing concluded that as long as a Turing machine exists that could compute a precise approximation of the number, that value was computable. This does include constants such as pi. Furthermore, functions can be computable when determining TRUE or FALSE for any given parameters. One example of this would be a function “IsEven”. If this function were passed a number, the computation would produce TRUE if the number were even and FALSE if the number were odd. Using these specifications, Turing machines can determine if a function is computable and terminate if said function is computable. Furthermore, Turing machines can interpret logic operators, such as "AND, OR, XOR, NOT, and IF-THEN-ELSE"[17] to determine if a function is computable. Turing is so important to computer science that his name is also featured on the Turing Award and the Turing test. He contributed greatly to British code-breaking successes in the Second World War, and continued to design computers and software through the 1940s until his untimely death in 1954 .[citation needed] At a symposium on large-scale digital machinery in Cambridge, Turing said, "We are trying to build a machine to do all kinds of different things simply by programming rather than by the addition of extra apparatus" .[citation needed] In 1941, Konrad Zuse developed the world's first functional program-controlled computer, the Z3; in 1998, it was shown to be Turing-complete in principle.[18][19] Zuse was also noted for the S2 computing machine, considered the first process-controlled computer. He founded one of the earliest computer businesses in 1941, producing the Z4, which became the world's first commercial computer. In 1946, he designed the first high-level programming language, Plankalkül.[20] In 1969, Zuse suggested the concept of a computation-based universe in his book Rechnender Raum (Calculating Space) .[citation needed] In 1948, the first practical computer that could run stored programs, based on the Turing machine model, had been built - the Manchester Baby .[citation needed] In 1950, Britain's National Physical Laboratory completed Pilot ACE, a small scale programmable computer, based on Turing's philosophy .[citation needed] |
About us|Jobs|Help|Disclaimer|Advertising services|Contact us|Sign in|Website map|Search|
GMT+8, 2015-9-11 22:09 , Processed in 1.173157 second(s), 16 queries .
