CS代考 Turing Machines: Limits of Decidability

Turing Machines: Limits of Decidability
COMP1600 / COMP6260
Australian National University
Semester 2, 2020

Efficient Computation
‘$
All problems
􏲑􏰐 􏲉􏲇
􏲒􏲈 􏲌􏰑
Feasible problems
Computable problems
Each of the inner sets is a tiny proportion of the set that contains it.
&T% T
1/47

Time Complexity
Q. It’s good about solving problems in general. How about efficiency? Inverting booleans. Easy: constant time.
Multiplication of integers. Easy: polynomial time
takes time that is proportional to the square of the total number of digits
if we double the digits, it takes 4 times as long.
if n are the total number of digits, multiplication has complexity of the order n2.
Matrix Multiplication. Polynomial, of order n2.376
Theorem Proving. Hard, sometimes of order 22n (or even undecidable)
Feasible Problems.
can be solved in polynomial time, i.e. in time of the order nk, for some k
n is the length of (the representation of) the input.
2/47

P vs. NP: Signpost
Polynomial Time. The complexity class P
problems (languages) that can be decided in the order of nk steps usually considered feasible
Non-deterministic polynomial time. The complexity class NP
problems that can be decided with guessing in polynomial time alternatively, problems whose solutions can be verified in polytime
Example. Boolean satisfiability is in NP
given boolean formula A, can A evaluate to T?
can guess solution (assignment)
alternatively, can verify correctness of assignment in polynomial time
As a slogan. Coming up with a solution within a time bound seems intuitively harder than checking someone else’s solution in that time.
Big Open Problem. Is P = NP?
most important open problem in our discipline 1, 000, 000 prize by the Clay maths foundation
3/47

More Detail
Computational Problem.
given by a Language L, say Question: for a string w, is w ∈ L?
Solution. A Turing machine M that always halts
and accepts w if and only if w ∈ L.
Time Complexity.
Given w, can count the number of steps of M to termination this defines a function f (w ) dependent on the input
4/47

Time Complexity – Abstraction
Problem. Number of steps function usually very complicated for example, n17 + 23n2 − 5
and hard to find in the first place.
Solution. Consider approximate number of steps focus on asymptotic behaviour
as we are only interested in large problems
. for f and g functions on natural numbers
f ∈O(g)if∃c.∃n0.∀n≥n0(f(n)≤c·g(n))
“for large n, g is an upper bound to f up to a constant.”
Idea. Abstract details away by just focussing on upper bounds e.g. n17 + 23n2 − 5 ∈ O(n17)
5/47

: Examples
Examples.
Polynomials: leading exponent dominates e.g. xn + lower powers of x ∈ O(xn)
Exponentials: dominate polynomials e.g. 2n + polynomial ∈ O(2n)
Important Special Cases.
linear. f is linear if f ∈ O(n)
polynomial. f is polynomial if f ∈ O(nk ), for some k exponential. f is exponential if f ∈ O(2n)
6/47

Important Special Cases, Graphically
(Image copyright )
7/47

Application to Computational Problems
Definition.
A computational problem (given by a language L) is in O(f ) if there is a Turing machine M that
always terminates, and accepts precisely all strings in L
on every input string of length n, terminates in g(n) steps and g ∈ O(f )
Example: Regular Languages
Given: regular language L
Question: what’s the complexity of deciding whether w ∈ L?
More Detail.
need to construct a Turing machine that decides whether w ∈ L or not.
how many steps (depending on length of input string) does M take?
8/47

Example: Graph Connectedness
Reminder. A graph is a pair G = (V,E) where
V is the set of vertices of the graph
E is the set of edges, a collection of two-element subsets of V
Example.
Formally. G = (V , E ) with V = {0,1,2,3,4}
E consisting of {0, 2}, {0, 1}, {0, 3}, {1, 2}, {1, 3}, and {3, 4}. Note: Edges are not directional.
9/47

Connected and non-connected Graphs
Definition. A graph is connected if there is a path between any two nodes. Connected Graph Example.
Non-Connected Graph Example
10/47

The Connected Graph Problem
Problem. Given a graph G = (V,E) is G connected?
what is the complexity of deciding whether G is connected?
Algorithm.
Pick a vertex v in G as starting vertex
do a breadth-first search and remember vertices encountered
if the total number of vertices found equals the number of vertices in the graph, we know that G is connected.
By Church-Turing Thesis. The problem “Is G connected?” is clearly computable.
Q. How many steps does an algorithm take to figure this out? number of steps refers to “on a Turing machine”
but input to TMs are strings, not graphs . . .
11/47

