# CS代考 Turing Machines: Limits of Decidability – cscodehelp代写

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

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?

A. This is linear. Think of finite automata.

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

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?

A. Probably not . . . this is the $1,000,000 Clayton math problem

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,ifthepathsv→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,ifthepathsv→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?

45/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