Class Notes
(810,577)

Canada
(494,155)

York University
(33,691)

Natural Science
(2,769)

NATS 1700
(204)

Zbigniew Stachniak
(36)

Lecture

# lecture5.pdf

Unlock Document

York University

Natural Science

NATS 1700

Zbigniew Stachniak

Summer

Description

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,
http://ideonexus.com/2009/02/05/javascript-turing-machine.
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