Transcript slides (pptx)

INFO100 and CSE100
Fluency with Information Technology
Katherine Deibel
2012-02-15
Katherine Deibel, Fluency in Information Technology
1


Computers do some really amazing
things don't they?
The following slides are some of
examples of computer applications
that I find simply amazing
2012-02-15
Katherine Deibel, Fluency in Information Technology
2


Computer images have
become complex enough
that telling the difference
between real humans and
CGI characters is hard
We seem to be leaving
the "uncanny valley"
2012-02-15
Katherine Deibel, Fluency in Information Technology
3


Drawing, painting, etc. is often
inaccessible to people with severe
motor disabilities (quadriplegia)
Susumu Harada developed a handsfree drawing software that use the
voice to control the mouse
2012-02-15
Katherine Deibel, Fluency in Information Technology
4
Susumu Harada
Using one’s voice to control a mouse
2012-02-15
Katherine Deibel, Fluency in Information Technology
5

The Indus River civilization was one of the
first human civilizations (located around
coastal Pakistan)
They left scripts that have not been
interpreted and may be art or language
 Rajesh Rao demonstrated through AI
techniques to demonstrate that the it holds
the same patterns as spoken language

2012-02-15
Katherine Deibel, Fluency in Information Technology
6
+
+
Creative thinking
Flexibility of technology
Awareness of issues
No problem is beyond solution
COMPUTERS HAVE NO LIMITS!
2012-02-15
Katherine Deibel, Fluency in Information Technology
7
Apollo Guidance Computer:
2.048 MHz processor
 32KB of RAM


4KB of ROM
4 16-bit registers for computation
 4 16-bit memory registers in CPU

THIS GOT US TO THE MOON!?!
COMPUTERS MUST HAVE NO LIMITS!
2012-02-15
Katherine Deibel, Fluency in Information Technology
8

Physical Limits
 Number of transistors we can fit on a chip
 Speed of light limits transmission

Philosophical Limits
 Can a computer reason like a human?
 Can a computer be conscious/sentient?

Mathematical Limits
 Some problems are intractable
 Some problems are just really hard
 Exactness is a problem
2012-02-15
Katherine Deibel, Fluency in Information Technology
9

Understanding the limits of computers
is a tale of three brilliant minds
David Hilbert
2012-02-15
Kurt Gödel
Alan Turing
Katherine Deibel, Fluency in Information Technology
10
A. Is a test of intelligence
B. Is a test of humanity
C. Involves two individuals
communicating
electronically
D. All of the above
25%
A.
2012-02-15
25%
B.
Katherine Deibel, Fluency in Information Technology
25%
C.
25%
D.
11
A.
B.
C.
D.
Sigmund
Frasier
Eliza
Bob
25%
A.
2012-02-15
25%
B.
Katherine Deibel, Fluency in Information Technology
25%
C.
25%
D.
12
A.
B.
C.
D.
E.
F.
G.
14%
14%
14%
14%
14%
A.
B.
C.
D.
E.
14%
14%
F.
G.
Tic-Tac-Toe
Checkers
Chess
Go
Two of A-D
Three of A-D
All of A-D
2012-02-15
Katherine Deibel, Fluency in Information Technology
13

Understanding the limits of computers
is a tale of three brilliant minds
David Hilbert
2012-02-15
Kurt Gödel
Alan Turing
Katherine Deibel, Fluency in Information Technology
14
The end of the nineteenth century was a
celebration of new science and the belief
that everything would be solved
"Everything that can
be invented has
been invented."
Charles Duell,
U.S. Patent
Commissioner
2012-02-15
Apocryphal quote misattributed to him
but indicative of mindset of that era
Katherine Deibel, Fluency in Information Technology
15

With new formalisms, many
thought that even all of
mathematics was soon to be
codified and solved
 Bertrand Russell and Alfred
Whitehead were preparing
Principia Mathematica
 This three-volume book sought
to derive all of mathematics
from a set of basic axioms
2012-02-15
Katherine Deibel, Fluency in Information Technology
16

There was always a rumor in mathematics
that one should not peer into infinity for
therein lay madness

In the late 1800s, George Cantor
formalized set theory and infinity
 He then spent years in a sanatorium
 To be fair, many mathematicians
hounded him and his work because
it disagreed with common sense and
suggested "dark" truths
2012-02-15
Katherine Deibel, Fluency in Information Technology
17

David Hilbert

2012-02-15
In 1900, Hilbert proposed a list of
23 key unsolved problems in
mathematics and logic
2.
Prove that the axioms of arithmetic
are logically consistent.
10.
Design an algorithm to solve any
Diophantine equation with rational
coefficients.
Everyone was certain that both
questions had positive answers
to be discovered
Katherine Deibel, Fluency in Information Technology
18

