Document

Chapter 11
Theory of Computation
Chapter 11: Theory of
Computation






11.1
11.2
11.3
11.4
11.5
11.6
Functions and Their Computation
Turing Machines
Universal Programming Languages
A Noncomputable Function
Complexity of Problems
Public Key Cryptography
2
Theory of Computation
--Long before PCs were born, there are theories
developed to justify what machines can or cannot
do.
--Any problem that can be solved on a computer has
a solution expressed in that corresponding
language.
--It can be concluded that there are some problems
unsolvable by today’s machines or any future
algorithmic machine.
3
Functions



Measurement of computation power: if one
machine is capable of computing more
functions than another, the former is
considered the more powerful.
Table lookup method can substitute the
functions for finite pairs of input/output’s.
Algebraic formulas are better ways to
describe the input/output associations of
many functions. V=P(1+r)^n
4
Figure 11.1 An attempt to display the function that
converts measurements in yards into meters
5
Functions



Some functions are too complex to express
by algebraic fucntions. sin(theta)
Can we find a system for computing
fucntions, regardless of the complexity?
Noncomputable function = a function
that cannot be computed by any algorithm
6
Turing Machines





Turing machine introduced by Alan M. Turing in
1936 is conceptual device for studying the power
of algorithmic processes.
It consists of a control unit that can read and
write symbols on a tape by a R/W head.
The tape extends indefinitely at both ends. Each
cell on the tape can store any one of a finite set of
symbols–alphabet.
At any time, it must be in one of a finite number
of states, including start/halt states.
Its computation starts in the start state, and
ceases in the halt state.
7
Figure 11.2 The components of a
Turing machine
8
Turing machine operation

Inputs at each step



State
Value at current tape position
Actions at each step



Write a value at current tape position
Move read/write head
Change state
9
Figure 11.3 A Turing machine for incrementing a
value
10
Universal programming language

A function can be computed in this manner by a Turing machine
is called Turing computable
Church-Turing thesis: A Turing machine
can compute any computable function.
(By Alan Turing and Alonzo Church)




Restatement: any computable function is Turing
computable
Not proven, but generally accepted
Universal programming language = a
language that can express a program to
compute any computable function

Examples: “Bare Bones” and most popular
programming languages
11
The Bare Bones language





Bare Bones is a simple, yet universal language
A universal programming language is a language that
encompasses the power of algorithmic processes
themselves
If a problem can be solved algorithmically, an algorithm
for solving the problem can be expressed in the language
If the problem can not be expressed in the language, there
is no such an algorithm to solve the problem.
Problem ⇔algorithm ⇔language ⇔machine.
12
The Bare Bones language
Machines merely manipulates the bit patterns according to
the instructions.
The bare bones language can simply treat all variables as
being of type “bit pattern of any length” directly, so it
needs no data description statements defined
Variable names consist only of letters; statements terminate
each with a semicolon.
 Statements(3 Assign and 1 Control)
 clear name;
 incr name;
 decr name;
 while name not 0 do; … end;
13
The Bare Bones language








“clear Y;” assigns a string of zeros to a variable Y.
“incrY;”increments the value of a variable Y to be the
next larger integer.
“decrY;”decrements Y to be the next smaller integer,
but remains zero as it is.Statements(Assign and
Control)
Initialization of variables “X = 3”:
“clear X;
incrX;
incrX;
incrX;”. \
14
The Bare Bones language
“clear Z;
 while X not 0 do
 incrZ;
 decrX;
 end;”
--Copy “Z = X”(cause “X = 0”):

15
Figure 11.4 A Bare Bones program for
computing X x Y(Destroying the X value)
16
Figure 11.5 A Bare Bones implementation of the
instruction “copy Today to Tomorrow”
17

理髮師悖論：在薩維爾村有一個理髮師，他掛
出了一塊招牌規定著：「我給而且只給村民中
不給自己刮鬍子的人刮鬍子。」
於是有人就問他：「你給不給自己刮鬍子呢？」
無論這個理髮師怎麼回答都會產生矛盾，如果
他不給自己刮鬍子，那麼按照招牌，他應該給
自己刮鬍子；如果他給自己刮鬍子，按照招牌
所言，他只給村裡不給自己刮鬍子的人刮鬍子，
那麼他便不能給自己刮鬍子。
18

假設有一個克里特人，名字叫伊壁孟德，
然後伊壁孟德說了一句話：「克里特人
都是撒謊者」。
19

“無窮倒退”:
雞與雞蛋，到底先有哪個？”先有雞嗎？
不，它必須從雞蛋裡孵出來，那先有雞
蛋嗎？不，它必須由雞生下。這類耳熟
能詳的例子，在邏輯學家之間稱為“無
窮倒退”。
20
A non-computable function --The halting
problem
Paradox
 Ex1
--The next statement is true.
--The previous statement is false.
Ex2:
The cook on a ship cooks for all those and only
those who do not cook for themselves

21
A non-computable function --The halting
problem


Gödel numbering: Kurt Gödel invented a scheme to
assign a unique non-negative integer to each object
(formulas, proofs, programs) in a collection. Any
program written in Bare Bones is possibly associated
with a unique integer.
This integer is program’s Gödel number.
22
The halting problem






A program is self-terminating if it ultimately
terminates after being started with its first
variable initialized to its Gödel number and
other variables being reset to 0.
Any program is either self-terminating or it is
not.
For instance, the program
“while X not 0 do;
incrX;
end;” .
23
Figure 11.6 Testing a program for selftermination
The halting problem is to predict in advance if a
program will terminate given the input Gödel
number(program).
24
The halting problem
An example of a non-computable function is to
output 1 or 0 according to whether the
program in question is self-terminating given
the input Gödel number(program).
The problem of computing this function is
commonly referred to as the halting problem.
 Given any encoded version of a program,
