Transcript Models of Computation - Department of Computer and Information

Department of Computer and Information Science,
School of Science, IUPUI
CSCI 230
Models of Computation
Dale Roberts, Lecturer
Computer Science, IUPUI
E-mail: [email protected]
Dale Roberts
Algorithms
Computer Science is a study of algorithms, which
includes:
their formal mathematical properties
their hardware realizations
their linguistic realizations
their applications
Therefore, our task is to:
design and develop algorithms to solve problems
study the algorithms to see if they are correct or efficient
design and build computer systems which can execute
these algorithms
design programming languages and translate these
algorithms into these languages
Dale Roberts
“If we can specify an algorithm for a
problem, then we can automate its
solution”
Definition of an Algorithm
consists of unambiguous & computable
operations
produce a result
halt in a finite amount of time
Dale Roberts
Examples of Algorithm
A good example of an algorithm
A recipe for cherry pie
step 1: mix 1 cup sugar, ¼ cup flour, ¼ tsp. salt
step 2: stir in ½ cup juice from the cherries
step 3: Cook & stir over medium heat until thick
step 4: Add 3 cups canned, pitted red cherries
step 5: Add 1 tblsp. butter & 4 drops almond extract
step 6: Make pie crust & place in a 9 inch pie plate
step 7: Fill crust with cherry mix & top with 2nd crust
step 8: Bake at 450 oF for 10 mins. then 350 for 45
mins.
Dale Roberts
A bad example of an algorithm
How to use shampoo XYX
step 1: Wet hair
step 2: Lather
step 3: Rinse
step 4: Repeat
What is wrong with algorithm?
Dale Roberts
Algorithmic problem Solving Approach
Algorithm Discovery and Design
Problem:
Assume that we have a list of 10,000 names called N1, N2, N3, …,
N10,000, along with their telephone numbers which we denotes as T1, T2,
T3, …, T10,000. Assume that the numbers are not in alphabetical order.
Design an algorithm which allows to input the name of any specific
person, same NAME. The algorithm should look for NAME in the list of
names and, if found, print the corresponding telephone number. If the
name is not found, print a message “ sorry NAME not found on
the list”
Names
Numbers
N1
T1
N2
T2
N3
T3
…
Nameip
…
…
…
N10,000
T10,000
Dale Roberts
Method 1:
Line
1
2
3
…
9,999
10,000
10,001
Operation
If NAME = N1 then write out the value T1
If NAME = N2 then write out the value T2
If NAME = N3 then write out the value T3
If NAME = N9,999 then write out the value T9,999
If NAME = N10,000 then write out the value T10,000
Stop
Dale Roberts
Method 2:
The sequential Search Algorithm
Line
Operation
1 Set the value of i to 1
2 Repeat lines 3 through 5 until either NAME is found or the
value of i exceeds 10,000
3 Check to see if NAME is equal to the ith name on the list,
i.e., Ni.
4 If they are equal then write the telephone number of that
person, Ti , and mark that NAME has been found
5 Add 1 to the value of i
6 If NAME was not found then write out the message “ I am
sorry ….”
7 Stop, you are done.
Dale Roberts
Method 3:
2nd Attempt at Designing A sequential Search Algorithm
Line
Operation
1 Set the value of i to 1
2 Repeat lines 3 through 5 until NAME is found
3 Check to see if NAME is equal to the ith name on the list,
i.e., Ni.
4 If they are equal then write the telephone number of that
person, Ti , and mark that NAME has been found
5 Add 1 to the value of i
6 Stop, you are done.
Dale Roberts
Algorithm Analysis
Not only we are interested in finding a solution,
we are also interested in finding an efficient one.
In the previous problem, how many comparisons
does it take to find a NAME?
Best case situation: 1 comparison
Worst case situation: n comparisons, where n =
10,000
Average case situation: (n+1)/2, where n=10,000
Dale Roberts
If N is a small number, ex. 100, we may not see
much significant difference.
However, consider the following example:
N.Y. City telephone directory has 20,000,000 entries.
A computer can do 50,000 comparisons per second.
Therefore, the average time to locate NAME is
(20,0000,000/50,000)/2  3½ minutes, or approximately
7 minutes to tell NAME is not in the list!!!
Dale Roberts
Models of Computation
What is a model?
Capture the important properties of the real thing
probably be different in scale from the real thing
suppress details of the real thing
lack full functionality of the real thing
Example: A model to compute the distance traveled for a moving vehicle:
d = r*t
d = distance; r = rate of speed; t = time
Dale Roberts
Why we need models if they are not the
real thing?
By changing some aspects, we can observe their
effects
Can provide an environment for learning
They can be used as design tools without
actually building the real thing – for economic
reasons
In summary, they can be predict, can be used for
training, can be used as test beds.
Dale Roberts
Model of a Computing Agent
Q:
Operations in an algorithm must be unambiguous
and effectively computable. Therefore, could we
design a model of an algorithm before we
implement the algorithm in hardware and /or
software?
A:
A computing agent (robot) is a thing/a person that
carries out the operations described in an algorithm.
Dale Roberts
Properties of a Computing Agent
can accept an input
can store & retrieve information from memory
can take actions according to instructions – the actions
may depend upon a present state and the current input
can produce an output
Agent
Input
Environment
?
Output
So, what is a State?
motor
Dale Roberts
agent
A Concept of a State
Consider a simple scenario:
If I am in my office:
if the phone rings; I’ll answer the phone and leave my office
if the phone does not ring; I’ll not answer the phone and will stay in the office
If I am NOT in my office:
if the phone rings; I’ll NOT answer the phone but I’ll come back to my office
if the phone does not ring; I’ll not answer it and will stay away from the office
Phone ring
I am in office
Answer
I will be in office?
1
1
1
0
0
1
0
1
1
0
0
1
1
0
1
0
Phone
0/1
Office
0/1
Answer the Phone
0/1
Dale Roberts
Output depends NOT ONLY on the INPUT, but also
depends on the internal (current) state of the office (0/1).
Let
A: is a state when I’m in the office
B: is a state when I’m NOT in the office
State Table
Present State
State Transition Diagram
Next State (Output)
phone = 0 phone = 1
in office
A
B
A, 0
B, 0
B, 1
A, 0
0/0
1/1
A
B
1/0
Dale Roberts
out of office
0/0
The Turing Machine (TM)
Turing Machine is a model of computing agent.
It is a pencil-and-paper type model that captures the essential
features of a computing agent.
A Turing machine consists of
1.
2.
3.
4.
a tape that extends infinitely in both directions
the tape is divided into cells, each cell can carry a symbol.
the symbols comes from a finite set of symbols called the alphabet
the alphabet consists of symbols : b (blank), 0, 1, and special
symbols X & Y
. . b b 0 1 1 b b .
1
5.
6.
the tape serve as memory
has a finite number of k states, 1, …k
Dale Roberts
A Turing machine can do only one operation at a
time. Each time an operation is done, three
actions may take place:
write a symbol to cell
2. go into a new state
3. move one cell left or right
1.
The above actions depends on:
The current state of the machine
content of cell currently being read (input)
Dale Roberts
The Turing Machine (TM)
Example: Assume a Turing machine (TM) instruction:
if you are in state 1
and
you are reading symbol 0
then
write symbol 1 onto tape
go into state 2
move right
State Transition:
1
0/1
R
input
R
output
W
Your movement
State: where you are now.
2
current state
next state
action (direction)
Written as: (1,0,1,2,R)
output
input
Dale Roberts
. . b b 0 1 1 b b .
1
. . b b 1 1 1 b b .
12
The Turing Machine (TM)
Example: Design a Turing Machine which will invert the string of binary digits
if the input string is 10110 then the output string should be 01001
let us draw a state diagram
1/0
1
0/1
The TM instruction sets will be
(1,0,1,1,R)
(1,1,0,1,R)
Let the initial configuration be: ... b 1 0 1 1 0 b ...
... b 1 0 1 1 0 b ...
... b 0 0 1 1 0 b ...
... b 0 1 1 1 0 b ...
... b 0 1 0 1 0 b ...
... b 0 1 0 0 0 b ...
... b 0 1 0 0 1 b ...
Dale Roberts
Unary Representation for TM
Unary representation is used in order to do any arithmetic operations on a TM.
Unary representation looks as follows
0 1
1  11
2  111
3  1111
4  11111
Example: Design a Turing Machine to add 1 to any number
start in state 1
if the state is 1 and current input is 1, write 1 and move right and stay in state 1
if the current state is 1 and current input is b, write 1 and move to state 2 and move right
and HALT
1/1
TM instructions:
(1,1,1,1,R)
b/1
1
2 Halt
(1,b,1,2,R)
R
(2,b,-,-,-) not allowed!
Let the initial configuration be: ... b 1 1 1 b ...
s1 ... b 1 1 1 b ... 2 in unary representation
s1 ... b 1 1 1 b ...
s1 ... b 1 1 1 b ...
s1 ... b 1 1 1 b ...
s2 ... b 1 1 1 1 b ... 3 in unary representation
Dale Roberts
Example: Adding of two non-zero numbers (unary representation)
. . b 1 1 1 b 1 1 b . .
. . b b b 1 1 1 1 b . .
Initial Setup
Answer should be:
(1,1,b,2,R):
(2,1,b,3,R):
(3,1,1,3,R):
(3,b,1,4,R):
(4,1,1,4,R):
(4,b,b,5,R):
Erase leftmost 1 and move right
Erase second 1 and move right
pass over any 1’s until a blank is full
write 1 over the blank
pass over remaining 1’s
halt
S1... b 1 1 1 b 1 1 b...
1/1
1
1/b
R
2
1/b
R
3
S2... b b 1 1 b 1 1 b...
1/1
b/1
R
4
b/b
R
Halt
5
S3... b b b 1 b 1 1 b...
S3... b b b 1 b 1 1 b...
S4... b b b 1 1 1 1 b...
S4... b b b 1 1 1 1 b...
S4... b b b 1 1 1 1 b...
Dale Roberts
Example: Add two numbers, 2 + 3
initial setup would: a ‘b’ separate the two numbers.
... b 1 1 1 b 1 1 1 1 b ...
2
3
and the expected answer is
... b 1 1 1 1 1 1 b ...
5
Let the initial configuration be:
S1... b 1 1 1 b 1 1 1 1 b...
S1... b 1 1 1 b 1 1 1 1 b...
The TM instruction sets will be
(1,1,1,1,R)
(1,b,1,2,R)
(2,1,1,2,R)
(2,b,b,3,L)
(3,1,b,4,L)
(4,1,b,5,L)
1/1
R
1
b/1
R
1/1
R
2
S1... b 1 1 1 b 1 1 1 1 b...
S1... b 1 1 1 b 1 1 1 1 b...
S2... b 1 1 1 1 1 1 1 1 b...
S2... b 1 1 1 1 1 1 1 1 b...
S2... b 1 1 1 1 1 1 1 1 b...
S2... b 1 1 1 1 1 1 1 1 b...
S2... b 1 1 1 1 1 1 1 1 b...
S3... b 1 1 1 1 1 1 1 1 b...
b/b
L
3
1/b
L
4
1/b
L
5
Dale Roberts
S4... b 1 1 1 1 1 1 1 b b...
S5... b 1 1 1 1 1 1 b b b...
Example: Add two numbers, 2 + 3
try
(1,1,b,2,R)
(2,1,b,3,R)
(3,1,1,3,R)
(3,b,1,4,R)
if an initial configuration is
1/1
1
1/b
R
2
1/b
R
R
3
b/1
R
4
b b 1 1 1 b 1 1 1 1 b b ..
S1... b b 1 1 1 b 1 1 1 1 b b...
S2... b b b 1 1 b 1 1 1 1 b b...
S3... b b b b 1 b 1 1 1 1 b b...
S3... b b b b 1 b 1 1 1 1 b b...
S3... b b b b 1 1 1 1 1 1 b b...
S4... b b b b 1 1 1 1 1 1 b b...
Dale Roberts