In 1931, Gödel answered if it
was possible to prove arithmetic
to be logical consistent
The answer was NO
 Two Incompleteness Theorems:
Any sufficiently complex
axiomatic system cannot be
used to prove that itself is:

Kurt Gödel
 Complete
 Consistent
2012-02-15
Katherine Deibel, Fluency in Information Technology
19

Gödel's theorems awoke
the idea that systems of
mathematics and logic
are inherently limited

Maybe some problems
(like problem 10) have
no algorithmic solutions
 Problem 10 proven in
1910 to be impossible
2012-02-15
Gödel, Escher, Bach
by
Douglas Hofstadter
Katherine Deibel, Fluency in Information Technology
20
Turing worked for the British in
WWII to break Nazi Germany's
Enigma encryption scheme
 Earlier graduate work extended
Gödel's theorems to computers

 Developed a mathematical model of a
Alan Turing
computer—the Turing Machine

His Turing Machine
 Could simulate any computer system
 Demonstrated that some problems are
intractable (unsolvable)
2012-02-15
Katherine Deibel, Fluency in Information Technology
21
Mathematical model of a
computer consisting of
An infinite tape
 A read-write head that
handles one cell at a time


A fixed alphabet of symbols
A fixed set of possible states
 A set of rules governing
writing, reading, head
movement, state changes, etc.
UW's CSE's
Steam-Powered
Turing Machine

2012-02-15
Katherine Deibel, Fluency in Information Technology
22
Everything but the infinite tape:
http://www.youtube.com/watch?v=E3keLeMwfHY
2012-02-15
Katherine Deibel, Fluency in Information Technology
23

The Turing Machine is the basis for
all theoretical computer science

Church-Turing Thesis:
All functions that can be computed
can be done so on a Turing Machine.

This allows for us to theorize about
computation without programming!
2012-02-15
Katherine Deibel, Fluency in Information Technology
24

Can we write a program to
determine if another program will
ever finish?
function willItHalt(program) {
}
2012-02-15
Katherine Deibel, Fluency in Information Technology
25

If we could write willItHalt(…)
 Easy to determine if complex problems
have a solution
 Prevent infinite loops
 Would actually allow us to detect any
virus or malware

It is too bad that we can never write
such a program
2012-02-15
Katherine Deibel, Fluency in Information Technology
26

HALT(p, i) returns true if program p halts
on input i, false otherwise
function TRICK(p, i) {
if(HALT(p,i) == true) loop forever;
else return true;
}
 What happens with TRICK(TRICK,TRICK)?

2012-02-15
Katherine Deibel, Fluency in Information Technology
27

Assume HALT(TRICK, TRICK) returns true
 TRICK does not loop forever

But… look at the code:
if(HALT(TRICK,TRICK) == true)
loop forever;
Therefore, TRICK loops forever
 CONTRADICTION!

2012-02-15
Katherine Deibel, Fluency in Information Technology
28

Assume HALT(TRICK, TRICK) returns false
 TRICK does loop forever

But… look at the code:
if(HALT(TRICK,TRICK) == true)
loop forever;
else
return true;
 Therefore, TRICK halts

CONTRADICTION!
2012-02-15
Katherine Deibel, Fluency in Information Technology
29




TRICK cannot halt because of the
contradiction it creates
TRICK cannot loop forever because
of the contradiction it creates
Therefore, TRICK is impossible
Therefore, HALT is impossible
2012-02-15
Katherine Deibel, Fluency in Information Technology
30

A Turing Machine is so powerful that
it cannot be applied to itself
 The self-reference problem
 The Barber Paradox:
The town barber shaves only those men
in town who do not shave themselves.
Who shaves the barber?
2012-02-15
Katherine Deibel, Fluency in Information Technology
31

The intractability of the Halting
Problem leads to
 Many problems that cannot be solved
 Imperfect protection from "bad" programs
2012-02-15
Katherine Deibel, Fluency in Information Technology
32

In 1952, Alan Turing was discovered to
be homosexual and convicted of sexual
indecency
 Turing agreed to receive hormone
"treatments" instead of going to jail

A few months later, Turing was found
dead of cyanide poisoning
 Suicide was not established but was likely
2012-02-15
Katherine Deibel, Fluency in Information Technology
33
Interesting Problems Can Be Hard
2012-02-15
Katherine Deibel, Fluency in Information Technology
34


Fortunately, there are plenty of
problems that Turing Machines (and
computers) can solve
The question is:
How efficiently can we solve them?
2012-02-15
Katherine Deibel, Fluency in Information Technology
35

