CT3620
VETENSKAPSMETODIK FÖR TEKNIKOMRÅDET
HISTORY OF IDEAS IN COMPUTING
Gordana Dodig-Crnkovic
Department of Computer Science and Engineering
Mälardalen University
2004
1
CDT403 Research Methodology in Natural Sciences and Engineering
A History of Computing:
A History of Ideas
Gordana Dodig-Crnkovic
Department of Computer Science and Electronic
Mälardalen University, Sweden
2
HISTORY OF COMPUTING
•
•
•
•
•
•
•
•
•
•
LEIBNIZ: LOGICAL CALCULUS
BOOLE: LOGIC AS ALGEBRA
FREGE: MATEMATICS AS LOGIC
CANTOR: INFINITY
HILBERT: PROGRAM FOR MATHEMATICS
GÖDEL: END OF HILBERTS PROGRAM
TURING: UNIVERSAL AUTOMATON
VON NEUMAN: COMPUTER
CONCEPT OF COMPUTING
FUTURE COMPUTING
3
4
Pieter BRUEGEL, the Elder
COMPUTING CURRICULA
5
Technological Advancement within
Computing over the Past Decade
– The World Wide Web and its applications
– Networking technologies, particularly those based on TCP/IP
– Graphics and multimedia
– Embedded systems
– Relational databases
– Interoperability
– Object-oriented programming
– The use of sophisticated application programmer interfaces (APIs)
– Human-computer interaction
– Software safety
– Security and cryptography
– …
6
Hackers & Painters
"Everything around us is turning into computers. Your
typewriter is gone, replaced by a computer. Your phone has
turned into one. So has your camera. Soon your TV will.
Your car has more processing power in it than a roomsized mainframe had in 1970. Letters, encyclopedias,
newspapers, and even your local store are being replaced
by the Internet. So if you want to understand where we are,
and where we're going, it will help if you understand
what's going on inside the heads of hackers.“
Paul Graham "Hackers & Painters"
7
Hackers & Painters
Hacking and painting have a lot in common. In fact, of all the
different types of people I’ve known, hackers and painters
are among the most alike.
Paul Graham "Hackers & Painters"
8
Yet there is a whole universe of people contributing to the
development of the field of computing rather different
from hackers and painters...
9
Computer Science
In practice, computer science includes a variety of topics
relating to computers, which range from the abstract
analysis of algorithms, formal grammars, etc. to more
concrete subjects like programming languages, software,
and computer hardware.
As a scientific discipline, it differs significantly from and is
often confused with mathematics, programming, software
engineering, and computer engineering, although there is
some degree of overlap with these and other fields.
http://en.wikipedia.org/wiki/Computer_science
10
Church-Turing Thesis
The Church-Turing thesis states that all known kinds of
reasonable paradigms of computation are essentially
equivalent in what they can do, although they vary in time
and space efficiency. The thesis is not a mathematical
theorem that can be proven, but an empirical observation
that all known computational schemes have the same
computational power.
Now the problem is what is the ”reasonable paradigm of
computation” – we will have reason to come back to this
point later on in this lecture.
11
Computer
Most research in computer science has been related to von
Neumann computers or Turing machines (computers that
do one small, deterministic task at a time). These models
resemble most real computers in use today. Computer
scientists also study other kinds of machines, some
practical (like parallel machines) and some theoretical (like
probabilistic, oracle, and quantum machines).
12
Computer Science
Computer scientists study what programs can and cannot do
(computability), how programs should efficiently perform
specific tasks (algorithms), how programs should store and
retrieve specific kinds of information (data structures and
data bases), how programs might behave intelligently
(artificial intelligence), and how programs and people
should communicate with each other (human-computer
interaction and user interfaces).
13
CS Body of Knowledge
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
Discrete Structures
Programming Fundamentals
Algorithms and Complexity
Programming Languages
Architecture and Organization
Operating Systems
Net-Centric Computing
Human-Computer Interaction
Graphics and Visual Computing
Intelligent Systems
Information Management
Software Engineering
Social and Professional Issues
Computational Science and Numerical Methods
...
14
Related Fields
Computer science is closely related to a number of fields.
These fields overlap considerably, though important
differences exist
• Information science is the study of data and information,
including how to interpret, analyze, store, and retrieve it.
Information science started as the foundation of scientific
analysis of communication and databases.
• Computer programming or software development is the act
of writing program code.
15
Related Fields
• Software engineering emphasizes analysis, design,
construction, and testing of useful software. Software
engineering includes development methodologies (such as
the waterfall model and extreme programming) and project
management.
• Information systems (IS) is the application of computing to
support the operations of an organization: operating,
installing, and maintaining the computers, software, and
data.
• Computer engineering is the analysis, design, and
construction of computer hardware
16
Related Fields
• Mathematics shares many techniques and topics with
computer science, but is more general. In some sense, CS
is the mathematics of computing.
• Logic is a formal system of reasoning, and studies
principles that lay at the very basis of computing/reasoning
machines, whether it be the hardware (digital logic) or
software (verification, AI etc.) levels. The subfield of logic
called computability logic provides a systematic answer to
the fundamental questions about what can be computed
and how. .
17
Related Fields
• Lexicography and specialized lexicography focus on the
study of lexicographic reference works and include the
study of electronic and Internet-based dictionaries.
• Linguistics is the study of languages, converging with
computer science in such areas as programming language
design and natural language processing.
18
Debate over Name
There is some debate over whether the name of the field
should be computer science or computation science or
computing. The first name is the original, traditional name;
however it implies that CS studies computers. The second
name is more recent, and it implies that CS studies what
we do with computers. The third is the most general term
including not only what we can do with present-day
computers but any computing process that any physical
system can perform.
19
Major Fields of Importance for CS
•
•
•
•
•
•
•
•
•
•
Mathematical foundations
Theoretical Computer Science
Hardware
Software
Data and Information Systems
Computing Methodologies
Computer Systems Organization
Computer applications
Computing Milieux
....
20
Mathematical Foundations
• Discrete mathematics (Boolean algebra, Graph theory,
Domain theory ..)
• Mathematical logic
• Probability and Statistics
• Information theory
• ...
21
Theoretical Computer Science
•
•
•
•
•
Algorithmic information theory
Computability theory
Cryptography
Formal semantics
Theory of computation (or theoretical computer science)
– analysis of algorithms and problem complexity
– logics and meanings of programs
– Mathematical logic and Formal languages
• Type theory
• ...
22
Hardware
•
•
•
•
•
•
Control structures and Microprogramming
Arithmetic and Logic structures
Memory structures
Input/output and Data communications
Logic Design
Integrated circuits
– VLSI design
• Performance and reliability
• ...
23
Software
• Computer programming (Programming techniques,
Program specification, Program verification)
• Software engineering
– Optimization
– Software metrics
– Software Configuration Management (SCM)
– Structured programming
– Object orientation
– Design patterns
– Documentation
• Programming languages
• Operating Systems
• Compilers
• ...
24
Computer Systems Organization
•
•
•
•
•
•
Computer architecture
Computer networks
Distributed computing
Performance of systems
Computer system implementation
...
25
Data and Information Systems
•
•
•
•
•
•
•
Data structures
Data storage representations
Data encryption
Data compression
Data recovery
Coding and Information theory
Files
– File formats
• Information systems
– Databases
– Information Storage and retrieval
– Information Interfaces and Presentation
• Data recovery
• .....
26
Computing Methodologies
•
•
•
•
•
•
•
•
•
Symbolic and Algebraic manipulation
Artificial intelligence
Computer graphics
Image processing and computer vision
Pattern recognition
Simulation and Modeling
Document and text processing
Digital signal processing
...
27
Computer Applications
• Administrative data processing
• Mathematical software (Numerical analysis, Automated
theorem proving, Computer algebra systems)
• Physical sciences and Engineering (Computational
chemistry, Computational physics)
• Life and medical sciences (Bioinformatics, Computational
Biology, Medical informatics)
• Social and behavioral sciences
• Arts and Humanities
• Computer-aided engineering
• Human-computer interaction (Speech synthesis, Usability
engineering)
• Robotics
28
• ....
Computing Aspects (Milieus)
•
•
•
•
•
•
•
Computer industry
Computers and education
Computers and society
Legal aspects of computing
Management of computing and Information systems
Personal computing
Computer and information security
29
Computing
• CS != Programming
• CS >> Programming
• Computing != CS
• Computing >> CS
30
Big ideas in Computer Science and Engineering
Prof. Gerry Sussman [MIT] said we could write down all the
ideas in computer science on 4 pages!
CS has added valuable knowledge to our understanding of the
world.
CS discipline offers some important concepts which it is
useful for everyone to understand. Just as there is a utility
for everyone to understand a certain amount of math and
science, there is a good reason for people to understand a
certain amount of computer science.
http://www.cs.caltech.edu/~andre/general/computer_science.html
31
Big ideas in Computer Science and Engineering
Hilbert’s program: Mechanical procedures exist for finding
the solutions to problems. That is, for many
questions/problems, we can write down a series of steps
and simple predicates which define precisely how to find
the correct solution. This process is completely
mechanical, not requiring any "human" judgment to
complete.
We can build physical machines which implement these
procedures and perform the calculations.
There are simple, universal models of computing which
capture the basic capabilities of these machines (e.g.
automata, pushdown automata, Turing Machines).
32
Big ideas in Computer Science and Engineering
The Turing Machine model is "robust" in the sense that
"reasonable" additions to it, or alternative formulations of
computing models have the same asymptotic power of
computability (Church's thesis).
“Reasonable" meaning they, for the most part, correspond to
things we imagine a real machine could support. In
particular, there are stronger models when the machine is
allowed to do "unreasonable" things like consult an oracle.
Deterministic/guaranteed procedures do not exist for all
problems (Halting Problem, uncomputability). An
important component of CS theory is to classify problems
as computable or uncomputable.
33
Big ideas in Computer Science and Engineering
Of the problems which are computable, tasks have different
computational difficulty (complexity). An important
component of CS theory allows us to analyze algorithms
and assess their complexity. (complexity classes
[P,NP,PSPACE, IP, ...], order analysis [O(), Omega(),
Theta()])
Common idioms/solution techniques, e.g.
– divide-and-conquer
– linear programming
– dynamic programming
– graph algorithms
34
Big ideas in Computer Science and Engineering
There are alternatives to directly solving hard problems
optimally. CS theory also tells us what we can give up in
the guarantee of solution quality to reduce computational
complexity.
– approximation algorithms
– online algorithms
– polynomial heuristic solutions
– randomized algorithms
35
Big ideas in Computer Science and Engineering
The desired computation can be captured precisely and
unambiguously. Computer science deals with how we
construct languages to describe computations, and how we
make them convenient for human use.
• languages
• syntax (grammars)
• semantics (denotational, operational)
36
Big ideas in Computer Science and Engineering
We do not have to emulate the user's description of a
computation to implement it correctly. We simply need to
implement a computation which gives the same visible
result (has the same meaning) as the user's computation
(compilation, CAD) which means semantic
transformations.
37
Big ideas in Computer Science and Engineering
The representation used for data in a computation can have a
big effect on efficiency of operation and ease of human
comprehension
• effects on computational and storage efficiency (e.g. arrays
and fixed structures vs. tagged lists, red-black trees; sparse
vs. dense representations of data)
• easing human comprehension (e.g. rich data structures)
38
Big ideas in Computer Science and Engineering
Our physical world allows us to build very large computer
systems. The practical limit to the useful size of a
computer system (or at least, the size of the function
efficiently supported by a computer system) is almost
always human comprehension, not the physical capacity
required. Consequently, a major concern of computer
science is techniques to manage and reduce complexity
(abstractions/information hiding, modularity, problem
decomposition, hierarchy, component isolation, invariants,
common idioms/paradigms for organization (e.g.
procedures, frames, streams, objects, APIs, servers)
39
Big ideas in Computer Science and Engineering
• A computing machine can be implemented out of X.
• X=mechanical interactions, relays, tubes, transistors, DNA,
molecules...
• common/useful abstractions (e.g. digital abstraction, flops,
memory, communication channels)
• disciplines achieving correctness in the face of
noise/uncertainty (e.g. voltage levels, timing models and
disciplines)
40
Big ideas in Computer Science and Engineering
We can extend our notion of abstraction/information hiding to
machine design. In particular, the machine code and
operating environment for a machine represents the
abstract interface it provides to the outside world. Any
implementation which provides the same semantics to the
machine code is viable.
Consequently, we have the notion of ISAs or architecture
families which all run the same machine code but which
admit to a variety of implementations (e.g. IBM 360, VAX,
MIPS, SPARC, x86).
41
Big ideas in Computer Science and Engineering
Machine code is just another language specifying precisely
the computation to be performed.
– a computational engine need only provide the intended
semantics, leaving it plenty of freedom as to how it
implements the semantics.
– like any other language, it can be translated from the
input format to another native format (perhaps another
machine's native machine format) as long as it provides
the original semantics (e.g. softPC, binary translation)
42
Big ideas in Computer Science and Engineering
The engineering side of computer science is about: How do
we minimize the resources we use in order to perform a
computation (set of computations). Physical machines have
finite/limited real resources so time, energy, area
(hardware: memory, wires)… must be minimized.
43
Big ideas in Computer Science and Engineering
We can provide the abstraction of more physical resources by
virtualizing the physical resources. That is, sharing the
physical resource among multiple uses over time. To
accomplish this, we store the state of a particular usage of
the physical resources in cheaper storage, e.g. virtual
memory, virtual channels, multitasking, time-sharing
44
Big ideas in Computer Science and Engineering
Computations occur at different time scales (rates). To
minimize work, when possible, hoist a computation out of
a high rate region into a slower region. A trivial example:
loop invariants/hoisting.
45
Big ideas in Computer Science and Engineering
Feedback is the key to diagnosing discrepancies between
one's model of the world and reality. This is really just the
heart of the scientific method. It should be used by
developers to improve programs (debug functional
problems, identify and improve performance problems).
Moreover, it can be embedded in programs so that they
adapt to their data and environment.
46
Big ideas in Computer Science and Engineering
A data structure or computation can either be dynamic or
static.
• Static structures and computations can be very efficient
when the size and shape of the computation is constant or
has little variance.
• Dynamic structures/computations are necessary when the
size or scope of the problem is unbounded. They cost more
per element or item, but they only have to be as large (as
complex) as a particular problem instance.
47
Big Ideas of Engineering
There are many big ideas in engineering, e.g.
• iterative design
• real-world constraints
• tradeoffs
• feedback
• complexity management techniques
that are important for understanding not only classical
engineered systems but also for understanding social
systems and the natural world.
48
History of Ideas of Computer Science
•
•
•
•
•
•
•
•
LEIBNIZ: LOGICAL CALCULUS
BOOLE: LOGIC AS ALGEBRA
FREGE: MATEMATICS AS LOGIC
CANTOR: INFINITY
HILBERT: PROGRAM FOR MATHEMATICS
GÖDEL: END OF HILBERTS PROGRAM
TURING: UNIVERSAL AUTOMATON
VON NEUMAN: COMPUTER
http://web.clas.ufl.edu/users/rhatch/pages/10-HisSci/links/ H I S T O R Y O F S C I E N C E
LINKS
49
C u ltu re
L o g ic
(R elig io n , A rt, … )
5
&
M a th em a tics
1
CS
N atu ral S cien ces
(P hy sics,
C h em istry ,
B iology , … )
2
S ocial S cien ces
(E co n o m ics, S o ciolo g y, A n th ro p o lo g y, … )
3
T h e H u m an ities
(P hilo so p h y, H isto ry, L in g u istics … )
4
The whole is more than the sum of its parts. Aristotle, Metaphysica
21
50
Leibniz: Logical Calculus
Gottfried Wilhelm von Leibniz
Born: 1 July 1646 in Leipzig, Saxony (now Germany)
Died: 14 Nov 1716 in Hannover, Hanover (now Germany)
51
Leibniz´s Calculating Machine
“For it is unworthy of excellent men to lose hours like slaves in
the labor of calculation which could safely be relegated to
anyone else if the machine were used.”
52
Leibniz´s Logical Calculus
DEFINITION 3. A is in L, or L contains A, is the same as to say that L can be
made to coincide with a plurality of terms taken together of which A is one.
B  N = L signifies that B is in L and that B and N together compose or
constitute L. The same thing holds for larger number of terms.
AXIOM 1.
B  N = N  B.
POSTULATE.
Any plurality of terms, as A and B, can be added to compose
A  B.
AXIOM 2.
A  A = A.
PROPOSITION 5. If A is in B and A = C, then C is in B.
PROPOSITION 6. If C is in B and A = B, then C is in A.
PROPOSITION 7. A is in A.
(For A is in A  A (by Definition 3). Therefore (by Proposition 6) A is in A.)
….
PROPOSITION 20. If A is in M and B is in N, then A  B is in M  N.
53
Boole: Logic as Algebra
George Boole
Born: 2 Nov 1815 in Lincoln, Lincolnshire, England
Died: 8 Dec 1864 in Ballintemple, County Cork, Ireland
54
George Boole is famous because he showed that rules used
in the algebra of numbers could also be applied to logic.
• This logic algebra, called Boolean algebra, has many
properties which are similar to "regular" algebra.
• These rules can help us to reduce an expression to an
equivalent expression that has fewer operators.
55
Properties of Boolean Operations
A AND B  A  B
A OR B  A + B
56
Frege: Matematics as Logic
Friedrich Ludwig Gottlob Frege
Born: 8 Nov 1848 in Wismar, Mecklenburg-Schwerin (now Germany)
Died: 26 July 1925 in Bad Kleinen, Germany
57
The Predicate Calculus (1)
•
•
In an attempt to realize Leibniz’s ideas for a language of
thought and a rational calculus, Frege developed a formal
notation (Begriffsschrift).
He has developed the first predicate calculus: a formal
system with two components: a formal language and a
logic.
58
The Predicate Calculus (2)
The formal language Frege designed was capable of expressing:
– predicational statements of the form
‘x falls under the concept F’ and ‘x bears relation R to y’, etc.,
– complex statements such as
‘it is not the case that ...’ and ‘if ... then ...’, and
– ‘quantified’ statements of the form
‘Some x is such that ...x...’ and
‘Every x is such that ...x...’.
59
The Analysis of Atomic Sentences and
Quantifier Phrases
Fred loves Annie.
Therefore, some x is such that x loves Annie.
Fred loves Annie.
Therefore, some x is such that Fred loves x.
Both inferences are instances of a single valid inference rule.
60
Proof
As part of his predicate calculus, Frege developed a strict
definition of a ‘proof’.
In essence, he defined a proof to be any finite sequence of
well-formed statements such that each statement in the
sequence either is an axiom or follows from previous
members by a valid rule of inference.
61
Cantor: Infinity
Georg Ferdinand Ludwig Philipp Cantor
Born: 3 March 1845 in St Petersburg, Russia
Died: 6 Jan 1918 in Halle, Germany
62
Infinities
Set of integers has an equal number of members as the set
of even numbers, squares, cubes, and roots to equations!
The number of points in a line segment is equal to the
number of points in an infinite line, a plane and all
mathematical space!
The number of transcendental numbers, values such as 
and e that can never be the solution to any algebraic
equation, were much larger than the number of integers.
63
Hilbert described Cantor's work as:- ´...the finest product
of mathematical genius and one of the supreme
achievements of purely intellectual human activity.´
64
Hilbert: Program for Mathematics
David Hilbert
Born: 23 Jan 1862 in Königsberg, Prussia (now Kaliningrad, Russia)
Died: 14 Feb 1943 in Göttingen, Germany
65
Hilbert's program
Provide a single formal system of computation capable of
generating all of the true assertions of mathematics from
“first principles” (first order logic and elementary set
theory).
Prove mathematically that this system is consistent, that is,
that it contains no contradiction. This is essentially a proof
of correctness.
If successful, all mathematical questions could be
established by mechanical computation!
66
Gödel: End of Hilberts Program
Kurt Gödel
Born: 28 April 1906 in Brünn, Austria-Hungary (now Brno, Czech Republic)
Died: 14 Jan 1978 in Princeton, New Jersey, USA
67
Incompleteness Theorems
1931 Über formal unentscheidbare Sätze der Principia
Mathematica und verwandter Systeme.
In any axiomatic mathematical system there are
propositions that cannot be proved or disproved within the
axioms of the system.
In particular the consistency of the axioms cannot be
proved.
68
Turing: Universal Automaton
Alan Mathison Turing
Born: 23 June 1912 in London, England
Died: 7 June 1954 in Wilmslow, Cheshire, England
69
When war was declared in 1939 Turing moved to work
full-time at the Government Code and Cypher School at
Bletchley Park.
Together with another mathematician W G Welchman,
Turing developed the Bombe, a machine based on earlier
work by Polish mathematicians, which from late 1940 was
decoding all messages sent by the Enigma machines of the
Luftwaffe.
70
At the end of the war Turing was invited by the National
Physical Laboratory in London to design a computer.
His report proposing the Automatic Computing Engine
(ACE) was submitted in March 1946.
Turing returned to Cambridge for the academic year 194748 where his interests ranged over topics far removed from
computers or mathematics, in particular he studied
neurology and physiology.
71
1948 Newman (professor of mathematics at the University
of Manchester) offered Turing a readership there.
Work was beginning on the construction of a computing
machine by F C Williams and T Kilburn. The expectation
was that Turing would lead the mathematical side of the
work, and for a few years he continued to work, first on the
design of the subroutines out of which the larger programs
for such a machine are built, and then, as this kind of work
became standardized, on more general problems of
numerical analysis.
72
1950 Turing published Computing machinery and intelligence
in Mind
1951 elected a Fellow of the Royal Society of London mainly
for his work on Turing machines
by 1951 working on the application of mathematical theory to
biological forms.
1952 he published the first part of his theoretical study of
morphogenesis, the development of pattern and form in
living organisms.
73
Von Neuman: Computer
John von Neumann
Born: 28 Dec 1903 in Budapest, Hungary
Died: 8 Feb 1957 in Washington D.C., USA
74
In the middle 30's, Neumann was fascinated by the
problem of hydrodynamical turbulence.
The phenomena described by non-linear differential
equations are baffling analytically and defy even
qualitative insight by present methods.
Numerical work seemed to him the most promising way to
obtain a feeling for the behaviour of such systems. This
impelled him to study new possibilities of computation on
electronic machines ...
75
Von Neumann was one of the pioneers of computer science
making significant contributions to the development of
logical design. Working in automata theory was a synthesis
of his early interest in logic and proof theory and his later
work, during World War II and after, on large scale
electronic computers.
Involving a mixture of pure and applied mathematics as
well as other sciences, automata theory was an ideal field
for von Neumann's wide-ranging intellect. He brought to it
many new insights and opened up at least two new
directions of research.
76
He advanced the theory of cellular automata,
advocated the adoption of the bit as a measurement of
computer memory, and
solved problems in obtaining reliable answers from
unreliable computer components.
77
Computer Science Hall of Fame
Charles Babbage
Julia Robinson
Ada Countess of Lovelace
Noam Chomsky
Axel Thue
Juris Hartmanis
Stephen Kleene
John Brzozowski
78
Computer Science Hall of Fame
Richard Karp
Stephen Cook
Donald Knuth
Sheila Greibach
Manuel Blum
Leonid Levin
79
Women in Computer History
•
•
•
•
•
•
•
•
•
•
•
•
Ada Byron King, Countess of Lovelace (1815-1852)
Edith Clarke (1883-1959)
Rósa Péter (1905-1977)
Grace Murray Hopper (1906-1992)
Alexandra Illmer Forsythe (1918-1980)
Evelyn Boyd Granville
Margaret R. Fox
Erna Schneider Hoover
Kay McNulty Mauchly Antonelli
Alice Burks
Adele Goldstine
Joan Margaret Winters
80
Ada Byron King,
Countess of Lovelace
(1815-1852)
Ada heard in November, 1834, Babbage's ideas for a new
calculating engine, the Analytical Engine. Ada was touched by
the "universality of Babbages ideas". Hardly anyone else was.
In her article, published in 1843, Lady Lovelace's far-sighted
comments included her predictions that such a machine might
be used to compose complex music, to produce graphics, and
would be used for both practical and scientific use.
Ada suggested to Babbage writing a plan for how the engine
might calculate Bernoulli numbers. This plan, is now regarded
as the first "computer program." A software language was
named "Ada" in her honor in 1979.
81
Edith Clarke
(1883-1959)
Edith Clarke is well-known in the field of
Power Engineering. Her main contribution
to the field was the development of tables
that speeded up calculations for engineers.
This was especially important because she
created them during World War I, when
engineers desperately needed to work
faster.
82
Rósa Péter
(1905-1977)
Her first research topic was number theory, but she
became discouraged on finding that her results had
already been proved by Dickson.
For a while Rósa wrote poetry, but around 1930 she was
encouraged to return to mathematics by Kalmár. He
suggested Rósa examine Gödel's work, and in a series of
papers she became a founder of recursive function theory.
Rósa wrote Recursive Functions in 1951, which was the
first book on the topic and became a standard reference.
In 1952 Kleene described Rósa Péter in a paper in Bull.
Amer. Math. Soc. as ``the leading contributor to the
special theory of recursive functions."
From the mid 1950's she applied recursive function theory
to computers. In 1976 her last book was on this topic:
Recursive Functions in Computer Theory.
83
ENIAC Ladies
84
Erna Schneider Hoover
Invention: Computerized Telephone Switching System
Erna Schneider earned a B.A. with honors in medieval history
from Wellesley College, and later a Ph.D. in the philosophy and
foundations of mathematics from Yale University.
In 1954, after teaching for a number of years at Swarthmore
College, she began a research career at Bell Laboratories.
While there, she invented a computerized switching system for
telephone traffic, to replace existing hard-wired, mechanical
switching equipment. For this ground-breaking achievement -the principles of which are still used today -- she was awarded
one of the first software patents ever issued (Patent #3,623,007,
Nov. 23, 1971) . At Bell Labs, she became the first female
supervisor of a technical department.
85
Grace Murray Hopper
(1906-1992)
Grace Murray Hopper: Inventor of
the Computer Compiler
She participated in the
development of the Common
Business-Oriented Language
(COBOL; 1959-61) for the
UNIVAC
The very first computer bug:
Grace Murray Hopper
originated this term when she
found a real bug in a computer
86
Ida Rhodes
(1900 -1986)
She designed the C-10 language in the early 1950
for the UNIVAC.
She also designed the original computer used for
the Social Security Administration.
In 1949, the department of Commerce awarded her
an exceptional Service Gold Medal for
significant pioneering leadership and
outstanding contributions to the scientific
progress of the nation.
87
Evelyn Boyd Granville
Evelyn Boyd Granville - was one of the first
African American women to earn a Ph.D. in
Mathematics.
She became a specialist in rocket and missile
fuses, orbit computations and trajectory
calculations for national defense and the space
program providing technical support for the
Vanguard, Mercury and Apollo projects. In
addition, she served as an educational
consultant to the State of California, helping to
improve the teaching of math in elementary
and secondary schools.
88
Jean E. Sammet
She initiated the concept and directed the
development of the first FORMAC (FORmula
MAnipulation Compiler). FORMAC was the
first widely used general language. It was also
the first system for manipulating nonnumeric
algebraic expressions.
In 1965, she became programming language
technology manager in the IBM Systems
Development Division. Afterward, she wrote a
book on programming languages.
Her book, Programming Languages: History and
Fundamentals, was published by Prentice-Hall
in 1969.
89
Dr. Thelma Estrin
Professor Emerita
Now retired from University of California, Los Angeles, where
she was a computer science professor, Estrin was a pioneer
in the field of biomedical engineering who realized that
some of the most important ideas in science did not fit
neatly into separate fields. Her work would combine
concepts from anatomy, physiology, and neuroscience with
electronic technology and electrical engineering. She was
one of the first to use computer technology to solve
problems in health care and in medical research.
Estrin designed and then implemented the first system for
analog-digital conversion of electrical activity from the
nervous system," a precursor to the use of computers in
medicine. She published papers on how to map the brain
with the help of computers, and long before the Internet
became popular and easy to use, she designed a computer
network between UCLA and UC Davis in 1975.
90
Dana Angluin
B.A., Ph.D. University of California at Berkeley, 1969,
1976, Joined Yale Faculty 1979
Algorithmic models of learning
Professor Angluin’s thesis was among the first work to
apply complexity theory to the field of inductive
inference.
Her work on learning from positive data reversed a
previous dismissal of that topic, and established a
flourishing line of research. Her work on learning
with queries established the models and the
foundational results for learning with membership
queries. Recently, her work has focused on the areas
of coping with errors in the answers to queries, maplearning by mobile robots, and fundamental questions
in modeling the interaction of a teacher and a learner.
91
Nancy A. Lynch
Professor of Electrical Engineering and Computer
Science, Massachusetts Institute of Technology.
Nancy Lynch heads the Theory of Distributed Systems
Group (TDS) research group in MIT's Laboratory for
Computer Science. This group is part of the Theory of
Computation (TOC) group and also of the Principles of
Computer Systems (POCS) group.
Teaching - Spring 2001: 6.897 Modeling and Analyzing
Really Complicated Systems, Using State Machines
Fall 2001 6.852 Distributed Algorithms
Research interests:
distributed computing, real-time computing, algorithms,
lower bounds, formal modelling and verification.
92
Adele E. Goldberg
Adele Goldberg received her Ph.D. from the
University of California at Berkeley in 1992. She
is an associate professor in the UIUC
Department of Linguistics and a part-time
Beckman Institute faculty member in the
Cognitive Science Group. Her fields of
professional interest are syntax/semantics,
constructional approaches to grammar, lexical
semantics, language acquisition, language
processing, and categorization.
93
Sandra L. Kurtzig
In today's male-dominated software industry, women
founders and CEOs (chief executive officers) are
practically nonexistent. But while software titans like
Bill Gates and Oracle's Larry Ellison have become the
poster boys for Silicon Valley success, the first
multimillion-dollar software entrepreneur was a
woman.
Starting with just $2,000, Sandra Kurtzig built a
software empire that, at its peak, boasted around $450
million in annual sales. And it all started as a part-time
job.
94
International Difference in Percentage of
Female Students within Informatics 2001
Country
England
Italy, France, Spain, Portugal
Former Sowjetunion
Bulgaria
%Women
35
40 50
50
60-70
Grece
59
India, Malaysia, Singapure
50
Germany
8
Olga Goldmann, Seminar: Geschichte der Informatik
http://www.millo.de/virtosphere/schillo/teaching/WS2001/Vortraege/Frauen.ppt
95
Philosophical Problems of Computing
Fleming's original thermionic valve, 1889.
Science Museum London
96
Babbage's Difference Engine No 1, 1832.
Front detail.
Science Museum London
97
The 'Bombe' code-breaking
machine, 1943 at Bletchley Park
in Bedfordshire, the British
forces' intelligence centre during
WWII.
The cryptographers at Bletchley
Park deciphered top- secret
military communiques between
Hitler and his armed forces.
These communiques were
encrypted in the 'Enigma' code
which the Germans considered
unbreakable.
However, the codebreakers at
Bletchley cracked the code with
the help of the Bombe machine.
98
Code-breaking personnel at
Bletchley Park, 1943.
This shows one of the Hut 3 priority
teams at Bletchley Park, in which
civilian and service personnel worked
together at code- breaking.
99
Wrens* operating the
'Colossus' computer, 1943.
Colossus was the world's first
electronic programmable
computer, at Bletchley Park
in Bedfordshire.
* Women's Royal Naval Service
100
The computer presents itself as a culturally defining technology
and has become a symbol of the new millennium, playing a
cultural role far more influential than the mills in the Middle
Ages, mechanical clocks in the seventeenth century, or the
steam engine in the age of the industrial revolution.
(Bolter 1984)
101
“The important difference is that the computer (the physical
object that is directly related to the theory) is not a focus of
investigation (not even it he sense of being the cause of
certain algorithm proceeding in certain way) but it is rather
theory materialized, a tool always capable of changing in
order to accommodate even more powerful theoretical
concepts. ”
Scientific Methods in Computer Science, GDC
102
Philosophy of Computing
or
Philosophy of Information?
DICHOTOMY
INFORMATION – COMPUTATION
SUBSTANTIVE - VERB
DATA STRUCTURE – FUNCTION/ALGORITHM
PARTICLE – FORCE (FIELD)
Instructive analogy from physics: ATOMISM
PARTICLES are considered as the primary principle.
FIELDS/INTERACTIONS are defined in terms of particles, particle
exchange.
103
What Is Information?
Luciano Floridi
There is no consensus yet on the definition of semantic information.
The Standard Definition of declarative, objective and semantic Information
(SDI):
information = meaningful data
Floridis main thesis is that meaningful and well-formed data constitute
information only if they also qualify as contingently truthful.
Now the problem is to interpret what contingently truthful means in this
context.
"The contingent, roughly speaking, is what has the ground of its being not in itself but in somewhat else. Such is the aspect under
which actuality first comes before consciousness . . . But the contingent is only one side of the actual . . . . It is the actual, in
the signification of something merely possible. Accordingly we consider the contingent to be what may or may not be, what
may be in one way or another, whose being or not-being, and whose being on this wise or otherwise, depends not upon itself
but on something else. To overcome this contingency is . . .the problem of science . . . ." Logic, § 145 Note.
www.class.uidaho.edu/mickelsen/texts/Hegel%20Glossary.htm
104
The Philosophy of Information (PI)
A new philosophical discipline, concerned with
a) the critical investigation of the conceptual nature and basic
principles of information, including its dynamics (especially
computation and flow), utilisation and sciences; and
b) the elaboration and application of information-theoretic and
computational methodologies to philosophical problems.
L. Floridi
"What is the Philosophy of Information?", Metaphilosophy, 2002
http://www.wolfson.ox.ac.uk/~floridi/papers.htm
105
What is Computation?
Brian Cantwell Smith
106
The Age of Significance
Volume I • Introduction
Brian Cantwell Smith
107
Construals of Computation
1. Formal symbol manipulation (FSM): the idea,
derivative from a century’s work in formal logic and
metamathematics, of a machine manipulating (at least
potentially) symbolic or meaningful expressions
without regard to their interpretation´or semantic
content;
2. Calculation of a function (FUN): behavior that, when
given as input an argument to a (typically
mathematical) function, produces as output the value of
that function on that argument.
3. Effective computability (EC): what can be done—and
how hard it is to do it—mechanically, as it were, by, an
abstract analogue of a “mere machine”;
108
4. Rule-following
or algorithm execution (RF): what is
involved, and what behaviour is thereby produced, in
following a set of rules or instructions, such as when cooking
dessert;
5. Digital state machines (DSM): the idea of an automaton with
a finite, disjoint set of internally homogeneous states—as
parodied in the “clunk, clunk, clunk” gait of a 1950’s cartoon
robot;
6. Information processing (IP): what is involved in storing,
manipulating, displaying, and otherwise trafficking in
“information,” whatever information might be; and
7. Physical symbol systems (PSS): the idea, made famous by
Newell and Simon, that, somehow or other, computers interact
with and perhaps are also made of symbols in a way that
depends on their mutual physical embodiment.
109
Church-Turing Thesis*
*Source:
Stanford Encyclopaedia of Philosophy (B. Jack Copeland)
110
A Turing machine is an abstract representation
of a computing device.
It is more like a computer program (software)
than a computer (hardware).
111
LCMs [logical computing machines:
Turing’s expression for Turing machines]
were first proposed by Alan Turing,
in an attempt to give a mathematically precise definition
of "algorithm" or "mechanical procedure".
112
Effective Computability
The Church-Turing thesis
concerns an
effective or mechanical method
in logic and mathematics.
113
A method M is called ‘effective’ or ‘mechanical’ iff:
1.
M is set out in terms of a finite number of exact instructions
(each instruction being expressed by means of a finite number
of symbols);
2.
M will, if carried out without error, always produce the desired
result in a finite number of steps;
3. M can (in principle) be carried out by a human being unaided
by any machinery save paper and pencil;
4.
M demands no insight or ingenuity on the part of the human
being carrying it out.
114
Misunderstandings of the Turing Thesis
Turing did not show that his machines can solve any problem
that can be solved "by instructions, explicitly stated rules,
or procedures" and nor did he prove that a universal Turing
machine "can compute any function that any computer,
with any architecture, can compute".
115
Turing proved that his universal machine can compute any
function that any Turing machine can compute; and he
put forward, and advanced philosophical arguments in
support of, the thesis here called Turing’s thesis.
116
Turing introduces his machines as an idealised description of
a certain human activity, the tedious one of numerical
computation, which until the advent of automatic
computing machines was the occupation of many
thousands of people in commerce, government, and
research establishments.
117
Turing’s "Machines". These machines are humans who
calculate.
(Wittgenstein)
A man provided with paper, pencil, and rubber, and subject to
strict discipline, is in effect a universal machine. (Turing)
118
A thesis concerning the extent of effective methods procedures that a human being unaided by machinery is
capable of carrying out - has no implication concerning the
extent of the procedures that machines are capable of
carrying out, even machines acting in accordance with
‘explicitly stated rules’.
119
Among a machine’s repertoire of atomic operations there may
be those that no human being unaided by machinery can
perform.
120
Two Most Fundamental Functions
SEARCH (identify objects = divide universe in parts)
SORT (organize: what is the same, what is different)
121
Repetition, Similarity
As repetition is based upon similarity, it must be relative. Two
things that are similar are always similar in certain respects.
122
Repetition, Similarity
Searching for similarity and differences leads to
classifications i.e. the division of objects or events in
different groups/classes.
The simplest tool by for classification is the binary opposition
or dichotomy (dualism). When we use dichotomy, we only
decide if an object is of kind A or of kind A. Examples of
frequent dichotomies are yes/no, true/false, before/after,
more/less, above/below, etc.
123
Identity
The basic feature of experimental method is its
reproducibility:
It must be possible to establish essentially the same
experimental situation in order to obtain the same results.
This means that the experimental arrangement can be made
with essentially equivalent parts.
What we call “essentially equivalent” (or we can call it
“essentially the same”) depends on situation. Even here the
principle of information hiding helps us to get a practical
“level of resolution” which means information hiding for
all objects below that level.
124
Identity
Declaring two systems/particles/states as identical is entirely
the matter of focus.
For example if we focus on question of how many people in
this country are vegetarians, we just treat all people as
equal units.
If on the other hand we want to know how many women in
this country are vegetarian, we discriminate between men
and women in our analysis of people, so they are no longer
identical.
125
Identity
Declaring two systems/particles/states as identical is entirely the
matter of focus.
126
Identity
We can e.g. assume that bacteria of particular sort are
interchangeable (indistinguishable) in certain context.
That enables us to make repeated experiments with different
agents and to treat all bacteria of the same type as equal.
It does not mean that they are identical in the absolute sense. It
only means that for our purpose the existing difference does
not have any significance.
127
Identity
Example of ancient atomic theory. The problem of showing
that one single physical body- say piece of iron is
composed of atoms is at least as difficult as of showing
that all swans are white. Our assertions go in both cases
beyond all observational experience.
The difficulty with these structural theories is not only to
establish the universality of the law from repeated
instances as to establish that the law holds even for one
single instance.
128
Identity
A singular statement like “This swan here is white” may be
said to be based on observation. Yet it goes beyond
experience- not only because of the word “white”, but
because of the word “swan”.
For by calling something a “swan”, we attribute to it
properties which go far beyond mere observation. So even
the most ordinary singular statements are always the
interpretations of the facts in the light of theories!
129
Classification (1)
– A relation is an equivalence relation if it is
reflexive, symmetric and transitive.
– An example of such is equality on a set.
130
Classification (2)
CLASSES SHOULD BE DISJUNCT ...
class2
class 1:
positive effect
class 2:
negative effect
class1
class 3: no effect
class3
Universe here is a group of
patients who test a new
medicine.
... AND CHOSEN ACCORDING TO SAME CRITERIA ...
131
Classification (3)
Jorge Luis Borges,
"The Analytical Language of John Wilkins“
(Incongruity)
Borges's fictive encyclopedia divides animals into:
(a)
those that belong to the Emperor,
(b)
embalmed ones,
(c)
those that are trained,
(d)
suckling pigs,
(e)
mermaids,
(f)
fabulous ones,
(g)
stray dogs,
(h)
those that tremble as if they were
mad,
(i) those that resemble flies from a
distance
(j) those drawn with a very fine camel's
hair brush,
(k) innumerable ones,
(l) others,
(m) those that have just broken a flower
vase
132
Relations to Natural Philosophers Paradigm
Konrad von Megenberg.
Buch der Natur (Augsburg, 1481).
A medieval Latin compendium of
science translated into German in
the fourteenth century and was first
printed in Augsburg in 1475.
(Lessing J. Rosenwald Collection),
Lobrary of Congress
133
Universe As An Assemblage Of Natural Objects
Rudolf II, patron of Kepler and
briefly Brahe was fascinated by
alchemy, astrology, and other
ways in which human art
interfered in or perfected nature.
Here one of his court painters
has, through art, depicted Rudolf
as an assemblage of natural
objects: fruits, vegetables,
grains, and flowers.
Galileo referred contemptuously
to such portraits in his Dialogue
on Two Chief World Systems.
134
Universe As An Assemblage Of Natural Objects
What properties must a
system have to be living?
Can we make a clear
distinction between living
and nonliving systems?
What is connection between
self-organization and life?
Two genetically engineered mice, 1988.
These male mice are direct descendants of the first
transgenic mammals to be granted a US patent. This
strain was patented by Harvard University.
Science Museum London
135
Philosophy Of Science – A New Paradigm
It is time again to direct gaze upward and see Nature as a whole.
What have we learned last couple of centuries of scientific
specialisation and division to ever smaller fields?
Field of computing seems to be the best candidate to replace
physics as paradigmatic mirror of Philosophy of Science used
to reflect the Universe that matters.
This time Universe has to include human, and not only as a
machine!
Unifying concept of information has even the potential to bring
together Sciences and Humanities. New Natural Philosophy?
136
137
A New Kind of Science
Stephen Wolfram
138
Santiago Theory - Autopoiesis
”Living systems are cognitive systems, and living as a
process is a process of cognition. This statement is valid
for all organisms, with and without a nervous system.”
Maturana Humberto, Biology of Cognition, 1970
139
INFORMATION
COMPUTATION
COGNITION
140
Evolutionary Biological Paradigm
The most developed forms of computational systems:
Evolutive self-organizing self-sustaining complex systems
built of metabolic/computational units
141
142
Pieter BRUEGEL, the Elder
NA-CAP 2006 @ RPI, Troy, NY, USA
North American Computing and Philosophy
Conference, August 10-12, 2006
Swedish National Course in Philosophy
of Computer Science
Gordana Dodig-Crnkovic
Mälardalen University
Department of Computer Science and
Electronics
http://www.idt.mdh.se/personal/gdc/
143
PHILOSOPHY
OF COMPUTER SCIENCE
CD5650
COURSE OUTLINE
http://www.idt.mdh.se/personal/gdc/pi-network.htm
http://www.idt.mdh.se/personal/gdc/PI_04/index.html
Gordana Dodig-Crnkovic
Department of Computer Science and Engineering
Mälardalen University, 23 January 2004
144
Interdisciplinary Distance Learning
in Computing and Philosophy
North American Computers and Philosophy Conference
July 26-28, 2007
NA-CAP @ Loyola University Chicago
Gordana Dodig-Crnkovic
http://www.idt.mdh.se/personal/gdc/
Department of Computer Science and Engineering
Mälardalen University, Sweden
145
BASED ON
Increasing Interdisciplinarity by Distance Learning:
Examples Connecting Economics with Software Engineering, and
Computing with Philosophy
Gordana Dodig-Crnković, Ivica Crnković
e-mentor
No 2 (19) / 2007
www.e-mentor.edu.pl/eng
and experiences with Swedish national course
PHILOSOPHY OF COMPUTER SCIENCE
http://www.idt.mdh.se/personal/gdc/pi-network.htm
http://www.idt.mdh.se/personal/gdc/PI_04/index.html
and
course in software engineering and management of software development
projects for students of management and economy.
146
146
Distance Interdisciplinary Courses
- Internet-based distance undergraduate course in software engineering
and management of software development projects for students of
management and economy. The goal of the course was to bridge the
gap between disciplines of economy (management) and software
engineering, transfer knowledge and provide necessary technical
background for future managers who very likely in their careers will
take part in software intense projects. Both the interdisciplinarity and
the advanced e-learning technology of this course made it challenging.
- Specialized level Swedish National Course in Philosophy of Computing
and Informatics for students of computing, philosophy and design,
which was a combination of a campus-based and a distance course
involving several Swedish universities, with a group of distinguished
teachers from both Sweden and abroad. The critical challenge of this
course was the establishing of a new inter-discipline and overarching
the gaps between traditions of disciplinary thinking.
147
•
•
•
It is interesting to compare the experiences of two different
courses aimed at strengthening interdisciplinary and crossdisciplinary competence and learning practices.
The course in software engineering for managers was necessarily
focused towards implementations and practical applications. The
ambition to provide future managers and economists with a
holistic view of management of software-intense projects turned
out not to be simple to realize. Taking a holistic approach goes
beyond exchanging basic facts between different knowledge
communities. In many cases the basic facts are not sufficient to
adequately describe specific cases of interest. Not only technical
matters but also many informal, cultural factors can be expected
to constitute barriers to reaching a common understanding
between fields which are so far from each other that they usually
148
do not communicate directly.
COMPUTING AND PHILOSOPHY
ARTS
PHILOSOPH
Y
COMP. ENG.
COMPUTER
SCIENCE
COMPUTING
149
149
LECTURES – PART I
22 January
09-12 Introduction to Philosophy of Information –
Luciano Floridi
13-14 Discussion on Introduction to PI
14-15 Physics as an “Ideal Science” Philosophical Foundations and Consequences
Lars-Göran Johansson
15-17 The Function of Natural Laws in Physics
Lars-Göran Johansson
23 January
09-12 Philosophical Foundations of Computability
Gordana Dodig-Crnkovic
13-14 Discussion on Phil. Found. of Computability
14-15 Planning for the Course and Mini-Conference
Closing Remarks (GDC)
150
150
LECTURES – PART II
04 March
09-12 Methodological Foundations of CS
Erik Sandewall
13-14 Discussion on Meth. Found. of CS
14-15 Critical Analysis of CS Methodology
Björn Lisper, Jan Gustafsson
15-16 Discussion on Critical Analysis of CS
Methodology, Björn Lisper, Jan Gustafsson
05 March
09-12 Modelling and Simulation
Kimmo Eriksson, Lars-Göran Johansson
13-14 Discussion on Modelling and Simulation
14-15 DISCUSSION OF PAPER DRAFTS (GDC)
15-16 Closing Remarks
151
151
LECTURES – PART III
13 May
09-12 Ethics and Professional Issues in Computing
Gordana Dodig-Crnkovic
13-14 Discussion on Ethics and Professional Issues
in Computing
14-15 Ethics and AI (Peter Funk)
15-16 Discussion on Ethics and AI
14 May
09-16 MINI-CONFERENCE
16-17 Closing Remarks
152
152
PI NETWORK
Ahonen-Jonnarth Ulla Senior Lecturer, CS/Biology, Gävle University
Dodig-Crnkovic Gordana Senior Lecturer, CS/Physics, Mälardalen University
Gustafsson Jan Senior Lecturer Computer Science, Mälardalen University
Funk Peter Senior Lecturer (docent) Artificial Intelligence Mälardalen University
Lager Torbjörn Professor of General
and Computational Linguistics, Göteborg University
Lisper Björn Professor of Computer Engineering, Mälardalen University
Nivre Joakim Professor of Computational Linguistics, Växjö University
Odelstad Jan Senior Lecturer (docent) CS/Theoretic Philosophy Gävle University
Correspondent: Gang Liu Deputy Director of Philosophy of Science and Technology
DivisionInstitute of Philosophy, Chinese Academy of Social SciencesPhD in
Philosophy, Beijing
153
153
Why is Philosophy Important for Computing?
•
”Thinking tool-box” - access to:
– Paradigms
– Metaphors
– Historical examples (knowledge capital)
•
Communication – both within computing community and wider
•
Context – conceptual and cultural framework
•
Humanist dimensions of higher education are important!
•
Knowledge society – leads to automated production, organization and even
automated discovery. Genuine human thinking abilities including creativity will
make the difference!
154
154
Why is Computing Important for Philosophy?
•
•
Simulated or experimental philosophy. Experiments “in silico” (or
alternative constructed cognitive/computational systems): As an
innovative extension of an ancient tradition of thought experiment,
application of computational modeling schemes to questions in logic,
epistemology, philosophy of science, philosophy of biology, philosophy
of mind, and so on.
Computing paradigms and metaphors
155
155
Results from the PI Course
•
Participants from different universities (Blekinge, Dalarna, Mälardalen,
Skövde, Uppsala, SICS Stockholm) have taken part in the course and
have presented their research papers at the Mini-conference. These
have been documented in the Course Proceedings,
http://www.idt.mdh.se/personal/gdc/PI_04/proceedings.pdf
•
As a result of the course ten papers have been published in journals
and conference proceedings or included as chapters in PhD theses.
156
156
Future Work
Extended network activity and future, possibly distance, courses in
collaboration with colleagues in other countries:
- Peter Boltuc, University of Illinois at Springfield;
- Vincent Müller, American College of Thessaloniki;
- Jordi Vallverdú. Universitat Autònoma de Barcelona;
- Teresa Numerico, University of Bologna and the University of Salerno;
- Matti Tedre University of Joensuu, Finland,
- Russ Abbott, California State University, Los Angeles
and a number of colleagues from Swedish Universities).
This will certainly broaden our experience and allow us to identify further
relevant topics to be included.
157
157
Computation, Information, Cognition:
The Nexus and the Liminal
Editor(s): Gordana Dodig Crnkovic and Susan Stuart
Cambridge Scholars Publishing Titles
in Print as of July 2007
http://www.c-s-p.org/Flyers/Computation-Information--Cognition--The-Nexus-and-theLiminal.htm
158
Computation, Information, Cognition:
The Nexus and the Liminal
Editor(s): Gordana Dodig Crnkovic and Susan Stuart
Cambridge Scholars Publishing Titles
in Print as of July 2007
http://www.c-s-p.org/Flyers/Computation-Information--Cognition--The-Nexus-and-theLiminal.htm
159
Knowledge Generation
as Natural Computation
KGCM - International Conference on
Knowledge Generation, Communication and Management
July 8-11, 2007 – Orlando, Florida, USA.
Gordana Dodig-Crnkovic
n
http://www.idt.mdh.se/personal/gdc/
Department of Computer Science and Engineering
Mälardalen University, Sweden
160
Correspondence Principle
picture from Stuart A. Umpleby
http://www.gwu.edu/~umpleby/recent_papers/2004_what_i_learned_from_heinz_von_foer
ster_figures_by_umpleby.htm
TM
Natural Computation
161
Church-Turing Thesis*
*Source: Stanford Encyclopaedia of Philosophy
162
A Turing machine is an abstract representation of a
computing device.
It is more like a computer program (software)
than a computer (hardware).
163
LCMs [Logical Computing Machines:
Turing’s expression for Turing machines]
were first proposed by Alan Turing,
in an attempt to give
a mathematically precise definition
of "algorithm" or "mechanical procedure".
164
•
•
•
•
The Church-Turing thesis
concerns an
effective or mechanical method
in logic and mathematics.
165
•
A method, M, is called ‘effective’ or ‘mechanical’ just in case:
1.
M is set out in terms of a finite number of exact instructions (each
instruction being expressed by means of a finite number of symbols);
M will, if carried out without error, always produce the desired result in a
finite number of steps;
M can (in practice or in principle) be carried out by a human being unaided
by any machinery except for paper and pencil;
M demands no insight or ingenuity on the part of the human being carrying
it out.
2.
3.
4.
166
• Turing’s thesis: LCMs [logical computing machines; TMs] can do
anything that could be described as "rule of thumb" or "purely
mechanical". (Turing 1948)
• He adds: This is sufficiently well established that it is now agreed
amongst logicians that "calculable by means of an LCM" is the correct
accurate rendering of such phrases.
167
• Turing introduced this thesis in the course of arguing that the
Entscheidungsproblem, or decision problem, for the predicate calculus
- posed by Hilbert in 1928 was unsolvable.
168
• Church’s account of the Entscheidungsproblem
• By the Entscheidungsproblem of a system of symbolic logic is here
understood the problem to find an effective method by which, given
any expression Q in the notation of the system, it can be determined
whether or not Q is provable in the system.
•
169
• The truth table test is such a method for the propositional calculus.
• Turing showed that, given his thesis, there can be no such method for
the predicate calculus.
170
• Turing proved formally that there is no TM which can determine, in a
finite number of steps, whether or not any given formula of the
predicate calculus is a theorem of the calculus.
• So, given his thesis that if an effective method exists then it can be
carried out by one of his machines, it follows that there is no such
method to be found.
171
• Church’s thesis: A function of positive integers is
effectively calculable only if recursive.
172
Misunderstandings of the Turing Thesis
• Turing did not show that his machines can solve any problem that can
be solved "by instructions, explicitly stated rules, or procedures" and
nor did he prove that a universal Turing machine "can compute any
function that any computer, with any architecture, can compute".
173
• Turing proved that his universal machine can compute any function
that any Turing machine can compute; and he put forward, and
advanced philosophical arguments in support of, the thesis here called
Turing’s thesis.
174
• A thesis concerning the extent of effective methods - procedures that a
human being unaided by machinery is capable of carrying out - has no
implication concerning the extent of the procedures that machines are
capable of carrying out, even machines acting in accordance with
‘explicitly stated rules’.
175
• Among a machine’s repertoire of atomic operations there may be those
that no human being unaided by machinery can perform.
176
• Turing introduces his machines as an idealised description of a certain
human activity, the one of numerical computation, which until the advent
of automatic computing machines was the occupation of many thousands
of people in commerce, government, and research establishments.
•
177
• Turing’s "Machines". These machines are humans who calculate.
(Wittgenstein)
• A man provided with paper, pencil, and rubber, and subject to strict
discipline, is in effect a universal machine. (Turing)
178
• The Entscheidungsproblem is the problem of finding a humanly
executable procedure of a certain sort, and Turing’s aim was precisely
to show that there is no such procedure in the case of predicate logic.
179
Other Models of Computation
180
Models of Computation
• Turing Machines
• Recursive Functions
• Post Systems
• Rewriting Systems
181
Turing’s Thesis
A computation is mechanical if and only if
it can be performed by a Turing Machine.
Church’s Thesis (extended)
All models of computation are equivalent.
182
Post Systems
• Axioms
• Productions
Very similar to unrestricted grammars.
183
Theorem:
A language is recursively enumerable
if and only if it is generated by a Turing Machine.
184
Theorem:
A language is recursively enumerable
if and only if it is generated by a recursive function.
185
Post Systems Example: Unary Addition
Axiom: 1  1  11
Productions:
V1  V 2  V 3
 V11  V 2  V 3 1
