7/21/21
What is an abstraction?
A Physical Machine
0000 0000 0001 0000 0010 0000
Machine Instructions
(defun fun (L) (mapcar #’1+ L))
A Programming Language
An abstraction
A Physical Machine
1
0000 0000 0001 0000 0010 0000
A Physical Machine Machine Instructions
LISP
car
cdr defun map
What is an abstraction?
12
34
A Physical Machine
A Virtual Machine
2
Abstraction of Physical Memory
A Physical Physical Machine Memory
Abstract Memory
3
Abstraction of Physical Memory
An abstract Idea – an array
100 99
1000 82
1500 65
Why is it not a list ofstoragein memory?
Because such a list might not be available – think of a large array
4
600 -5
A physical implementation of the Idea
Programming languages empower us with the ability to do abstract reasoning.
So, it is not just a language designed to instruct the computer to do some calculations.
It is also a language designed to help us derive a solution that is computable.
5
Henceforth, it would be reasonable to ask:
What is a computable solution?
Can we guarantee that all computable solutions derived are runnable on a computer?
Which PLs would allow us to write more computable functions and hence are deemed more powerful?
6
56
1
7/21/21
So, which of the following languages would allow us to write more computable functions & hence are more powerful?
Java
C C++ Simula BCPL LISP Wai Basic
[hold on to your answer] The theory of what can and can’t be computed by an ideal computer is called computability theory.
7
Computable Functions* Computability, however, is an informal notion
but why?
A function is computable if its value can be
obtained by an effective procedure
So, you don’t know if a function is computable
until you know what the effective procedure is.
*I find the brief description in Wikipedia on computable functions an easy read: https://en.wikipedia.org/wiki/Computable_function
8
78
Computable Functions
So far, we have only one procedure – which
one? the human mind
But it is not very effective and we don’t know
how it works
So, we need some procedure that is “simple” and effective.
Two well-known procedures are Turing machines and lambda-calculus
9
Computable Functions
(1936) invented a formal system called l-calculus and defined the notion of computable function using it.
(1936) invented a class of machines and defined the notion of computable function via them.
10
9 10
Turing Machines
1936 – Turing, a Professor at Cambridge, developed an abstract machine to investigate the extent and limitations of what can be computed:
The Turing Machine
An infinite 1-D tape*
Can read/write 0/1 from the tape A state table
For a nice story: https://www.technologyreview.com/s/426834/turings-enduring-importance/
11
An Example of a Turing Machine
Task: Add two positive numbers
Representation: a number n is represented by n+1 1’s. Each number is separated by a 0.
011110111110
Q: What are the numbers on the tape?
12
11 12
2
7/21/21
011110111110
State Table has a 4-tuple entry:
State Id
[ S0, 1, S0, >> ]
Input Move to read next state
Move tape: >> right; << left.
Can write 0/1 on tape too!
13
011110111110
S0
State Table for addition:
[S0,0,S1,1 ] [ S0, 1, S0, >> ]
[ S1, 1, S1, << ] [ S1, 0, S2, >> ]
Note S0 is also known as the start state and S2, the halt state (i.e any state with no entries in the table)
Try running this machine.
14
13 14
011110111110
Start
S0 [ S0, 1, S0, >> ]
[S0,0,S1,1 ] [ S1, 1, S1, << ] [ S1, 0, S2, >> ]
011111111110
Finish S2 You always finish with the pointer at the start of the result – why?
Is the answer correct?
15
011110111110
Start
S0
Sum required is: 3 + 4 = 7
Finish S2
011111111110
Number on tape is 9
What do we need to do to get it right?
16
15 16
Well to get it right, we do:
011111111110
Finish
000111111110
Finish Modify the front bits
011111111000
Finish Modify the end bits
Which is easier and how?
17
Exercise: Complete the table
011111111110
S2
[ S1, 1, S1, << ] [ S1, 0, S2, >> ]
[ S0, 1, S0, >> ]
Remember – you [ S0, 0, S1, 1 ] currently end at
000111111110
S?
S2 – you need to do more
18
17 18
3
7/21/21
Exercise: Complete the table
011111111110
S2
[S0,1,S0,>>] [S0,0,S1,1 ] [S1,1,S1,<<] [ S1, 0, S2, >> ]
[S2, 1,S2,0 ] [S2, 0,S3,>> ] [S3,1,S3,0 ] [ S3, 0, S4, >> ]
000111111110
S4
19
Turing Machines
1936 – Turing, a Professor at Cambridge, developed an abstract machine to investigate the extent and limitations of what can be computed:
The Turing Machine
An infinite 1-D tape*
Can read/write 0/1 from the tape A state table
If the machine halts, the function is computable.
20
19 20
l-calculus
1930s – Church invented an abstract model of
computation using functions and variables.
No, we are not talking about having different functions and variables with different values. Just functions in general (call it lambda, l – no specific name) and variables: a, b, c.
How could the manipulations of functions, defined formally in some ways, be an effective procedure!?
21
Church invented a formal system, l-calculus, which allow him to do the following
Function application – combine l- (M N) terms, M, N.. as lists Can combine terms as a list
like LISPJ
Function abstraction – for creating individual functions; specifying its arguments and body.
Think of l as defun in LISPJ
Function manipulations – reduction, substitution, currying.
(lx.M) args body
22
21 22
Pure l-calculus Formally, l-calculus consists of l-terms:
Examples:
x y l-terms
23
(x (ly.(a b))) A list of 2 l-terms
lx.(y z) (lx. (ly. (x y))) Function definitions
(x y)
lx.x
((lx.x) y) Function application
Pure l-calculus Reduction Examples
(lx. x z) (a b) (a b) z
(lx. ly.x) y z (ly.y) z z
Like Turing, Church now faced the question: how could we use the calculus to compute something (i.e. turn it into a program)?
24
23 24
4
7/21/21
Pure l-calculus Like Turing, to compute, you need a
representation system. What did Turing use?
Church observed that numbers can be represented as functions:
1 = (succ 0)
2 = (succ 1) = (succ (succ 0))
3 = (succ 2) = (succ (succ (succ 0))) :
25
Church numerals
So, using his formal system, l-calculus,
numbers can be represented as follows:
0 := λf.λx.x
1 := λf.λx.f x
2 := λf.λx.f (fx)
3 := λf.λx.f (f (fx))
λfx.x
λfx. f (x) λfx.f(f x) λfx.f(f(f x))
Simplified to the right by writing λf.λx as λfx
26
25 26
Church numerals
So, what does this represent: λfx.f(f(f(f(f x)) 5
Integers are represented as higher-order functions. The number of f tells you what the number is.
27
Hooray, the first abstract program! 0 := λf.λx.x λfx.x
1 := λf.λx.f x λfx. f (x) SUCC := λnfx.f (n f x)
Succ 0 = λnfx.f(n f x) (λfx. x) = λfx.f( (λfx. x) f x)
= λfx.f( (λx. x) x) = λfx.f (x)
28
27 28
Church numerals 0 := λf.λx.x λfx.x
1 := λf.λx.f x λfx. f x
SUCC := λnfx.f (n f x)
Succ 0 = λnfx.f(n f x) (λab. b)
= λfx.f( (λab. b) f x) ; replace n = (λab. b) =λfx.f((λb.b)x) ; replace a = f
= λfx.f (x) ; replace b = x
29
Church numerals
0 := λf.λx.x 1 := λf.λx.f x
SUCC := λnfx.f (n f x)
Take the current number n
λfx.x λfx. f x
Put the previous value to it
Add 1 f to it
30
29 30
5
7/21/21
Pure l-calculus in horror! On no, why so terrible just to work out the
successor!?
Why use such an ugly representation? Why don’t you use numbers? So nice, so easy – succ(5) is 6.
It is not about creating an alternative representation for numbers but rather for proving how computations work. Like TM, it is not designed for you to write practical programs.
31
Summary: l-calculus & TM
Both created a formalism using only symbols
and rules!
l-calculus ignores any details of the machine in proving computability. It captures the idea that computation is a process and hence could be described using functions
TM shows how computation can be done by a machine; no humans needed. Implication?
32
31 32
Summary: l-calculus & TM
Turing later proved that any problem that can be described as a sequence of mathematical steps can be solved using the same procedure
In other words, a function is computable if a TM halts. Or, a TM will halt if the function is computable. Implications? This guarantees the computer will find you
your solution if you run a computable function.
Turing also showed that a TM can run another
TM, giving rise to the idea of a Universal TM.
Implication? We can have a general purpose computer that runs every computable function.
33
Summary: l-calculus & TM
So, what is this digression into Turing machines
and l-calculus really mean?
More importantly, for this course, how are they related to programming languages? [especially since we don’t program in them anyway?]
You might want to read: http://www.i- programmer.info/programming/theory/4514-lambda-calculus-for- programmers.html
34
33 34
Summary: l-calculus & TM Both discovered an effective procedure for
computing a result
Turing’s work led to the invention of general purpose computers and a proof that if you run any computable function, the machine will halt.
Church’s work, on the other hand, lay the foundation for the study of of functional programming, recursion theory and computability
35
So, which of the following languages would allow us to write more computable functions and hence is a more powerful language?
Java
C C++ Simula BCPL LISP Wai Basic
None because every computable function can be written using them. Technically, they are Turing equivalent.
36
35 36
6
7/21/21
So, which of the following languages would allow us to write more computable functions and hence is a more powerful language?
C++ Simula
Java C
C++ Simula
BCPL LISP
But, which ones allow us to write better programs, solve problems faster, solve problems easier, etc.?
Or, for some of you, which ones allow us to get a job, to make more money, etc.?
37
Evolution of computation
Perform a single task Hard-wired
Perform any single task An effective procedure
Perform any task A computer
Use a lookup table
A Turing Machine l-calculus
A Universal Turing Machine
38
37 38
39 40
41 42
If the machine can compute, how do we know that it is intelligent?
Turing Test
Turing Test
Is Turing Test an adequate test of intelligence?
No, because it is a behavioral test
Furthermore, even if it passes the test, it does not mean it is truly intelligent i.e with “conscious” behavior
40
A thought-experiment for AI
Searle’s Chinese Room Argument 1980
41
Searle’s Chinese Room Argument
42
7
7/21/21
Replies to the Chinese Room Argument
The systems reply (Berkeley)
Yes, the man in the room doesn’t understand but the whole system does!
The robot reply (Yale)
Allow the program to interact in the world by putting it inside a robot. Then the robot could come to understand what it is doing.
43
Replies to the Chinese Room Argument
The brain simulator reply (Berkeley/MIT)
Imagine the program is written not in the usual symbolic manner but rather in a way that it simulates how the brain works! So, if the brain in us could somehow give us consciousness, then such a program would too!
44
43 44
45
Replies to the Chinese Room Argument
The combination reply (Berkeley/Stanford)
If we have all the above, then surely the program understands
If you are keen to read more:
https://plato.stanford.edu/entries/chinese-room/
45
8