School of Computing University of Portsmouth
January, 2022
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 1 / 40
Lecture B: Revision
Copyright By PowCoder代写 加微信 powcoder
THCSB overview
What does “computability” mean? Church-Turing Thesis. Different Computational Models and their equivalence.
Undecidable problems
Computational Complexity – time complexity
Asymptotic growth, big-O, big-Ω, big-Θ
Problem complexity – tractable and intractable problems, lower bounds
P, NP, NP-complete problems
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 2 / 40
What is computable?
It all started with Hilbert’s quest for the foundations of mathematics and a quest for a mechanical procedure for separating mathematical truths from mathematical falsehoods.
What is computable?
“Computable” has something to do with a formal process (execution) and a formal description (algorithm).
Example. The derivation process associated with grammars, the evaluation process associated with functions, the execution process associated with programs and programming languages.
A model is a formalization of an idea (Turing machine, Partial
recursive function, . . . ). Computational models can have different
power. Is there a most powerful model?
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 3 / 40
Church-Turing Thesis
Why “thesis” instead of “theorem”?
On the one hand: we have only informal ideas of what being computable means.
On the other hand: the idea of a Turing machine is formal and precise.
No one ever invented a computational model more powerful than a Turing machine!
But there are several alternative formalisations for the notion of
computability, equivalent to a TM. . .
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 4 / 40
Fact (Church-Turing Thesis)
Anything that is intuitively computable can be computed by a Turing machine.
Computational Models equivalent to TMs
λ-calculus (Church, 1930) – important in the theory of programming languages, original inspiration for functional programming, in particular Lisp
Partial recursive functions (Church-Kleene)
Simple programming language (Stepherdson and Sturgis, 1963) Markov algorithms (Markov, 1954)
Post algorithms (Post, 1943)
Post systems
Game of Life (Conway, 1970; Rendell, 2000)
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 5 / 40
M2: Recursive functions
Primitive recursive functions:
zero, zero(x) = 0
successor, succ(x) = x + 1 projection, projecti(x1, . . . , xk) = xi.
The operations:
composition from primitive recursive functions,
primitive recursion:
f(x, 0) = h(x),
f(x, succ(y)) = g(x, y, f(x, y))
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 6 / 40
M2: Recursive functions
h(x) = succ(succ(zero(x))) h(x) is the constant function that always returns 2.
add(x, 0) = x,
add(x, succ(y)) = succ(add(x, y))
is a primitive recursive function of addition.
All primitive recursive functions are total functions.
All primitive recursive functions are computable by a Turing machine.
But not all functions computable by a TM are primitive recursive – we need to add an operation of minimalisation.
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 7 / 40
M2: Recursive functions
Minimalisation. Define a new function f in terms of a total function g as follows (where x represents any number of arguments).
f(x) = min(y, g(x, y) = 0).
If such a y exists, then define f(x) = y. Otherwise, f(x) is undefined.
Partial recursive functions can be built up using the base functions and the operations of composition, primitive recursion and minimisation.
Partial recursive functions are partial functions.
A function is computable by a TM if an only if it is partial recursive.
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 8 / 40
M2: Recursive functions
The Ackermann function is an example of a function, which is total, but not primitive recursive.
(0,y)=y+1, A(x,0)=A(x−1,1) A(x, y + 1) = A(x − 1, A(x, y))
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 9 / 40
M3: Simple programming language
An informal description:
1 There are variables that take values in the set N of natural numbers.
2 There is a while statement of the form
while X̸=0 do statement od.
3 There is an assignment statement taking one of the three forms: X := 0, X := succ(Y), X := pred(Y).
4 A statement is either:
– a while statement,
– an assignment statement,
– a sequence of two or more statements separated by semicolons.
5 A simple program is a statement.
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 10 / 40
M3: Simple programming language
The simple language has the same power as a Turing machine. Example. A simple code for the macro statement X := Y.
X := succ(Y); X := pred(X); A simple code for the macro statement X := 2.
X := 0; X := succ(X); X := succ(X);
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 11 / 40
M4: Markov algorithms
Markov algorithms are equivalent in power to Turing machines.
A Markov algorithm transforms an input string into an output string using a given finite ordered sequence of productions.
Example. Suppose M is the Markov algorithm over {a, b} consisting of the following sequence of three productions:
1. aabaa → b
What will be the output for a string aaabaaaaa?
Remember, the order of production is important!
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 12 / 40
M5: Post algorithms
Post algorithms are equivalent in power to Turing machines.
A Post algorithm transforms an input string into an output string using a given finite sequence of productions.
The productions have the form s → t, where s and t are strings made up of symbols from Σ and possibly some variables (some productions can be labelled with halt).
If a variable X occurs in t then X occurs in s.
Don’t forget, an input string (or any string in the process of
derivation) must match with the left side of a production rule.
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 13 / 40
M5: Post algorithms
Example. Consider the following single production over the alphabet {a, b}:
Applying this Post algorithm to the string: – aaabb returns a,
– aaabbb returns Λ, – bb returns bb.
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 14 / 40
Typical kinds of questions
State the Church-Turing Thesis.
Compare the class of problems which are solvable by TMs and today’s computers.
Are all computational models the same in power?
Give an example of a computational model which is equivalent to the Turing machine (describe it in details).
What is the Ackermann function?
Given a partial recursive function, be able to calculate one of its values.
Write or apply a Markov algorithm/Post algorithm.
Rewrite a given macro statement using tools available in a
simple programming language.
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 15 / 40
The basic classification of problems
Undecidable (unsolvable) – can’t be solved by any algorithm ( =⇒ any computer).
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 16 / 40
Undecidable problem
An undecidable decision problem is partially decidable if there is an algorithm that
halts with the answer yes for those instances of the problem that have yes answers, but
may run forever for those instances of the problem whose answers are no.
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 17 / 40
Examples of undecidable problems
The Halting problem. Is there an algorithm that can decide whether the execution of an arbitrary program halts on an arbitrary input? (partially decidable)
The Post correspondence problem. Given a finite sequence of pairs of strings
(s1,t1),…,(sn,tn),
is there a sequence of indexes i1, . . . , ik with repetitions allowed,
si1 …sik = ti1 …tik
Is there an algorithm that can decide whether an arbitrary instance of
the problem has a solution? (partially decidable)
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 18 / 40
Examples of undecidable problems
The Equivalence problem. Does there exist an algorithm that can decide whether two arbitrary computable functions produce the same output?
Hilbert’s Tenth Problem. Does a polynomial equation
p(x1, . . . , xn) = 0 with integer coefficients have a solution consisting of integers? (partially decidable)
The Total Problem. Is there an algorithm to tell whether an arbitrary computable function is total? (not partially decidable)
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 19 / 40
Examples of undecidable problems
The Tiling Problem. Given a particular set of tile types, is it possible to tile all sizes of floor?
The tiles are divided along diagonals, each quarter is coloured in some colour. Edges that touch each other must have the same colour. We can only slide tiles around; we are not allowed to rotate them.
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 20 / 40
Tools from the proof of undecidability
Self-reference – Barber (or librarian) paradox
every man in the town keeps himself clean-shaved: some by shaving themselves, some by attending the barber;
the barber obeys the following rule: He shaves all and only those men in town who do not shave themselves.
Under this scenario, we can ask the following question: Does the barber shave himself?
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 21 / 40
Tools from the proof of undecidability
Diagonalisation
To construct a set (a string/a number) which is not in a given list.
Example. To construct a string of length 6 over the alphabet {0, 1, 2} which is not in a set
{000000, 101010, 010101, 110011, 111111, 111000}.
Idea. For a new string s, for each i, 1 ⩽ i ⩽ 6 define s[i] different fromsi[i],e.g.s[i]=(si[i]+1) mod3.
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 22 / 40
Tools from the proof of undecidability
Countable and uncountable sets
Countable sets are either finite or there is 1-1 matching with the set N of positive integers {1,2,…,}.
Example. The set of even numbers is countable as well as the set of fractions with denominator 3.
Infinite sets that are not countable are uncountable, e.g. the set of all subsets of N is uncountable.
The set of all languages over the finite alphabet is uncountable, but the set of all Turing machines is countable.
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 23 / 40
Examples of exam questions
Give examples of undecidable problems and solve it for some instances.
Explain how a halting problem, if it were solvable, might be useful for solving unsolved problems.
What is the size of the set of all numbers which are divisible by 8, what is the size of the set of all strings over the alphabet
Σ = {a}, what is the size of the set of all languages over the alphabet Σ = {a}, . . .
Why do undecidable problems exist?
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 24 / 40
Asymptotic growth – big O
O(g) is called an asymptotic upper bound of a function f if f grows at most as fast as g
Formal definition: f(n) = O(g(n)) if there exists c, n0 ∈ R+ such that for all n ⩾ n0, f(n) ⩽ c · g(n).
Example. 2n3 + 7n = O(n3), but 2n3 + 7n ̸= O(n)
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 25 / 40
Asymptotic growth – big Ω
Ω(g) is called an asymptotic lower bound of a function f if f grows at least as fast as g.
Formal definition: f(n) = Ω(g(n)) if there exists c, n0 ∈ R+ such that for all n ⩾ n0, f(n) ⩾ c · g(n).
Example. 2n3 + 7n = Ω(n), but 2n3 + 7n ̸= Ω(2n)
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 26 / 40
Asymptotic growth – big Θ
Θ(g) is used to denote the asymptotic tight bound of a function if f is essentially the same as g, to within a constant multiple.
Formal definition: f(n) = Θ(g(n)) if f(n) = O(g(n)) and
f(n) = Ω(g(n)), i.e. there exist n0, c1, c2 ∈ R+ such that for all n ⩾ n0, c1 · g(n) ⩽ f(n) ⩽ c2 · g(n).
Example. 2n3 + 7n = Θ(n3), but 2n3 + 7n ̸= Θ(2n)
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 27 / 40
Hierarchy of basic functions
Here is a hierarchy of some familiar functions according to their growth rates:
1≺logn≺n≺nlogn≺n2 ≺n3 ≺2n ≺3n ≺n!≺nn, where f(n) ≺ g(n) means that
f(n) = O(g(n)) and f(n) ̸= Θ(g(n)) constants don’t matter
the smallest terms in the sum don’t matter
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 28 / 40
Typical kinds of exam questions
Given two functions, f(n) and g(n), can you prove that f is big … ofg?
Can you determine where a particular function f(n) belongs in the hierarchy of functions?
Give an example of functions, which are big . . . of g?
Decide whether the presented relations big . . . are true/false.
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 29 / 40
Analysing algorithms
The choice of an algorithm matters in terms of the resources: time and memory.
The time complexity function, T(n), describes how the time (= number of basic steps of the algorithm) to execute it changes with the size of the input.
Worst case time complexity: the algorithm has to finish for all inputs of size n
Example. Searching in an ordered array:
sequential O(n) versus binary O(log n)
Exchange sort O(n2) versus Merge sort O(n log n)
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 30 / 40
Problem complexity
There may be many different algorithms for solving a problem.
When we find an algorithm for solving the problem, we have an upper bound on the complexity of the problem.
To verify whether an algorithm is the best possible, it is useful to find a lower bound for the minimum number of operations required.
A lower bound can often be found using decision trees.
We cannot always determine what the lower bound is and there is often a gap between a lower bound and an upper bound.
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 31 / 40
Typical kinds of exam questions
Given a simple algorithm, can you determine how its time complexity function scales as a function of its inputs?
Given a time complexity function, how does the time required change when the input size is changed?
What is the maximum input n that can be run in a given time for a particular T(n)?
Given two algorithms with different complexity functions, for what values of n does it make sense to use the first algorithm?
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 32 / 40
Talking about time complexity . . .
Tractable problems: solvable in practice, and whose solutions are at worst polynomial in time.
For example: 1, log n, n, n log n, n2, n3
Intractable problems: are very difficult to solve in practice and the
time required grows exponentially with the size of input.
For example: 2n , n! , nn
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 33 / 40
Talking about time complexity . . .
1 Proven unsolvable (undecidable), e.g. the Halting problem.
2 Polynomial solutions found (tractable), e.g. searching, sorting.
3 Proven to need exponential time (intractable), e.g. Tower of Hanoi.
4 ??? Unknown if tractable or intractable, e.g. the travelling salesman problem, the Hamiltonian problem
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 34 / 40
Complexity classes
Decision problems are ones with a ‘yes’ or ‘no’ answer.
P is the set of decision problems which are solvable by
polynomial time algorithms
NP (non-deterministic polynomial) is the set of decision problems which are solvable in polynomial time by a non-deterministic algorithm
– a solution can be verifiable by polynomial time algorithms
All problems in P are also in NP, hence P ⊆ NP.
Does NP = P? We just don’t know!
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 35 / 40
P versus NP
Theorem (joke). P = NP Proof. Simply set N = 1. . .
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 36 / 40
P, NP, NP-complete/NP-hard problems
the definitions/examples of the classes
the basic properties of the problems from the classes how we can tackle them
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 37 / 40
Typical exam questions
Give some examples of tractable and intractable problems (provable or apparently).
Give the formal definitions of the complexity classes P, NP and NP-complete.
What is meant by a non-deterministic polynomial algorithm?
Discuss the consequences of P = NP. How might you prove or disprove it?
What are our options when we need to “solve” an NP-complete or NP-hard problem.
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 38 / 40
That’s it!!!
Good luck on the exam …
Hopefully everyone will pass on the first try, but if you do have to re-sit the exam, be sure to learn from your mistakes. Understand where you went wrong!
Good luck with your TB2!
And last but not least:
P.S. If you solve P versus NP please let me know 🙂
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 39 / 40
Be prepared for real life!
́ıkov ́a (SoC, UoP) THCS, Part B January, 2022 40 / 40
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com