We have mathematical models of the
complexity of problems to solve
 Big O notation: O( f(n) )
means a program will take f(n) steps

Basic idea for this class:
 Fast, easy problems take polynomial
time: O(n), O(n2), O(n3), O(n log n)
 Harder problems are exponential: O(2n)
2012-02-15
Katherine Deibel, Fluency in Information Technology
36




Sorting a list
Finding the max, min, median, etc.
Determining if a number is prime
Finding the shortest road distance
between two cities
2012-02-15
Katherine Deibel, Fluency in Information Technology
37

There is a difference between solving
a problem and checking a solution
 Checking a solution may take only
polynomial time
 Finding the solution is the problem,
especially if you have to try all the
possibilities
2012-02-15
Katherine Deibel, Fluency in Information Technology
38

A salesman has to visit n cities
Some cities are connected by
airplane trips
 Each trip has a cost associated with it


The salesman wants to visit each city
exactly ONE time
Can he do this?
 What is the minimum cost if he can?

We have no efficient algorithm for this!
2012-02-15
Katherine Deibel, Fluency in Information Technology
39

NP-Complete problems
 Can be checked in polynomial time
 Have no known efficient algorithm

All NP-Complete problems are related
 If we figure out how to solve one in
polynomial time, we can solve ALL of
them in polynomial time
 Known as the "Does NP = P" problem
2012-02-15
Katherine Deibel, Fluency in Information Technology
40






Traveling Salesman
Graph Coloring
Subset Sum
Boolean Satisfiability
Clique finding
Knapsack problems
All have useful applications
in the real world
2012-02-15
Katherine Deibel, Fluency in Information Technology
41

Approximation algorithms
 Give us near-optimal solutions

Probabilistic algorithms
 Use random numbers to get us a chance
at having the best answer
2012-02-15
Katherine Deibel, Fluency in Information Technology
42
The Limits are Closer than You Think
2012-02-15
Katherine Deibel, Fluency in Information Technology
43
A.
B.
C.
D.
E.
F.
1
2
2
3
3
4
true
true
false
true
false
false
17%
A.
2012-02-15
17%
B.
17%
17%
C.
D.
Katherine Deibel, Fluency in Information Technology
17%
E.
17%
F.
44
A.
B.
C.
D.
true true
true false
false true
false false
25%
A.
2012-02-15
25%
B.
Katherine Deibel, Fluency in Information Technology
25%
C.
25%
D.
45

Try it out:
var x = 0.1 + 0.2;
alert((x==0.3) + " " +(x>=0.3));
alert("0.1 + 0.2 = " + x);

What we get:
false true
0.1 + 0.2 = 0.30000000000000004
2012-02-15
Katherine Deibel, Fluency in Information Technology
46


Remember, every number in a
computer is represented in binary
We have discussed how to represent
nonnegative integers
 But what about negative integers?
 What about real numbers?
2012-02-15
Katherine Deibel, Fluency in Information Technology
47

Computers have to play tricks with
binary to represent numbers
 Negative numbers are done through
having a bit for indicating sign plus
some other tricks
 Floating point numbers (decimals) are
only approximations based on binary
fractions and rounding rules
2012-02-15
Katherine Deibel, Fluency in Information Technology
48

If you have to compare decimal
numbers, do the following:
function fuzzyEqual(x, y, err) {
if ( Math.abs(x-y) <= err )
return true;
else
return false;
}
2012-02-15
Katherine Deibel, Fluency in Information Technology
49


err is a tolerance value for how close
you want to be
Math.abs makes (x-y) positive
2012-02-15
Katherine Deibel, Fluency in Information Technology
50

Numbers are infinite; computers are finite
 All number types have upper and lower limits
 Going above and below will cause either
software crashes or calculation errors

Signed zero
 Some systems distinguish between +0 and -0
2012-02-15
Katherine Deibel, Fluency in Information Technology
51

Computers have fundamental limits to them
in terms of math and logic
 Some problems are unsolvable
 Some are hard to solve
 Some basic math can be a problem

But computers do and will do amazing things
 Will we have sentient AI in the future?
 Will computers have emotions?
 Will computers win at chess, go, shogi, etc.?
2012-02-15
Katherine Deibel, Fluency in Information Technology
52

BBC documentary (2008). Dangerous knowledge.

A. Doxiadis, C. Papadimitriou, A. Papadatos &
A.D. Donna (2009). Logicomix: An epic search
for truth.

D.R. Hofstadter (1979). Gödel, Escher, Bach:
An eternal golden braid.
2012-02-15
Katherine Deibel, Fluency in Information Technology
53