Coding of Graphs as Strings
Recall. We have coded TM transition tables as strings.
Coding of graphs:
vertices: numbered 0 to n, can be coded by n in binary
single edge: pair (n,k), can be coded by 01…0#11…1. 􏰣􏰢􏰡􏰤 􏰣􏰢􏰡􏰤
nk set of edges: can be coded by e1##e2 . . . el−1##el
Complete Graph
10…11##11…1#10…0## …##11…0#11…0
green number of vertices blue set of edges
black separators
12/47

Question, reloaded.
Computational Problem. Given a graph G = (V , E ), how many steps does a TM take to determine whether the encoding of G is a connected graph?
the encoded graph is now a string
number of steps relative to the length of encoding
Difficulty. Exact answers require way too much bookeeping. Landau symbols O(·) allow us to be “generous” required answer of the form “in O(f )”.
13/47

Complexity Analysis
Algorithm in Turing machine form. pick vertex 0 initially.
designate vertex 0 as “to explore” (e.g by writing its binary encoding to the right of the input)
for every vertex v that is (still) to explore:
􏲓 search through the edges to find other vertices it connects with
􏲓 if a connected vertex is neither explored nor marked “to explore”, mark
it as “to explore” (e.g. by writing its binary encoding to the right of
the input, with a special separator)
􏲓 mark the vertex v as “explored”
check that the number of vertices found is equal to the number of vertices in the graph.
14/47

Worst Case Analysis
Worst Case for a given graph G with n vertices
When exploring a vertex, need to check n2 edges For every edge checked, one more vertex to explore this needs to be done for every vertex
High Level Analysis. Of complexity O(n3) – polynomial need to do n2 checks, at most n times
Overhead of a Turing implementation.
checking whether two vertices match: polynomial
􏲓 at most n (in fact, log n) bitwise comparisons
􏲓 and going back and forth over the tape, at most n2 · ntimes adding another vertex to the list: polynomial
􏲓 at most n bits to add
􏲓 and going back and forth over the tape, at most n2 · n steps
Summary. Polynomial Complexity polynomially many “high level” steps each of which takes polynomial time
15/47

Other Problems: Propositional Satisfiability
Given. A propositional formula, constructed from ∧, ∨, →, ¬, T, F and variables.
Question. Is there a truth value assignment to the propositional variables such that the formula evaluates to T?
Naive Algorithm. Truth tables
loop through all possible assignments and evaluate the formula
Questions.
1. How many truth assignments do we need to check? 2. How do we measure the size of the input?
3. What is the worst case complexity of this algorithm?
16/47

Complexity Class: Polynomial Time
Definition. The class P of polynomial time decision problems consists of all problems that can be answered in time polynomial in the input
of order O(n), O(n2), O(n3), . . .
Examples.
check whether a graph is connected
check whether a list is sorted
check whether a propositional formula is true for a given valuation
Last Problem. Have two inputs
need only one line of the truth table according to the valuation given
17/47

Other Problems: Propositional Satisfiability
Given. A propositional formula, constructed from ∧, ∨, →, ¬, T, F and variables.
Coding.
have new tape symbols for ∧, →, etc.
assume that variables are numbered, encode in binary
Worst Case.
variables proportional to length of formula (e.g. p1 ∧ p2 ∧ p3 ∧ . . . ) exponentially many valuations
This Algorithm
at least exponential, e.g. O(2n) and in fact exponential
Q. Can we do better?
18/47

Propositional Satisfiability
Verifying whether a formula evaluates to T for an assignment takes polynomial time
Determining whether a satisfying assignment exists
takes exponential time
but if we could guess an assignment, it would be fast (polynomial)
Observation. The (coding of) a valuation is polynomially large in fact, shorter than the formula, a sequence of 0s and 1s
Non-Deterministic Machines (informally)
like non-deterministic finite automata: more than one transition
possible
propositional satisfiability: guess a valuation, then check
19/47

Complexity Class: Nondeterministic Polynomial Time
Definition. The class NP of non-deterministic polynomial time decision problems consists of all decision problems L that can be solved by a non-deterministic Turing machine in polynomial time
we don’t define this type of machine formally idea: can make guesses at every stage
accepts if the machine can move into final state
Alternative Characterisation L is in NP if, for every string w ∈ L there exists a certificate c such that
c is of polynomial length (in the length of w) determining whether c is a certificate for w ∈ L is in P
Example. Propositional Satisfiability
certificates are valuations
checking the formula under a valuation is polynomial
20/47

