Class Notes (810,577)
Canada (494,155)
York University (33,691)
Natural Science (2,769)
NATS 1700 (204)


29 Pages
Unlock Document

York University
Natural Science
NATS 1700
Zbigniew Stachniak

Lecture 5. The Dawn of Automatic Comput- ing Informal and unedited notes, not for distribution. (c) Z. Stachniak, 2011. Note: in the case when I was unable to nd the primary source of an image or determine whether or not an image is copyrighted, I have specied the source as unknown. I will provide full information about images and/or obtain reproduc- tion rights when such information is available to me. Introduction By the 1930s, mechanical and electromechanical calculators from Burroughs, Felt & Tarrant, Marchant, Monroe, Remington, Victor, and other manufac- turers had penetrated all aspects of a modern oce operations. It seemed that the mathematical tables could handle the rest in science and engineering. However, certain branches of science and engineering reached a calculat- ing barrier that prevented further progress unless an automated method of dealing with complex operations, such as solving linear equalities, dierential equations, etc. could be found. What was needed was a new type of a calculating machine that could per- form large-scale error-free calculations by following, in a mechanical way, a predened sequence of operations, that is, by following a program. The 1930s was a crucial period in the development of computing. Not only the rst designs of computers started to appear in Europe and the US but also a groundbreaking theoretical research on computing was initiated. In this lecture we shall take a look at the pioneering work on digital com- puters. We shall discuss the origins of the rst computers and their intended use. We shall talk about people and events leading to the rst designs and their impact on society and on the development of future computer industry. 1 Alan Turing on Computing Fig. 1. Alan Turing. Source: unknown. We begin with our discussion on computer pioneers with a portrait of Alan Turing who was not an engineer by training but a British mathematician, logician, and cryptanalyst whose contributions to the science of computing were not only large in scope but also groundbreaking. Turing is perhaps best known for his outstanding contributions to cryptog- raphy during the WWII when at Bletchley Parkthe wartime headquarters of the UK Government Code and Cypher Schoolhe (and others) worked successfully on breaking German ciphers. However, we shall concentrate on his work on the mathematics of computing that led him to the discovery one of the most powerful computing devices ever conceived. One can safely claim that the rst general-purpose and uni- versal computer ever devised was that created by Turing out of a few symbols written on a piece of paper. In honour of its inventor, that device is now called the Turing Machine. In spite of the fact that Turing did his groundbreaking research on ab- stract computing machines at a time when there were no real computers (he published his results in 1936-37), his work is considered among the most signicant contributions to the discipline of computing for this day. 2 The Hilbert Program To appreciate Turings contributions fully, we have to temporarily switch the focus of our narrative to another outstanding scientist David Hilbert, who was among the most inuential mathematicians in the rst decades of the 20th century. In 1928, Hilbert suggested that the entire mathematics could be mecha- nized. Speaking very(!) informally, according to Hilbert, the entire math- ematics could be done on some sort of an algorithm-following calculating machine and the job of a mathematician would be to discover the appropri- ate algorithms. Many mathematicians agreed with Hilbert but not all. In 1936, Turing published a paper On Computable Numbers, with an Application to the Entscheidungsproblem (Entscheidungsproblem in German means decision problem). In his paper, Turing demonstrated that, informally speaking, there are math- ematical problems that are unsolvable, that is, putting it dierently and in- formally, could not be solved in an algorithmic way as envisioned by Hilbert. We shall postpone a detailed analysis of Turings result until the next semester. For now, let us only mention that to prove his result Turing designed an ab- stract computer a simple mathematical concept but a powerful computing device sketched in Figure 2. Turing proved on paper that a computing ma- chine could perform very complex tasks but not all such tasks. 3 Fig. 2. A sketch of a Turing Machine. Source: Ryan Somma, At the time when Turing published his work, there were no computers. But when they started to appear and when the discipline of computer science was born, Turing machines had helped to dene and understand the notions fundamental to computing such as an algorithm, a computer, a computation and its complexity. The Turing Machine remains a fundamental concept of theoretical computer science a discipline that provides foundations for the entire discipline of computing. To honour Turings achievements, in 1966 the ACM established the A.M. Turing Award to recognize the most outstanding contributions to computer science. The award is recognized as the highest distinction in Computer Science (often referred to as Nobel Prize of computing). 4
More Less

Related notes for NATS 1700

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.