Lecture 5 - Computation

Question 1

History of computers

Answer 1

Computers originally = people would calculate sine, cosine, tangent of different values in a table

1820s, Charles Babbage:
algorithm machine of 4 tons, 25,000 moving pieces. Cylinders, manually crank, preprogrammed calculations

1837, Charles Babbage and Ada Lovelace
The analytical engine
(not ever made concretely, just idea) … arbitrary calculations, not just preprogrammed ones.
-number cards, printer, operation cards, barrells, mill, variable cards, store, steam engine… HUGE
Ada Lovelace= first programmer, the enchantress of numbers

Von Neurmann Architecture
Machine cycle. 3 parts: Main memory, control unit, ALU
Step 1: Fetch instruction from Main Memory (into control unit)
Step 2: In Control Unit, decode instructions into commands
Step 3: In ALU, execute commands
Step 4: Store results in Main Memory

Question 2

Alan Turing and Turing Machines

Answer 2

Alan Turing, 1912-1954 (killed because gay? suicide?)
Movie The Imitation Game is about him

Turing test/The imitation game: two convos, one with computer and one with person. If external judge can’t tell which is which, computer passes test and is ‘intelligent’

Turing Machines - why?
● Hypothetical system → proof
○ Halting problem
○ Church-Turing Hypothesis
● Metaphor for modern computers → inspired Von Neumann

Turing Machines - what?
● 1-Dim infinite tape with cells (boxes).. Tape head looks at one section at a time
● Read/write head
● Control program
Has states (ex: S1, S2, S3), Tape alphabet (0, 1) and Head moves (left, right)

Example:
Condition (IF) in S1 the current symbol is 0/1, Action (THEN) write symbol 0, move to the right and into S2
If in S2 the current symbol is 0/1, write symbol 1, move to left and into S3
If in S3 the current symbol is 0, write 1 and move to the right into S1
(starts over into a loop)

Question 3

Turing Machine - Implementation

Answer 3

● Implementation doesnʼt matter
● Equivalents:
○ PC:
■ Control program → program
■ Read/write head → CPU
■ Tape → RAM/hard drive
○ DNA/RNA + Proteins

Turing Machines and Marr
● Computational: Goal → execute program
● Algorithmic: Turing Machine program
● Implementation: tape machine (see image) (physical implementation is unimportant…?)

Question 4

Why do we care?

Answer 4

● X is “Turing-computable” → can be implemented on TM
○ E.g. cosine, log, x+1, x^2
● Program ⇔ TM
● Church-Turing Hypothesis
○ How do you know if there CAN BE a program that solves a task?
■ → It can be implemented on a Turing machine
○ Solution exists → can be implemented on TM
○ Can be implemented on TM → solution exists
○ “A function on the natural numbers can be calculated by an effective method if and only if it is
computable by a Turing machine”
● Physical implementation is unimportant

“Turing’s results entail something remarkable, namely that a standard digital computer, given only the right program, a large enough memory and sufficient time, can compute any rule-governed input-output function. That is, it can display any systematic pattern of responses to the environment whatsoever.” (Dennet, 1990)

Question 5

Halting Problem

Answer 5

Turing Machine → Universal Turing Machine
● States (S1, S2, S3) → 0000, 0001, 0010, etc.
● Program instructions (e.g. S1+0 → Right, 1, S2) → 0000 0 1 1 0001
● Tape → Tape
Program ⇔ TM → Computer ⇔ UTM (universal turing machine)

Question: Can we construct UTM that will tell if program halts?
Perfect halting detector program H(W)
-Output: “W halts”… Infinite loop
-Output: “W doesn’t halt”… Stop
Pack it all as program W
Then program W reloops back into perfect halting detector program

For any perfect halting program… can program one that breaks it
For simple problems yes can see if finishable, for any program no

Strange loops
“The next sentence is False.
The previous sentence is True.”

Question 6

Chinese Rooms

Answer 6

Searle’s Chinese Room Argument 1980

If put non-chinese person in a room, someone outside puts in chinese symbol inputs, the person looks in book to find the equivalent symbol, then puts out of room output of result

Kind of like a computer does

Is it “intelligent”?
Does it “understand”?

Chinese room isn’t intelligent, but the book is

Question 7

Complexity - Traveling salesman problem

Answer 7

If the salesman has to road trip through a bunch of cities, the more cities, the more possible paths to take
ex: 5 cities, 12 possible paths
10 cities, 181 440 possible paths
If 25 cities, 310 sextillion possible paths!!!!!!!!!!!!!
Becomes REALLY complex

Computational Complexity
● Quickly solvable → “P” (e.g. calculate 5+4)
● Quickly checkable → “NP” (e.g. Sudoku)
● Neither → “NP-Hard” (e.g. Traveling Salesman Problem)

Question 8

Summary

Answer 8

● History of Computation:
○ Difference Engine → Analytical Engine → Turing Machine → Von Neumann Architecture
● Alan Turing: Cool dude
● Turing Machines: General abstraction of computers and anything computable
● Halting Problem: Problems exist that canʼt be computed
● Complexity: Easiness to solve/check (P/NP). Some problems neither (NP-Hard).
● Brain == Computer?