More Problems
The Independent Set Problem Assume you want to throw a party. But you know that some of your friends don’t get along. You only want to invite people that do get along.
As a Graph.
vertices are your mates
draw an edge between two vertices if people don’t get along
Problem. Given k ≥ 0, is ItnhedreapneindeepentdeSnet tset, i.e. a subset I of ≥ k
vertices so that
no two elements of I are connected with an edge.
• Independent set =
subset of vertices inducing no vertices
i.e. everybody in I gets along
• Problem: Given a graph and integer ,
Example of an indeipsetnhedrenatnsinetdeopfensdizeent2set of size ?
21/47

subset of vertices inducing no vertices • Problem: Given a graph and integer
,
?
Independent Set: Naive Algorithm
is there an independent set of size
loop through all subsets of size ≥ k
and check whether they are independent sets
Alternative Formulation using guessing: guess a subset of vertices of size ≥ k check whether it is an independent set
Complexity. Independent Set is in NP
represent subsets as bit-vectors (certificates) checking is polynomial
22/47

Vertex Cover
Vertex Cover Independent Set
Vertex Cover. Given a graph G = (V,E), a vertex cover is a set C of • has a vertex cover of size
• So
• VC is NP‐complete
vertices such that every edge in G has at least one vertex in C. has an independent set of size
Example.
reduces
IS is NP‐complete
if and only if
Vertex Cover
Independent Set
Vertex Cover Problem. Given a graph G = (V,E) and k ≥ 0, is there a vertex cover of size ≤ k?
Naive Algorithm.
search through all subsets of size ≤ k check whether it’s a vertex cover
23/47

Independent Set
From Independent Set to Vertex Cover
• has a vertex cover of size if and only if
Reductions. Use solutions of one problem to solve another problem has an independent set of size
Observation. Let G be a graph with n vertices and k ≥ 0. • So reduces
G hasav. c. ofsize≤k iffG hasani. s. ofsizen−k • VC is NP‐complete IS is NP‐complete
Vertex Cover Independent Set
Reduction. A polynomial reduction from decision problem A to decision problem B is a function f that transforms A-instances to B-instances and
w ∈ A ⇐⇒ f (w) ∈ B and f is computable in polynomial time Example. Vertex cover to independent set
(G , k ) 􏱹→ (G , n − k ) where n is the number of vertices of G
24/47

Reductions and Difficulty
Recall. A reduction from decision problem A to B is a polytime function f suchthatw∈A ⇐⇒ f(w)∈B.
Informally. If we can solve B, then we can also solve A Given w, is w ∈ A?
Compute f (w ), and decide whether f (w ) ∈ B
Q. If A is reducible to B, which of A and B is more “difficult”?
25/47

NP-Completeness
Q. What is the “hardest” or most difficult NP-problem?
A. It’s a problem that all other NP-problems can be reduced to
a solution would yield solutions to all NP-problems
recall that B is more difficult than A if A can be reduced to B
NP-Hardness and completeness.
A decision problem L is NP-hard if all other NP-problems can be
reduced to it.
A decision problem is NP-complete if it is NP-hard and in NP.
Hard Theorem. ( 1974) The propositional satisfiability problem is NP-complete
have seen that satisfiability is in NP
hard part: reduce all NP-problems to satisfiability.
26/47

The P vs NP Problem
Big Open Question. is P = NP or not?
Given that propositional satisfiability is NP-complete “all” it takes is to solve one problem efficiently!
Ramifications If P = NP …
could break public-key cryptography
this includes https-protocol!
could solve optimisation problems efficiently
lots of AI (learning) problems have fast solutions
27/47

Summary.
Undecidable Problems.
Problems for which we cannot find an algorithmic answer
most famous: halting problem – determine whether a computation terminates
Efficiently Solvable Problems.
usually identified with polynomial time, i.e P
More difficult Problems. Polynomial time with guessing complexity class NP, not considered feasible NP-complete problems, like propositional satisfiability
Open Problem. Is P = NP or not?
neither have proof nor counter-example
most important open problem in the discipline
28/47

Weighted Graphs
Definition. A weighted graph is an undirected graph where every edge is (additionally) labelled with a non-negative integer.
Formally: A weighted graph is a triple G = (V , E , l ) where
(V,E) is an undirected graph (with vertices V and edges E)
l : E → N is a labelling function that assigns a weight (or cost) to each edge.
Example.
Intuition.
the vertices can be locations
the edges indicate whether we can travel between two locations the labels indicate the cost of travelling between two locations
29/47