return 1 if the program will eventually halt, or
0 if the program will run forever.
25
Figure 11.7 Proving the unsolvability of the halting
program
26

某些科學家想讓計算機不工作來節省機
器的壽命。結果他們的辦法便是向計算
機說：“你必須拒絕我現在給你編的語
句，因為我編的所有語句都是錯的。”
沒想到計算機卻因此而不斷地重複工作
直到耗盡它的壽命。
27
Complexity of problems



Among solvable problems, some problems
appear easier than the others.
Big theta notation is used to classify the
algorithms on their efficiencies according to
their execution time.
The insertion sort algorithm is in the class
Θ(n^2), the sequential search algorithm is in
Θ(n), and the binary search algorithm is in
Θ(log n).
28
Complexity of problems


Unfortunately, finding a best solution or
knowing it is the best is difficult.
Time complexity = number of instruction
executions required



Unless otherwise noted, “complexity” means “time
complexity.”
As such, the big O notation is often used to
address the complexity of problems.
If f(n) is a mathematical expression in n and a
problem can be solved by an algorithm in
Θ(f(n)), the complexity of a problem is in
29
O(f(n)) safely upper bounded by f(n).
Complexity of problems
The problem could have a better solution.


A problem is in class O(f(n)) if it can be
solved by an algorithm in Q(f(n)).
A problem is in class Q(f(n)) if the best
algorithm to solve it is in class Q(f(n)).
30
Figure 11.8 A procedure Merge Lists for merging two
lists
31
Figure 11.9 The merge sort algorithm implemented as
a procedure MergeSort
32
Figure 11.10 The hierarchy of problems
generated by the merge sort algorithm
33
Figure 11.11 Graphs of the mathematical expression
n, lg, n, n lg n, and n2
34
Class P






Polynomial problems are the problems in O(f(n)), where f(n) is
either a polynomial itself or bound by a polynomial.
P is traditionally used to represent the collection of all
polynomial problems.
The searching and sorting problems belong to P.
A problem in P can be solved in polynomial time; the problem
has a polynomial time solution.
Class P = all problems in any class Q(f(n)), where f(n) is a
polynomial
Intractable = all problems too complex to be solved practically
 Most computer scientists consider all problems not in class P
to be intractable.
35
Class NP

Class NP = all problems that can be solved
in polynomial time by a nondeterministic
algorithm in a class P
Nondeterministic or deterministic
 May require “creativity
--Go to next intersection and turn either right or left
--Go to next intersection and turn either right or left
depending on what the person standing on the
corner tells you what to do

36
Class NP




The traveling salesman problem: find a path
from/to home via n cities whose total length
within a budget
--Not a polynomial problem
Alternative approach
Pick one of the possible paths and computer
its total distance. If the distance <= budget,
then declare success else nothing
37
Class NP


Class NP
Nondeterministic algorithm = an
“algorithm” whose steps may not be uniquely
and completely determined by the process
state



May require “creativity”
NP-complete problems are the set of problems in NP: if a
solution in P found for one problem in the set, it can be
converted into solutions for others.
Whether the class NP is bigger than class P is
currently unknown.
38
Figure 11.12 A graphic summation of the problem
classification
39
Public key cryptography

Key = specially generated set of values used
for encryption



Public key: used to encrypt messages
Private key: used to decrypt messages
RSA = a popular public key cryptographic
algorithm(honor 3 inventors)

Relies on the (presumed) intractability of the
problem of factoring large numbers
40
Public key cryptography



Math tells us if p and q are prime
numbers and m in an integer between 0
and pq then, for any positive integer k,
it satisfies the following
1=(m^(k(p-1)(q-1))) mod (pq)
If p=3, q=5, m =4, k=1, n=pq=15
4^(2*4) mod 15=65536 mod 15 = 1
41
Encrypting the message 10111
Let integer e, d, n satisfies
e*d=k(p-1)(q-1)+1 and n = p*q
p=7 q=13 e=5 d=29 , n=7x13
5*29=145=2(7-1)(13-1)+1,
 Encrypting keys: n = 91 and e = 5
 10111two = 23ten
e
5
 23 = 23 = 6,436,343
 6,436,343 ÷ 91 has a remainder of 4
 4ten = 100two
 Therefore, encrypted version of 10111 is 100.
42

Decrypting the message 100






Decrypting keys: d = 29, n = 91
100two = 4ten
4d = 429 = 288,230,376,151,711,744
288,230,376,151,711,744 ÷ 91 has a
remainder of 23
23ten = 10111two
Therefore, decrypted version of 100 is
10111.
43
Figure 11.13 Public key cryptography
44
Figure 11.14 Establishing a RSA public key encryption
system
45
Road map to CS study


Fundamental courses: Physics, Mathematics, and
Introduction to Computer Science.
Software:
--Fundamental: Problem Solving and Programming,
Data Structure, Algorithm, and Software Engineering.
--Language: Assembly Language, Programming
Language, C/C++, and JAVA.
--Theory: Software Methodology, Formal Language &
Theory of Computation.
--System: Architecture, OS, Compiler, Networking,
Database, and Multimedia.
46
Road map to CS study

Hardware:
Electronics, Logic Design, VLSI
Design & Digital System Design.

Applications:
Consumer products, Numerical
and Symbolic Computation, Databases and
Information Retrieval, Artificial Intelligence and
Robotics, Graphics, Organizational Informatics,
Bioinformatics
47

Download Report