V1  V 2  V 3
 V1  V 2 1  V 3 1
186
A production:
V1  V 2  V3
 V11  V 2  V3 1
1  1  11  11  1  111  11  11  1111
V1  V 2  V3
 V1  V 2 1  V3 1
187
Post systems are good for
proving mathematical statements
from a set of Axioms.
188
Theorem:
A language is recursively enumerable
if and only if it is generated by
a Post system.
189
Rewriting Systems
They convert one string to another
• Matrix Grammars
• Markov Algorithms
• Lindenmayer-Systems (L-Systems)
Very similar to unrestricted grammars.
190
Matrix Grammars
Example:
P1 : S  S1 S 2
P2 : S1  aS 1 , S 2  bS 2 c
P3 : S1   , S 2  
Derivation:
S  S1 S 2  aS 1bS 2 c  aaS 1bbS 2 cc  aabbcc
A set of productions is applied simultaneously.
191
P1 : S  S1 S 2
P2 : S1  aS 1 , S 2  bS 2 c
P3 : S1   , S 2  
n n n
L  { a b c : n  0}
192
Theorem:
A language is recursively enumerable
if and only if it is generated by
a Matrix grammar.
193
Markov Algorithms
Grammars that produce
Example:

ab  S
aSb  S
S  
Derivation:
aaabbb  aaSbb  aSb  S  
194
ab  S
aSb  S
S  
n n
L  { a b : n  0}
*
In general:
L  {w : w   }
195
Theorem:
A language is recursively enumerable
if and only if it is generated by a Markov algorithm.
196
Lindenmayer-Systems
They are parallel rewriting systems
Example:
a  aa
Derivation:
a  aa  aaaa  aaaaaaaa
L  {a
2
n
: n  0}
197
Lindenmayer-Systems are not general
as recursively enumerable languages
Extended Lindenmayer-Systems:
( x, a, y )  u
context
Theorem:
A language is recursively enumerable if and only if it is
generated by an Extended Lindenmayer-System.
198
L-System Example: Fibonacci numbers
• Consider the following simple grammar:
•
•
•
•
•
•
variables : A B
constants : none
start: A
rules: A B
B  AB
199
• This L-system produces the following sequence of strings ...
•
•
•
•
•
•
•
•
Stage 0 : A
Stage 1 : B
Stage 2 : AB
Stage 3 : BAB
Stage 4 : ABBAB
Stage 5 : BABABBAB
Stage 6 : ABBABBABABBAB
Stage 7 : BABABBABABBABBABABBAB
200
• If we count the length of each string, we obtain the Fibonacci sequence
of numbers :
•
1 1 2 3 5 8 13 21 34 ....
201
Example - Algal growth
The figure shows the pattern of cell lineages found in
the alga Chaetomorpha linum.
To describe this pattern, we must let the symbols
denote cells in different states, rather than different
structures.
202
• This growth process can be generated from an axiom A and growth
rules
•
•
•
•
•
A  DB
BC
CD
DE
E A
203
Here is the pattern generated by this model.
It matches the arrangement of cells in the original alga.
•
•
•
•
•
•
•
•
•
•
•
•
Stage 0 :
A
Stage 1 :
D
B
Stage 2 :
E
C
Stage 3 :
A
D
Stage 4 :
D
B
E
Stage 5 :
E
C
A
Stage 6 :
A
D
D
B
Stage 7 :
D B E
E
C
Stage 8 : E C A
A
D
Stage 9 : A D D B D B E
Stage 10 : D B E E C E C A
Stage 11 : E C A A D A D D B
204
Example - a compound leaf (or branch)
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Leaf1 {
; Name of the l-system, "{" indicates start
; Compound leaf with alternating branches,
angle 8
; Set angle increment to (360/8)=45 degrees
axiom x
; Starting character string
a=n
; Change every "a" into an "n"
n=o
; Likewise change "n" to "o" etc ...
o=p
p=x
b=e
e=h
h=j
j=y
x=F[+A(4)]Fy ; Change every "x" into "F[+A(4)]Fy"
y=F[-B(4)]Fx ; Change every "y" into "F[-B(4)]Fx"
[email protected]@i1.18
}
; final } indicates end
205
http://www.xs4all.nl/~cvdmark/tutor.html
(Cool site with animated L-systems)
206
Here is a series of forms created by slowly changing the
angle parameter. lsys00.ls
Check the rest of the Gallery of L-systems:
http://home.wanadoo.nl/laurens.lapre/
207
Plant
Reception
Environment
Response
Internal processes Internal processes
Response
Reception
A model of a horse chestnut
tree
inspired by the work of Chiba
and Takenaka.
Here branches compete for light
from the sky hemisphere.
Clusters of leaves cast shadows
on branches further down. An
apex in shade does not produce
new branches. An existing
branch whose leaves do not
receive enough light dies and is
shed from the tree. In such a
manner, the competition for light
controls the density of branches
in the tree crowns.
208
Plant
Environment
Reception
Response
Internal processes
Internal processes
Response
Reception
209
Apropos adaptive reactive systems:
"What's the color of a chameleon put onto a mirror?" -Stewart
Brand
(Must be possible to verify experimentally, isn’t it?)
210
Fundamental Limits of Computation
211
Biological Computing
212
DNA Based Computing
• Despite their respective complexities, biological and mathematical
operations have some similarities:
• The very complex structure of a living being is the result of applying
simple operations to initial information encoded in a DNA sequence
(genes).
• All complex math problems can be reduced to simple operations like
addition and subtraction.
213
• For the same reasons that DNA was presumably selected for living
organisms as a genetic material, its stability and predictability in
reactions, DNA strings can also be used to encode information for
mathematical systems.
214
The Hamiltonian Path Problem
• The objective is to find a path from start to end going through all the
points only once.
• This problem is difficult for conventional (serial logic) computers
because they must try each path one at a time. It is like having a whole
bunch of keys and trying to see which fits a lock.
215
• Conventional computers are very good at math, but poor at "key into
lock" problems. DNA based computers can try all the keys at the same
time (massively parallel) and thus are very good at key-into-lock
problems, but much slower at simple mathematical problems like
multiplication.
• The Hamiltonian Path problem was chosen because every key-intolock problem can be solved as a Hamiltonian Path problem.
216
Solving the Hamiltonian Path Problem
1.
2.
3.
4.
5.
Generate random paths through the graph.
Keep only those paths that begin with the start city (A) and conclude
with the end city (G).
Because the graph has 7 cities, keep only those paths with 7 cities.
Keep only those paths that enter all cities at least once.
Any remaining paths are solutions.
217
Solving the Hamiltonian Path Problem
•
The key to solving the problem was using DNA to perform the five
steps in the above algorithm.
•
These interconnecting blocks can be used to model DNA:
•
218
• DNA tends to form long double helices:
•
•
The two helices are joined by "bases", represented here by coloured
blocks. Each base binds only one other specific base. In our example,
we will say that each coloured block will only bind with the same
colour. For example, if we only had red blocks, they would form a long
chain like this:
•
•
Any other colour will not bind with red:
•
•
•
•
•
219
Programming with DNA
• Step 1: Create a unique DNA sequence for each city A through G. For
each path, for example, from A to B, create a linking piece of DNA
that matches the last half of A and first half of B:
•
• Here the red block represents city A, while the orange block represents
city B. The half-red half-orange block connecting the two other blocks
represents the path from A to B.
•
In a test tube, all the different pieces of DNA will randomly link with
each other, forming paths through the graph.
220
• Step 2: Because it is difficult to "remove" DNA from the solution, the
target DNA, the DNA which started at A and ended at G was copied
over and over again until the test tube contained a lot of it relative to
the other random sequences.
• This is essentially the same as removing all the other pieces. Imagine a
sock drawer which initially contains one or two coloured socks. If you
put in a hundred black socks, chances are that all you will get if you
reach in is black socks!
221
• Step 3: Going by weight, the DNA sequences which were 7 "cities"
long were separated from the rest.
• A "sieve" was used which allows smaller pieces of DNA to pass
through quickly, while larger segments are slowed down. The
procedure used actually allows you to isolate the pieces which are
precisely 7 cities long from any shorter or longer paths.
222
• Step 4: To ensure that the remaining sequences went through each of
the cities, "sticky" pieces of DNA attached to magnets were used to
separate the DNA.
• The magnets were used to ensure that the target DNA remained in the
test tube, while the unwanted DNA was washed away. First, the
magnets kept all the DNA which went through city A in the test tube,
then B, then C, and D, and so on. In the end, the only DNA which
remained in the tube was that which went through all seven cities.
223
• Step 5: All that was left was to sequence the DNA, revealing the path
from A to B to C to D to E to F to G.
224
Advantages
• The above procedure took approximately one week to perform.
Although this particular problem could be solved on a piece of paper in
under an hour, when the number of cities is increased to 70, the
problem becomes too complex for even a supercomputer.
• While a DNA computer takes much longer than a normal computer to
perform each individual calculation, it performs an enormous number
of operations at a time (massively parallel).
225
• DNA computers also require less energy and space than normal
computers. 1000 litres of water could contain DNA with more memory
than all the computers ever made, and a pound of DNA would have
more computing power than all the computers ever made.
226
The Future
• DNA computing is less than ten years old and for this reason, it is too
early for either great optimism of great pessimism.
• Early computers such as ENIAC filled entire rooms, and had to be
programmed by punch cards. Since that time, computers have become
much smaller and easier to use.
227
• DNA computers will become more common for solving very complex
problems.
• Just as DNA cloning and sequencing were once manual tasks, DNA
computers will also become automated. In addition to the direct
benefits of using DNA computers for performing complex
computations, some of the operations of DNA computers already have,
and perceivably more will be used in molecular and biochemical
research.
• Read more at:
•
http://www.cis.udel.edu/~dna3/DNA/dnacomp.html; http://dna2z.com/dnacpu/dna.html;
•
•
http://www.liacs.nl/home/pier/webPagesDNA; http://www.corninfo.chem.wisc.edu/writings/DNAcomputing.html;
http://www.comp.leeds.ac.uk/seth/ar35/
228
Quantum Computing
229
• Today: fraction of micron (10-6 m) wide logic gates and wires on the
surface of silicon chips.
• Soon they will yield even smaller parts and inevitably reach a point
where logic gates are so small that they are made out of only a handful
of atoms.
• 1 nm = 10-9 m
230
• On the atomic scale matter obeys the rules of quantum mechanics,
which are quite different from the classical rules that determine the
properties of conventional logic gates.
• So if computers are to become smaller in the future, new, quantum
technology must replace or supplement what we have now.
231
What is quantum mechanics?
• The deepest theory of physics; the framework within which all other
current theories, except the general theory of relativity, are formulated.
Some of its features are:
• Quantisation (which means that observable quantities do not vary
continuously but come in discrete chunks or 'quanta'). This is the one
that makes computation, classical or quantum, possible at all.
232
• Interference (which means that the outcome of a quantum process in
general depends on all the possible histories of that process).
•
This is the feature that makes quantum computers qualitatively more
powerful than classical ones.
233
• Entanglement (Two spatially separated and non-interacting quantum
systems that have interacted in the past may still have some locally
inaccessible information in common – information which cannot be
accessed in any experiment performed on either of them alone.)
• This is the one that makes quantum cryptography possible.
234
• The discovery that quantum physics allows fundamentally new modes
of information processing has required the existing theories of
computation, information and cryptography to be superseded by their
quantum generalisations.
235
• Let us try to reflect a single photon off a half-silvered mirror i.e. a mirror
which reflects exactly half of the light which impinges upon it, while the
remaining half is transmitted directly through it.
•
It seems that it would be sensible to say that the photon is either in the
transmitted or in the reflected beam with the same probability.
236
• Indeed, if we place two photodetectors behind the half-silvered mirror in
direct lines of the two beams, the photon will be registered with the
same probability either in the detector 1 or in the detector 2.
• Does it really mean that after the half-silvered mirror the photon travels
in either reflected or transmitted beam with the same probability 50%?
• No, it does not ! In fact the photon takes `two paths at once'.
237
This can be demonstrated by recombining the two beams
with the help of two fully silvered mirrors and placing
another half-silvered mirror at their meeting point, with two
photodectors in direct lines of the two beams.
With this set up we can observe a truly amazing quantum
interference phenomenon.
238
• If it were merely the case that there were a 50% chance that the photon
followed one path and a 50% chance that it followed the other, then we
should find a 50% probability that one of the detectors registers the
photon and a 50% probability that the other one does.
• However, that is not what happens. If the two possible paths are
exactly equal in length, then it turns out that there is a 100%
probability that the photon reaches the detector 1 and 0% probability
that it reaches the other detector 2. Thus the photon is certain to strike
the detector 1!
239
It seems inescapable that the photon must, in some
sense, have actually travelled both routes at once for if an
absorbing screen is placed in the way of either of the two
routes, then it becomes equally probable that detector 1
or 2 is reached.
240
• Blocking off one of the paths actually allows detector 2 to be reached.
With both routes open, the photon somehow knows that it is not
permitted to reach detector 2, so it must have actually felt out both
routes.
• It is therefore perfectly legitimate to say that between the two halfsilvered mirrors the photon took both the transmitted and the reflected
paths.
241
• Using more technical language, we can say that the photon is in a
coherent superposition of being in the transmitted beam and in the
reflected beam.
• In much the same way an atom can be prepared in a superposition of
two different electronic states, and in general a quantum two state
system, called a quantum bit or a qubit, can be prepared in a
superposition of its two logical states 0 and 1. Thus one qubit can
encode at a given moment of time both 0 and 1.
242
• In principle we know how to build a quantum computer; we can start
with simple quantum logic gates and try to integrate them together into
quantum circuits.
• A quantum logic gate, like a classical gate, is a very simple computing
device that performs one elementary quantum operation, usually on two
qubits, in a given period of time.
• Of course, quantum logic gates are different from their classical
counterparts because they can create and perform operations on
quantum superpositions.
243
• So the advantage of quantum computers arises from the way they
encode a bit, the fundamental unit of information.
• The state of a bit in a classical digital computer is specified by one
number, 0 or 1.
• An n-bit binary word in a typical computer is accordingly described by
a string of n zeros and ones.
244
• A quantum bit, called a qubit, might be represented by an atom in one
of two different states, which can also be denoted as 0 or 1.
• Two qubits, like two classical bits, can attain four different welldefined states (0 and 0, 0 and 1, 1 and 0, or 1 and 1).
245
• But unlike classical bits, qubits can exist simultaneously as 0 and 1,
with the probability for each state given by a numerical coefficient.
• Describing a two-qubit quantum computer thus requires four
coefficients. In general, n qubits demand 2n numbers, which rapidly
becomes a sizable set for larger values of n.
246
• For example, if n equals 50, about 1015 numbers are required to
describe all the probabilities for all the possible states of the quantum
machine--a number that exceeds the capacity of the largest
conventional computer.
• A quantum computer promises to be immensely powerful because it
can be in multiple states at once (superposition) -- and because it can
act on all its possible states simultaneously.
• Thus, a quantum computer could naturally perform myriad operations
in parallel, using only a single processing unit.
247
• The most famous example of the extra power of a quantum computer
is Peter Shor's algorithm for factoring large numbers.
• Factoring is an important problem in cryptography; for instance, the
security of RSA public key cryptography depends on factoring being a
hard problem.
• Despite much research, no efficient classical factoring algorithm is
known.
248
• However if we keep on putting quantum gates together into circuits we
will quickly run into some serious practical problems.
• The more interacting qubits are involved the harder it tends to be to
engineer the interaction that would display the quantum interference.
• Apart from the technical difficulties of working at single-atom and
single-photon scales, one of the most important problems is that of
preventing the surrounding environment from being affected by the
interactions that generate quantum superpositions.
249
• The more components the more likely it is that quantum computation
will spread outside the computational unit and will irreversibly
dissipate useful information to the environment.
• This process is called decoherence. Thus the race is to engineer submicroscopic systems in which qubits interact only with themselves but
not not with the environment.
250
But, the problem is not entirely
new!
Remember STM?
(Scanning Tuneling Microscopy )
STM was a Nobel Prize winning invention by Binning and
Rohrer at IBM Zurich Laboratory in the early 1980s
251
• Title : Quantum Corral
• Media : Iron on Copper (111)
252
• Scientists discovered a new method for confining electrons to artificial
structures at the nanometer length scale.
• Surface state electrons on Cu(111) were confined to closed structures
(corrals) defined by barriers built from Fe adatoms. T
• The barriers were assembled by individually positioning Fe adatoms
using the tip of a low temperature scanning tunnelling microscope
(STM). A circular corral of radius 71.3 Angstrom was constructed in
this way out of 48 Fe adatoms.
253
The standing-wave patterns in the local density of states of the
Cu(111) surface. These spatial oscillations are quantummechanical interference patterns caused by scattering of the twodimensional electron gas off the Fe adatoms and point defects.
254
What will quantum computers be good at?
• The most important applications currently known:
• Cryptography: perfectly secure communication.
• Searching, especially algorithmic searching (Grover's
algorithm).
• Factorising large numbers very rapidly
•
(Shor's algorithm).
• Simulating quantum-mechanical systems efficiently
255
What is Computation?
• Theoretical Computer Science 317 (2004)
• Burgin, M., Super-Recursive Algorithms, Springer Monographs in
Computer Science, 2005, ISBN: 0-387-95569-0
• Minds and Machines (1994, 4, 4) “What is Computation?”
• Journal of Logic, Language and Information (Volume 12 No 4 2003)
What is information?
256
•
Theoretical Computer Science,
2004 Volume:317
Three aspects of super-recursive algorithms and hypercomputation
or finding issue:1-3
black swans
Burgin, Klinger
Hypercomputation
•
Toward a theory of intelligence Kugel
•
Algorithmic complexity of recursive and inductive algorithms Burgin
•
Characterizing the super-Turing computing power and efficiency of classical fuzzy Turing machines
Wiedermann
•
Experience, generations, and limits in machine learning Burgin, Klinger
•
Hypercomputation with quantum adiabatic processes Kieu
•
Super-tasks, accelerating Turing machines and uncomputability Shagrir
•
Natural computation and non-Turing models of computation MacLennan
•
Continuous-time computation with restricted integration capabilities Campagnolo
•
The modal argument for hypercomputing minds Bringsjord, Arkoudas
•
Hypercomputation by definition Wells
•
The concept of computability Cleland
•
Uncomputability: the problem of induction internalized Kelly
•
Hypercomputation: philosophical issues Copeland
257
Descargar

Document