Travelling Between Two Nodes
Q. Given two vertices v1 and v2, what is the “cheapest” way of getting from v1 to v2?
In More detail.
as a computation problem: given vertices v1 and v2, find a cheapest path that connects v1 and v2
as a decision problem: given graph G and k ≥ 0, is there a path that connects vertices v1 and v2 of total cost ≤ k?
Q. Easy or hard? Solvable in polynomial time?
30/47

Dijkstra’s Algorithm
Main Idea.
to find a shortest path between v1 and v2, need to consider intermediate nodes
more general problem: shortest path between v1 and any vertex v2 a bit like breadth-first search
Data Structures. Given a start vertex s
cheapest[v]: For every vertex v, the “price” of the “cheapest” path from s to v
explored[v]: a boolean marker whether v has been explored
31/47

Algorithm Detail for source vertex s
Initialisation.
set cheapest[s] = 0, cheapest[v] = undef for v ̸= s set explored[v] = false, all v ∈ V
Iteration.
1. Select a vertex in v that is not explored and minimal:
􏲓 explored[v] = false
􏲓 cheapest[v] ≤ cheapest[w] for all w with explored[w] = false
2. for each vertex w that is adjacent to v:
􏲓 update,ifthepaths􏲔v→wischeaper,thatis
􏲓 if cheapest[v] + cost(v, w) ≤ cheapest[w]
􏲓 then cheapest[w] = cheapest[v] + cost(v, w)
3. mark v as explored: explored[v] = true
􏲓 once a node v is marked explored, cheapest[v] is the price of the
cheapest path from source to v
32/47

Dijkstra’s Algorithm: Correctness
Invariant. if E is the set of explored nodes, then
for e ∈ E, cheapest[e] is the cost of cheapest path from source to e for u ∈ V \ E , cheapest[u] is the cost of the cheapest path to u that only visits explored nodes.
True after Initialisation.
trivial, as all nodes are marked as unexplored
Invariant holds after every iteration.
pick minimal and unexplored node u
cheapest path from source to u cannot traverse unexplored nodes after (possible) update: cheapest is still minimal for paths through explored vertices
At End of Iteration.
cheapest[v] is cost of cheapest path from source to v
Recognise the While-Rule in Hoare Logic?
could formalise this in Hoare logic
here: Hoare-Logic as informal guidance principle
33/47

Dijkstra’s Algorithm: Complexity
Worst Case Focus.
need to explore all nodes
In Every Iteration
possibly update cheapest[v], for all vertices v
Overall Complexity for a graph with n vertices run through n iterations, in each iteration:
􏲓 find minimal unexplored vertex – n steps
􏲓 update cheapest[v] – n steps
so overall O(n2) steps
Low-Level Operations are “harmless” (polynomial) comparing two n-bit binary numbers
marking / checking explored status
34/47

Shortest Paths
Decision Problem. Given G,v1,v2 and k ≥ 0, is there a path of cost ≤ k from v1 to v2?
run Dijkstra’s algorithm and then check whether cheapest[v2] ≤ k Computational Problem Given G,v1 and v2, find the shortest path from v1
to v2
Dijkstra’s algorithm only gives cost paths needs to be re-constructed idea: remember penultimate nodes
35/47

Computing Shortest Paths
Initialisation.
set cheapest[s] = 0, cheapest[v] = undef for v ̸= s set explored[v] = false, all v ∈ V
set penultimate[v] = undef, all v ∈ V
Iteration.
1. Select a vertex in v that is not explored and minimal:
􏲓 explored[v] = false
􏲓 cheapest[v] ≤ cheapest[w] for all w with explored[w] = false
2. for each vertex w that is adjacent to v:
􏲓 update,ifthepaths􏲔v→wischeaper,thatis
􏲓 if cheapest[v] + cost(v, w) ≤ cheapest[w]
􏲓 then cheapest[w] = cheapest[v] + cost(v, w) 􏲓 and put penultimate[w] = v
3. mark v as explored: explored[v] = true
􏲓 once a node v is marked explored, cheapest[v] is the price of the
cheapest path from source to v
36/47

Path Reconstruction
Idea.
Reconstruction of a path from source to v
initialisation: the last node is v iteration: path expansion on the left
􏲓 if partial path v1 , . . . , vn is already constructed
􏲓 extend it to penultimate[v1], v1, . . . , vn
termination: if the constructed path is of the form source, . . . , vn
Complexity.
reconstruction phase: at most n additional steps iteration phase: adds constant overhead
so overall, still polynomial
How About Coding Graphs as Strings?
our analysis in terms of number of vertices bounded above by length of encoding
penultimate[v] is the penultimate node of a cheapest path from source to v
37/47

Travelling Salesman Problem
Given. A weighted undirected graph vertices represent cities
edges represent travel time
Q.Findapathv1 →v2 →···→vn →v1
that begins and ends in the same city
that visits each city exactly once
for which the overall travel time is minimal.
Q. Easy or hard? Solvable in Polytime?
38/47

Travelling Salesman: Naive Approach
Naive Algorithm Given n cities, and their distances dist(c, d)
initialise: construct set S consisting of all possible sequences of nodes
􏲓 sequences may not have repeated vertices
􏲓 sequences must contain all vertices of the graph
computation phase:
for each s = (c1,…,cn) ∈ S, compute the total distance
􏰊i dist(ci, cj)
report the smallest such distance
Q. What is the complexity of this algorithm?
39/47

Travelling Salesman: Naive Approach
Counting Permutations of n vertices
n possibilities for 1st city, n−1 for 2nd, n−2 for third … overall: n! different paths to check
Estimate on a machine that does 1,000,000 steps per second
simplified: this does not include overhead for moving on Turing tapes
size
time
20
7
40
2.6 · 1031
80
2.3 · 10102
Q. What is the unit of time in the right-hand column? (we have seen this before)
40/47

Travelling Salesman as Decision Problem
Travelling Salesman as Decision Problem. Given weighted graph G and k ≥ 0, is there a path that
visits each vertex in G exactly once is of total cost ≤ k
Guessing and Checking.
Certificate for existence of path is path itself
of polynomial size (if G is encoded “reasonably”, i.e at least one bit per vertex)
Certificate Checking. As for Hamiltonian paths, plus check that the total cost of the path is ≤ k
n − 1 additions, one comparison – polynomial so checking is polynomial, overall
Corollary. Travelling Salesman as a decision problem is in NP.
41/47

The Knapsack Problem
Given. A knapsack with maximal capacity C, and items with weights w1,…,wn and values v1,…vn
What’s the best way to fill the knapsack?
sum of the weight of the items shouldn’t exceed capacity sum of the values of the items should be maximal.
Assumptions.
all weights are strictly positive, i.e. wi > 0 for all i = 1,…,n there is an unlimited supply of each item
42/47

Knapsack: Main Idea
Construct a Table
0 1 2…C m(0) m(1) m(2) … m(C)
m(w) = value of the “best” knapsack with weight w m(0) = 0 (empty knapsack)
m(w)=max{vi +m(w−wi)|wi ≤w}
Solution. m(C) – value of the best knapsack with capacity C
Correctness Argument.
the “best” knapsack with weight w must contain an item – say item i removing this item, we get the best knapsack with weight w − wi (otherwise, can have better knapsack with weight w)
Solution.
iteratively compute m(0), m(1), . . . , m(C )
store already computed values in a table (don’t recompute)
43/47

Knapsack: Complexity Analysis
Complexity Analysis given capacity C and n items
need to construct a table with C + 1 entries (starting at zero)
for each > 0 entry for weight: need to check n items, compute maximum
Overall complexity: n · C
Q. Does that mean that knapsack is linear or quadratic?
44/47

Knapsack: Encoding
Recall. Complexity depends on encoding of input data usual encoding for numbers: as binary strings
For Knapsack:
Capacity: C as a binary integer (log C bits) number of items n as binary integer (log n bits) weights as n-element lists of binary integers values as n-element lists of binary integers
Q. How large is C as a function of the length of the encoding of the knapsack problem in the worst case?
A. In the worst case:
one item, value 1, weight 1: 3 bits (plus separators)
encoding of C has log C many bits, so C = 2log C is exponential
Overall Complexity. Exponential in the size of the problem
if numbers are coded in binary
only polynomial if C is coded in unary – also called pseudo polytime 45/47

Summary
Bad News.
there are lots of problems that are undecidable about TMs Rice’s theorem gives plenty – any property of languages
But . . .
specific instances may be decidable often useful to search for solutions
Example. Provability in First-Order Logic
not decidable, but there are plenty of implementations implementations may not terminate . . .
goal: try and solve as many problems as possible problem of interest: usually human-generated
46/47

Course Summary
Alignment
you can already do programming (functional / imperative)
Questions.
What do programs really do?
What is computation in general? What are the limits?
Answers.
use logic to formally describe systems functional programs: induction proofs imperative programs: Hoare logics computation in general: Turing machines
47/47

Related Posts