Computational Complexity Review

1. Turing Machines @ Automata by Jeff UllmanPermalink

1.1 IntroductionPermalink

Questions:

• How to show that certain tasks are impossible, or in some cases, possible but intractable?
  • Intractable means solvable but only by very slow algorithms
• What can be solved by computer algorithms?

Turing machine (TM):

• In some sense an ultimate automaton.
• A formal computing model that can compute anything we can do with computer or with any other realistic model that we might think of as computing.
• TMs define the class of recursively enumerable languages which thus the largest class of languages about which we can compute anything.
  • There is another smaller class called recursive languages that can be thought of as modeling algorithms–computer programs that answer a particular question and then finish.

1.2 DataPermalink

Data types:

• int, float, string, etc.
• But at another level, there is only one type $\Rightarrow$ string of bit.
  • It is more convenient to think of binary strings as integers.
• Programs are also strings and thus strings of bits.
  • The fact that programs and data are at heart the same thing is what let us build a powerful theory about what is not computable.

“The $i^{th}$ data”:

• Integers $\Rightarrow 1,2,3,\dots$
• “Data” can also be mapped to $1,2,3,\dots$ (with some tricks from coding or cryptography)
  • Then it makes sense to talk about “the $i^{th}$ data”
• E.g. “the $i^{th}$ string”:
  • Text strings (ASCII or Unicode) $\Rightarrow$ Binary strings $\stackrel{\text{encode}}{\Rightarrow }$ Integers
    • A small glitch: If you think simply of binary integers, then
      • $101$ $\Rightarrow$ “the $5^{th}$ string”
      • $0101$ $\Rightarrow$ “the $5^{th}$ string”
      • $00101$ $\Rightarrow$ “the $5^{th}$ string”
  • This can be fixed by prepending a $1$ to the string before converting to an integer. Thus,
    • $101$ $\Rightarrow$ “the ${13}^{th}$ string” ($1101=13$)
    • $0101$ $\Rightarrow$ “the ${21}^{st}$ string” ($10101=21$)
    • $00101$ $\Rightarrow$ “the ${37}^{th}$ string” ($100101=37$)
• E.g. “the $i^{th}$ proof”:
  • A formal proof is a sequence of logical expressions.
    • We can encode mathematical expressions of any kind in Unicode.
    • Convert expression to a binary string and then an integer.
  • Problems:
    • A proof is a sequence of expressions, so we need a way to separate them.
    • Also, we need to indicate which expressions are given and which follow from previous expressions.
  • Quick-and-dirty way to introduce special symbols into binary strings:
    1. Given a binary string, precede each bit by 0. E.g.:
       • $101$ becomes $010001$.
    2. Use strings of two or more $1$’s as the special symbols. E.g.:
       • Let $111$ mean “start of expression”
       • Let $11$ mean “end of expression”
  • E.g. $1110\underset{―}{1}0\underset{―}{0}0\underset{―}{1}111110\underset{―}{0}0\underset{―}{0}0\underset{―}{1}0\underset{―}{1}11=\underset{―}{101},\underset{―}{0011}$

1.3 Orders of infinityPermalink

• There aren’t more “data” than there are integers.
• While the number is infinite, you may aware that there are different orders of infinity, and the integers is of the smallest one.
  • E.g. there are more real numbers than there are integers, so there are more real numbers than there are “programs” (think of programs as data).
    • This immediately tells you that some real numbers cannot be computed by programs.

1.3.1 Finite setsPermalink

• A finite set has a particular integer that is the count of the number of members–the cardinality.
  • E.g. $\mathrm{card}(\{a,b,c\})=3$
• It is impossible to find a 1-to-1 mapping between a finite set and a proper subset of itself.

1.3.2 Infinite SetsPermalink

• Formally, an infinite set is a set for which there is a 1-to-1 mapping between itself and a proper subset of itself.
  • E.g. the positive integers $\{1,2,3,\dots \}$ is an infinite set.
    • There is a 1-to-1 mapping $1\mapsto 2,2\mapsto 4,3\mapsto 6,\dots$ between this set and a proper subset (the set of even integers).

1.3.3 Countable SetsPermalink

• A countable set is a set with a 1-to-1 mapping with the positive integers.
  • $\Rightarrow$ Hence, all countable sets are infinite.
• E.g. set of all integers:
  • $0\mapsto 1$
  • $-x\mapsto 2x$
  • $+x\mapsto 2x+1$
  • Thus, order is $0,-1,1,-2,2,-3,3,\dots$, i.e.
    • $1^{st}$ integer is $0$
    • $2^{nd}$ integer is $-1$
    • etc.
• E.g. set of binary strings, set of Java programs.
• E.g. pairs of integers
  • Order the pairs of positive integers first by sum, then by first component: $[1,1],[2,1],[1,2],[3,1],[2,2],[1,3],[4,1],[3,2],\dots ,[1,4],[5,1],\dots$
  • $[i,j]\mapsto f(i,j)=\frac{(i+j)(i+j-1)}{2}-i+1=\frac{(i+j-1)(i+j-2)}{2}+j$

1.3.4 EnumerationsPermalink

• An enumeration of a set is a 1-to-1 mapping between the set and the positive integers.
• Thus, we have seen enumerations for strings, programs, proofs, and pairs of integers.

1.3.5 Set of all languages over some fixed alphabetPermalink

Question: Are the languages over $\{0,1\}$ countable?

Answer: No. Proof by Diagonalization (a table of $m$ strings $\times$ $n$ languages):

Suppose we could enumerate all languages over $\{0,1\}$ and talk about “the $i^{th}$ language.”

Consider the language:

Clearly, $L$ is a language over $\{0,1\}$.

Thus, $L$ is the $j^{th}$ language for some particular $j$.

Let $x$ be the $j^{th}$ string. Is $x$ in $L$?

• If so, $x$ is not in $L$ by definition of $L$.
• If not, then $x$ is in $L$ by definition of $L$.

We have a contradiction: $x$ is neither in $L$ nor not in $L$, so our sole assumption (that there was an enumeration of the languages) is wrong. $◼$

This is really bad; there are more languages than programs:

• The set of all programs are countable
• The set of all languages are not countable

1.4 Turing-MachinePermalink

Turing-Machine Theory:

• One important purpose of the theory of Turing machines is to prove that certain specific languages have no membership algorithm.
• The first step is to prove certain languages about Turing machines themselves have no membership algorithm.
• Reductions are used to prove more common questions undecidable.

Picture of a Turing Machine:

• Finite number of states.
• Infinite tape with cells containing tape symbols chosen from a finite alphabet.
  • Tape head: always points to one of the tape cells.
• Action: based on the state and the tape symbol under the head, a TM can
  • change state
  • overwrite the current symbol
  • move the head one cell left or right

Why Turing Machines? Why not represent computation by C programs or something like that?

• You can develop a theory about programs without using Turing machines, but it is easier to prove things about TM’s, because they are so simple.
• And yet they are as powerful as any computer.
  • In fact, TMs are more powerful than any computer, since they have infinite memory
    • Yes, we could always buy more storage for a computer.
    • But the universe is finite so where are you going to get the atoms from which to build all of those discs?
    • However, once you accept that the universe is finite, the limitation doesn’t seem to be effecting what we can compute in practice.
    • So we are not going to argue that a computer is weaker than a Turing machine in a meaningful way.

1.4.1 Turing-Machine FormalismPermalink

A TM is typically described by:

1. A finite set of states, $Q$
2. An input alphabet, $\mathrm{\Sigma }$
   • symbol 和 alphabet 的关系是 $\text{symbol}\in \text{alphabet}$
3. A tape alphabet, $\mathrm{\Gamma }$
   • $\mathrm{\Sigma }\subseteq \mathrm{\Gamma }$
4. A transition function, $\delta$
5. A start state, $q_0\in Q$
6. A blank symbol, $B\in \mathrm{\Gamma }\setminus \mathrm{\Sigma }$
   • All tape except for the input is blank initially.
   • $B$ is never an input symbol.
7. A set of final states, $F\subseteq Q$

Conventions:

• $a,b,\dots$ are input symbols.
• $\dots ,X,Y,Z$ are tape symbols.
• $\dots ,w,x,y,z$ are strings of input symbols.
• $\alpha ,\beta ,\dots$ are strings of tape symbols.

Transition Function $\delta (q,Z)=(p,Y,D)$:

• Arguments:
  1. Current state $q\in Q$
  2. Current tape symbol $Z\in \mathrm{\Gamma }$
• Return value (when $\delta (q,Z)$ in not undefined):
  • $p$ is a state
  • $Y$ is the new tape symbol (to replace the current symbol on the tape head)
  • $D$ is a direction, $L$ or $R$

TM Example:

• Description:
  • This TM scans its input (all binary bits) left to right, looking for a 1.
  • If it finds 1, it changes it to a 0, goes to final state $f$, and halts.
  • If it reaches a blank, it changes it to a 1 and moves left.
• Formalism:
  • States $Q=\{q\text{(start)},f\text{(final)}\}$.
  • Input symbols $\mathrm{\Sigma }=\{0,1\}$.
  • Tape symbols $\mathrm{\Gamma }=\{0,1,B\}$.
  • $\delta (q,0)=(q,0,R)$.
  • $\delta (q,1)=(f,0,R)$.
  • $\delta (q,B)=(q,1,L)$.
• Example tape: $BB00BB$; starts from the first 0
  • $BB00BB$, $\delta (q,0)=(q,0,R)$, move right
  • $BB00BB$, $\delta (q,0)=(q,0,R)$, move right
  • $BB00BB$, $\delta (q,B)=(q,1,L)$, move left
  • $BB001B$, $\delta (q,0)=(q,0,R)$, move right
  • $BB001B$, $\delta (q,1)=(f,0,R)$, move right
  • $BB000B$, undefined, halt.

Instantaneous Descriptions of a Turing Machine:

• Initially, a TM has a tape consisting of a string of input symbols surrounded by an infinity of blanks in both directions.
• The TM is in the start state, and the head is at the leftmost input symbol.
• TM ID’s: (我觉得更合适的名字应该叫 TM State ID)
  • An ID is a string $\alpha q\beta$, where
    • $\alpha =$ string from the leftmost nonblank to tape head (exclusive)
    • $\beta =$ string from the tape head (inclusive) to the rightmost nonblanks.
      • I.e. the symbol to the right of $q$ is the one being scanned.
    • If an ID is in the form of $\alpha q$, it is scanning a $B$.
  • As for PDA’s (Pushdown automaton) we may use symbols
    • $I{D}_i⊢I{D}_j$ to represent “$I{D}_i$ becomes $I{D}_j$ in one move” and
    • $I{D}_i{⊢}^{\star }I{D}_j$ to represent “$I{D}_i$ becomes $I{D}_j$ in zero or more moves,”。
  • Example: The moves of the previous TM are $q00⊢0q0⊢00q⊢0q01⊢00q1⊢000f$
• Formal Definition of Moves:
  1. If $\delta (q,Z)=(p,Y,R)$, then
     • $\alpha qZ\beta ⊢\alpha Yp\beta$
     • If $Z$ is the blank $B$, then $\alpha q⊢\alpha Yp$
  2. If $\delta (q,Z)=(p,Y,L)$, then
     • For any $X$, $\alpha XqZ\beta ⊢\alpha pXY\beta$
     • In addition, $qZ\beta ⊢pBY\beta$

1.4.2 Languages of a TMPermalink

There are actually two ways to define the language of a TM:

• A TM defines a language by final state.
  • $L(M)=\{w|q_{0}w{⊢}^{\star }I,\text{where I is an ID with a final state}\}$
• Or, a TM can accept a language by halting.
  • $H(M)=\{w|q_{0}w{⊢}^{\star }I,\text{and there is no move possible from ID}I\}$

Equivalence of Accepting and Halting:

1. If $L=L(M)$, then there is a TM $M^{\prime }$ such that $L=H(M^{\prime })$.
2. If $L=H(M)$, then there is a TM $M”$ such that $L=L(M”)$.

Proof:

Final State => Halting:

• Modify $M$ to become $M^{\prime }$ as follows:
  1. For each final state of $M$, remove any moves, so $M^{\prime }$ halts in that state.
  2. Avoid having $M^{\prime }$ accidentally halt.
     • Introduce a new state $s$, which runs to the right forever; that is $\delta (s,X)=(s,X,R)$ for all symbols $X$.
     • If $q$ is not a final state, and $\delta (q,X)$ is undefined, let $\delta (q,X)=(s,X,R)$.

Halting => Final State:

• Modify $M$ to become $M”$ as follows:
  1. Introduce a new state $f$, the only final state of $M”$.
  2. $f$ has no moves.
  3. If $\delta (q,X)$ is undefined for any state $q$ and symbol $X$, define it by $\delta (q,X)=(f,X,R)$. $◼$

Recursively Enumerable Languages:

• We now see that the classes of languages defined by TM’s using final state and halting are the same.
• This class of languages (that can be defined in both those ways) is called the recursively enumerable languages.
  • Why this name? The term actually predates the Turing machine and refers to another notion of computation of functions.

Recursive Languages:

• A proper subset of Recursively Enumerable Languages.
• An algorithm formally is a TM accepting (a language) by final state that halts on any input regardless of whether that input is accepted or not.
  • 注意这里的逻辑，algorithm 是 TM 而不是 language.
• If $L=L(M)$ for some TM $M$ that is an algorithm, we say $L$ is a recursive language.
  • In other words, the language that is accepted by final state by some algorithm is a recursive language.
  • Why this name? Again, don’t ask; it is a term with a history.
• Example: Every CFL (Context-free language) is a recursive language.
  • By the CYK algorithm.

2. Decidability @ Automata by Jeff UllmanPermalink

Central Ideas:

• TMs can be enumerated, so we can talk about “the $i^{th}$ TM”.
  • Thus possible to diagonalize over TMs, showing a language that cannot be the language of any TM.
• Establish the principle that a problem is really a language.
  • Therefore some specific problems do not have TMs.

Binary-Strings from TM’s:

• We shall restrict ourselves to TM’s with input alphabet $\{0,1\}$.
• Assign positive integers to the three classes of elements involved in moves:
  1. States: $q_1$ (start state), $q_2$ (final state), $q_3$, etc.
  2. Symbols: $X_1$ (0), $X_2$ (1), $X_3$ (blank), $X_4$, etc.
  3. Directions: $D_1$ (L) and $D_2$ (R).
• Suppose $\delta (q_i,X_j)=(q_k,X_l,D_m)$.
• Represent this rule by string $0^i{10}^j{10}^k{10}^l{10}^m$. ($0^n$ 表示 $n$ 个连续的 $0$)
  • Key point: since integers $i,j,\dots$ are all $>0$, there cannot be two consecutive $1$’s in these strings.
• Represent a TM by concatenating the codes for each of its moves, separated by $11$ as punctuation.
  • That is: ${\text{Code}}_{1}11{\text{Code}}_{2}11{\text{Code}}_{3}11\dots$
  • Note: if bianry string $i$ cannot be parsed as a TM, assume the $i^{th}$ TM accepts nothing.

Diagonalization:

• Table of Acceptance (denoted by $A$):
  • TM $i=1,2,3,\dots$ $\times$ String $j=1,2,3,\dots$
  • $A_{ij}=0$ means the $i^{th}$ TM does not accept the $j^{th}$ string.
  • $A_{ij}=1$ otherwise.
• Construct a 0/1 sequence $D=d_1{d}_2\dots$, where $d_i=\overline{A_{ii}}$
  • $D$ cannot be a row in $A$.
  • Question: Let’s suppose $w=10101010\dots$. What does it mean if $w$ appears in the $i^{th}$ row of the table $A$?
  • Answer: It means the $i^{th}$ TM exactly accepts the $1^{st},3^{rd},5^{th},\dots$ binary strings.
• Let’s give a name to this language–the diagonalization language $L_d=\{w|w\text{ is the }{i}^{th}\text{ string, and the }{i}^{th}\text{ TM does not accept }w\}$.
• We have shown that $L_d$ is not a recursively enumerable language; i.e., it has no TM.
  • There are no more TMs than integers.
  • $L_d$ exists but we cannot always tell whether a given binary string $w$ is in $L_d$.

Problems:

• Informally, a “problem” is a yes/no (the output) question about an infinite set of possible instances (the input).
  • Example: “Does graph G have a Hamilton cycle (cycle that touches each node exactly once)?
  • Each undirected graph is an instance of the “Hamilton-cycle problem.”
• Formally, a problem is a language.
  • Each string encodes some instance.
  • The string is in the language if and only if the answer to this instance of the problem is “yes.”
• Example: A Problem About Turing Machines
  • We can think of the language $L_d$ as a problem.
  • 如果 table $A$ 的 string 是 TM 自身的 binary string 的话，这个 problem 就成了 “Does this TM not accept its own code?”

Decidable Problems:

• A problem is decidable if there is an algorithm to answer it.
  • Recall: An “algorithm,” formally, is a TM that halts on all inputs, accepted or not.
  • Put another way, “decidable problem” = “recursive language.”
• Otherwise, the problem is undecidable.

Bullseye Picture:

• 最中心的集合：Decidable problems = Recursive languages
• 外一圈：Recursively enumerable languages
  • Languages accepted by TMs with no guarantee that they will halt on inputs they never accept
  • Recursively enumerable languages $\supset$ Recursive languages
• 最外层：Not recursively enumerable languages，比如 $L_d$
  • Languages that have no TM at all.
  • Recursively enumerable languages 的补集

Examples: Real-world Undecidable Problems

• Can a particular line of code in a program ever be executed?
• Is a given context-free grammar ambiguous?
• Do two given CFG’s generate the same language?

The Universal Language:

• An example of a recursively enumerable, but not recursive language
• We call it $L_u$, of a universal Turing machine, or call it Universal TM language.
• UTM inputs include:
  • a binary string representing some TM $M$, and
  • a binary string $w$ for $M$
• UTM accepts $⟨M,w⟩$ if and only if $M$ accepts $w$.
• E.g. JVM
  • JVM takes a coded Java program and input for the program and executes the program on the input.

Designing the UTM:

• Inputs are of the form: $\text{Code–for–}M111w$
  • Note: A valid TM code never has $111$, so we can split $M$ from $w$.
  • The UTM must accept its input if and only if $M$ is a valid TM code and $M$ accepts $w$.
• UTM is a multi-tape machine:
  • Tape 1 holds the input $\text{Code–for–}M111w$
    • Tape 1 is never changed, i.e. never overwritten.
  • Tape 2 represents the current tape of $M$ during the simulation of $M$ with input $w$
  • Tape 3 holds the state of $M$.
• Step 1: The UTM checks that $M$ is a valid code for a TM.
  • E.g., all moves have five components, no two moves have the same state/symbol as first two components.
  • If $M$ is not valid, its language is empty, so the UTM immediately halts without accepting.
• Step 2: Assuming the code for $M$ is valid, the UTM next examines $M$ to see how many of its own tape cells it needs to represent one symbol of $M$.
  • How to do this: we discover the longest block of $0$s representing a tape symbol and add one cell to that for a marker (e.g. $\text{\#}$) between symbols of $M$’s tape.
  • Thus if say $X_7$ is the highest numbered symbol then we’ll use 8 squares to represent one symbol of $M$.
    • Symbol $X_i$ will be represented $i$ $0$s and $7-i$ blanks followed by a marker outside.
    • For example, here’s how we would represent $X_5$: $00000BB\text{\#}$.
• Step 3: Initialize Tape 2 to represent the tape of $M$ with input $w$, and initialize Tape 3 to hold the start state (always $q_1$ so it is represented by a single $0$).
• Step 4: Simulate $M$.
  • Look for a move on Tape 1 that matches the state on Tape 3 and the tape symbol under the head on Tape 2.
    • If we cannot find one then apparently $M$ halts without accepting $w$ so UTM does so as well.
  • If found, change the symbol and move the head on Tape 2 and change the State on Tape 3.
  • If $M$ accepts (i.e. halts), the UTM also accepts (i.e. halts).

Proof That $L_u$ is Recursively Enumerable (RE), but not Recursive:

• We designed a TM for $L_u$, so it is surely RE.
• Proof by contradiction:
  • Suppose $L_u$ were recursive, which means we could design a UTM $U$ that always halted.
  • Then we could also design an algorithm for $L_d$, as follows.
    • Given input $w$, we can decide if $w\in L_d$ by the following steps.
      1. Check that $w$ is a valid TM code.
         • If not, then $w$’s language is empty, so $w\in L_d$.
      2. If valid, use the hypothetical algorithm to decide whether $w111w$ is $\in L_u$.
      3. If so, then $w\notin L_d$; else $w\in L_d$.
  • But we already know there is no algorithm for $L_d$.
  • Thus, our assumption that there was an algorithm for $L_u$ is wrong.
  • $L_u$ is RE, but not recursive.

$◼$

这个证明需要好好解读与总结：

• 什么是 language?
  • TM $M$ 的 language $L_M=\{\text{tape (不算两端的 blank 区域)}|\text{TM 能从这个 tape 的起始点一直运行到一个 final state, i.e. halt}\}$
  • Tape 的本质是什么？是 string 呀
  • 我们说 TM $M$ accepts a language，那么同样也可以说 TM $M$ accepts a string，然后所有 $M$ accept 的 string 构成了 $M$ 的 language
• 什么是 algorithm?
  • algorithm 是个 TM, which always halts on any input regardless of whether that input is accepted or not
    • always halts 是什么意思？你可以理解为 “always generate an output”
      • accept 输出 1
      • reject 输出 0
    • 明显，infinite loop 不可能是一个 algorithm
• 什么是 problem?
  • problem is a language
• TM accept a language => algorithm accepts a problem
  • 但是我们一般不这么说，因为我们常用的说法是 algorithm solves a problem
  • 反过来，a problem is solved by algorithm，也就相当于 “我们可以为 problem 这个 language 找到一个 always halt 的 TM，即找到一个 algorithm”
    • 能找到 algorithm 的 problem => Decidable Problem, i.e. Recursive language
    • 能找到 TM (但不保证是 algorithm) 的 problem => Recursively enumerable language
      • 能找到 TM，但确定不是 algorithm 的 problem => The Universal Language
    • 连 TM 都找不到的 problem => Not recursively enumerable language
• $w$ 的两面性
  • 如果 TM $M$ 的 binary string 是 $w$，那么
    1. $w$ 可以表示 TM $M$
    2. $w$ 可以表示一个 plain string
  • 那么我们可以同时有 “$w$ accepts $w$” 和 “$w$ is accepted by $w$” 这两种逻辑
• $L_d$ 的两种解读
  • 首先它是个 language，然后 language 可以看做一个集合；然后 problem 也是 language，所以也把 $L_d$ 抽象成一个问题描述
  • 貌似默认是把 Acceptance table $A$ 的 string 限定为 TM 的 binary string 的话（相当于是 $w\times w$ 这样的一张表），那么：
    • $L_d=\{w|\text{TM }w\text{ does not accept string }w\}$
      • 你理解为 string 的集合或者 TM 的集合都行，因为 $w$ 的两面性
      • 原来的定义是 $L_d=\{w|w\text{ is the }{i}^{th}\text{ string, and the }{i}^{th}\text{ TM does not accept }w\}$，请自行体会一下是不是可以这么理解
    • $L_d$ is a problem “Does this TM not accept its own code?”
• If $w$ is not a valid TM code:
  • 有点无赖地，我们把这样的 $w$ 看做一种特殊的 TM
  • $w$’s language is empty
    • => $w$ accepts nothing
      • => $w$ cannot accept $w$
        • => $w\in L_d$
• $L_u$ 没有 algorithm 意味着什么？
  • 给定一个 $⟨M,w⟩$，没有 algorithm 确定是否有 $M$ accepts $w$
  • 还是回到 “$w$ accepts $w$” 这个逻辑上，然后我们可以把 $⟨w,w⟩$ 写成 $w111w$，所以针对这个输入，没有 algorithm 可以确定是否有 $w$ accepts $w$

3. Extensions and properties of Turing machines @ Automata by Jeff UllmanPermalink

17.1 Programming TricksPermalink

Programming Trick: Multiple Tracks

• Enable us to leave markers on the tape so TM can find their way back to an important place.
• If there are $k$ tracks => Treat each symbol as a vector of size $k$
  • E.g. $k=3$. $\left(\begin{array}{c}0\\ 0\\ 0\end{array}\right)$ represents symbol $0$; $\left(\begin{array}{c}B\\ B\\ B\end{array}\right)$ represents blank; $\left(\begin{array}{c}X\\ Y\\ Z\end{array}\right)$ represents symbol $[X,Y,Z]$

Programming Trick: Marking

• $k-1$ tracks for data; 1 track for marks
• Almost all tape cells hold blank in this mark track, but several hold special symbols (marks) that allow the TM to find particular places on the tape.
• E.g. $\left(\begin{array}{ccc}B& X& B\\ W& Y& Z\end{array}\right)$ represents an unmarked $W$, a marked $Y$ and an unmarked $Z$ ($X$ is a mark)

Programming Trick: Caching in the State

• Treat state as a vector.
• First component is the “control state,” i.e. the orginal state
• Other components are used as a cache to hold values the TM needs to remember.

例子待续

17.2 RestrictionsPermalink

Semi-infinite Tape: 待续

17.3 ExtensionsPermalink

Multitape TM:

• To simulate a $k$-Tape TM, use $2\times k$ tracks ($2\times k$ tracks 仍然视为一个 tape；$k$-Tape 是要有 $k$ 个 head 的)
• For every 2 tracks simulating 1 tape:
  • 1 track for tape data
  • 1 track for tape head (use mark $X$ to indicate the head position)
• 待续

Nondeterministic TM:

• Allow TM to have more than 1 choice of move at each step for any <state, symbol> pair.
  • Each choice is a <state,symbol,direction> triple, as for the deterministic TM.
• Simulating a NTM by a DTM: 待续

How a TM can simulate a store (a storage system that allow us to associate any value with any name):

• Very large stores => a significant factor in big-data world, like google's big table.
• 待续

17.4 Closure Properties of Recursive and RE LanguagesPermalink

待续

4. Specific undecidable problemsPermalink

Rice’s theorem: tells us that almost every question we can ask about the recursively enumerable languae is undecidable.

Properties of Languages:

• Any set of languages is a property of languages.
  • Example: The infiniteness property is the set of infinite languages.
  • If a language $L$ “has property infiniteness”, it means “$L\in \text{ property infiniteness}$”
  • In what follows, we’ll focus on properties of RE languages, because we can’t represent other languages by TM’s.
• We shall think of a property as a problem about Turing machines.
  • 我们可以认为 property $P=\{L|L\text{ has property }P\}$。从这个角度看，property 是一个关于 languages 的 language；进一步，property 是一个 problem。
    • 这个 problem 可以描述为：Given a language, does it have property $P$?
    • 那尽然 property 是一个 problem，我们就可以说 “property is decidable/undecidable”
  • 又因为 $L$ 可以由 TM 产生，所以我们进一步定义：For any property $P$, we can define a language $L_P$, the set of binary strings for TM $M$ such that $L(M)$ has property $P$.
    • 简单说就是 $L(M)\in P\Rightarrow M\in L_P$
    • 我们可以把 $L_P$ 视为这样的一个 problem：Given a code for a TM, does it define a language with that property $P$?
• There are two (trivial) properties $P$ for which $L_P$ is decidable.
  1. The always-false property, which contains no RE languages.
     • E.g. “this language is not RE.”
     • How do we decide this property? I.e. the algorithm for this property is: Given an input $w$, ignore it and say no (reject).
     • Empty language is a RE language.
  2. The always-true property, which contains every RE language.
     • E.g. “this language is RE.”
     • How do we decide this property? I.e. the algorithm for this property is: Given an input $w$, ignore it and say yes (accept).
• Rice’s Theorem: For every other (i.e. non-trivial) property $P$, $L_P$ is undecidable.

Reductions:

• A reduction from language $L$ to language $L^{\prime }$ is an algorithm (TM that always halts) that takes a string $w$ and converts it to a string $x$, with the property that: $x$ is in $L^{\prime }$ if and only if $w$ is in $L$.
• The value of having such a reduction is that it tells us $L$ is no harder than $L^{\prime }$, at least as far as decidability is concerned.
• TM’s as Transducers
  • We have regarded TM’s as acceptors of strings.
  • But we could just as well visualize TM’s as having an output tape, where a string is written prior to the TM halting.
• If we reduce $L$ to $L^{\prime }$, and $L^{\prime }$ is decidable, then the algorithm for $L$ + the algorithm of the reduction shows that $L$ is also decidable.
  • Normally used in the contrapositive (逆否命题).
  • If we know $L$ is not decidable, then $L^{\prime }$ cannot be decidable.
• More powerful forms of reduction: if there is an algorithm for $L^{\prime }$, then there is an algorithm for $L$.
  • E.g. we reduced $L_d$ to $L_u$
• More in NP-completeness discussion on Karp vs. Cook reductions
  • The simple reduction is called a Karp reduction.
  • More general kinds of reductions are called Cook reductions.

Proof of Rice’s Theorem

• Proof Skeleton
  • We shall show that for every nontrivial property $P$ of the RE languages, $L_P$ is undecidable.
  • We show how to reduce $L_u$ to $L_P$.
  • Since we know $L_u$ is undecidable, it follows that $L_P$ is also undecidable.
• The Reduction
  • The input to $L_u$, is a TM $M$ and an input $w$ for $M$. Then our reduction algorithm produces the code for a TM $M^{\prime }$.
  • Define property $P=“M\text{ accepts }w”$.
    • Thus $L(M^{\prime })$ has property $P$ if and only if $M$ accepts $w$.
      • “$L(M^{\prime })$ has property $P$” 也就意味着 “$M^{\prime }$ accepts a language with property $P$”
    • That is $M^{\prime }\in L_P$ if and only if $⟨M,w⟩\in L_u$.
  • $M^{\prime }$ has two tapes, used for:
    1. Simulates another TM $M_L$ on $M^{\prime }$’s own input, say $x$
       • The transducer (which in fact is $M$) does not deal with or see $x$
    2. Simulates $M$ on $w$.
       • Note: neither $M$, $M_L$, nor $w$ is input to $M^{\prime }$.
  • Assume that the empty language $\mathrm{\varnothing }$ does not have property $P$.
    • If it does, consider the complement of $P$, say $Q$. $\mathrm{\varnothing }$ then has property $Q$.
    • If we could prove that $Q$ are undecidable, then $P$ must be undecidable. That is if $L_P$ were a recursive language, then so would be $L_Q$ since the recursive languages are closed under complementation.
  • Let $L$ be any language with property $P$, and let $M_L$ be a TM that accepts $L$.
• Design of $M^{\prime }$
  1. On the second tape, $M^{\prime }$ writes $w$ and then simulate $M$ on $w$.
  2. If $M$ accepts $w$, then simulate $M_L$ on the input $x$ on the first tape.
  3. $M^{\prime }$ accepts its input $x$ if and only if $M_L$ accepts $x$, i.e. $x\in L$.
     • If $M$ does not accept $w$, $M^{\prime }$ never gets to the stage where it simulate $M_L$, and therefore $M^{\prime }$ accept nothing.
     • In this case, $M^{\prime }$ defines an empty language, which does not have property $P$.
  4. Suppose $M$ accepts $w$.
     • Then $M^{\prime }$ simulates $M_L$ and therefore accepts $x$ if and only if $x$ is in $L$.
     • That is, $L(M)=L$, $L(M^{\prime })$ has property $P$, and $M^{\prime }\in L_P$.
  5. Suppose $M$ does not accept $w$.
     • Then $M^{\prime }$ never starts the simulation of $M_L$, and never accepts its input $x$.
     • Thus, $L(M^{\prime })=\mathrm{\varnothing }$, and $L(M^{\prime })$ does not have property $P$.
     • That is, $M^{\prime }\notin L_P$.
  6. Thus, the algorithm that converts $M$ and $w$ to $M^{\prime }$ is a reduction of $L_u$ to $L_P$.
     • Thus, $L_P$ is undecidable.

5. Turing Machines @ Erickson §6Permalink

6.1 Why Bother?Permalink

Admittedly, Turing machines are a terrible model for thinking about fast computation; simple operations that take constant time in the standard random-access model can require arbitrarily many steps on a Turing machine. Worse, seemingly minor variations in the precise definition of “Turing machine” can have significant impact on problem complexity. As a simple example (which will make more sense later), we can reverse a string of n bits in $O(n)$ time using a two-tape Turing machine, but the same task provably requires $\mathrm{\Omega }(n^2)$ time on a single-tape machine.

But here we are not interested in finding fast algorithms, or indeed in finding algorithms at all, but rather in proving that some problems cannot be solved by any computational means. Such a bold claim requires a formal definition of “computation” that is simple enough to support formal argument, but still powerful enough to describe arbitrary algorithms. Turing machines are ideal for this purpose. In particular, Turing machines are powerful enough to simulate other Turing machines, while still simple enough to let us build up this self-simulation from scratch, unlike more complex but efficient models like the standard random-access machine.

(Arguably, self-simulation is even simpler in Church’s $\lambda$-calculus, or in Schönfinkel and Curry’s combinator calculus, which is one of many reasons those models are more common in the design and analysis of programming languages than Turing machines. Those models much more abstract; in particular, they are harder to show equivalent to standard iterative models of computation.)

6.2 Formal DefinitionsPermalink

• Three distinct special states $\{\text{start},\text{accept},\text{reject}\in Q\}$.
• A transition function $\delta :(Q\setminus \{\text{start},\text{reject}\})\times \mathrm{\Gamma }\to Q\times \mathrm{\Gamma }\times \{-1,+1\}$.

7. Turing Machines @ Computational Complexity by Mike RosulekPermalink

Languages and UTM (Lecture 1 & 2)Permalink

Language:

• A language is a subset of $\{0,1{\}}^{\star }$ (actually it could be any subset of $\{0,1{\}}^{\star }$)
• A language $L$ is a set of “yes-instances”
  • $x$ is a “yes-instance” if $x\in L$
• Language $S$ is Turing-recognizable (“recursively enumerable / r.e.”) if $\mathrm{\exists }$ TM $M$, such that $\mathrm{\forall }x$
  • $x\in S\Rightarrow M$ accepts $x$
  • $x\notin S\Rightarrow M$ rejects $x$ or runs forever
• Language $S$ is Turing-decidable (“recursive”) if $\mathrm{\exists }$ TM $M$, such that $\mathrm{\forall }x$
  • $x\in S\Rightarrow M$ accepts $x$
  • $x\notin S\Rightarrow M$ rejects $x$
• An algorithm formally is a TM which
  1. halts on any input regardless of whether that input is accepted or not, and
  2. accepts (a language) by final state
• In other words, language $S$ is Turing-decidable (“recursive”) if $\mathrm{\exists }$ an algorithm for $S$.
• If $M$ is a TM, define $L(M)=\{x|M\text{ accepts }x\}$

Programming conventions:

• Programming a TM for real is cruel!
• Describe a TM “program” in terms of tape modifications & head movements
• “Mark” cells on the tape (e.g., $a\to \acute{a}$)

E.g. TM algorithm for $\text{Palindromes}=\{x|x=reverse(x)\}$:

1. “Mark” first char (e.g., $O\to \mathrm{\varnothing }$), remember that char in internal state
2. If char to the right is “marked” or blank, then accept; else scan right until blank or a “marked” char
3. If $\text{prev char}\ne \text{remembered char}$, reject; else mark it
4. Scan left to leftmost unmarked char; if no more unmarked chars, accept; else repeat from step #1

Universal Machines:

• TMs can be encoded as strings (“code is data”)
  • Convention: every string encodes some TM
  • $⟨M⟩$: encoding of a TM $M$
  • $⟨M,x⟩$: encoding of a TM $M$ and a string $x$
• $L_{acc}=\{⟨M,x⟩|M\text{ is a TM that accepts }x\}$ is Turing-recognizable (RE)
  • Suppose there such a TM $U$ that accept $⟨M,x⟩$, i.e. $U(⟨M,x⟩)=\text{yes}$.
  • $U\text{ accepts }⟨M,x⟩⟺⟨M,x⟩\in L_{acc}$.
  • In other words, $U$ recognizes $L_{acc}$, i.e. $L(U)=L_{acc}$
• TM $U$ can recognizes $L_{acc}$, which means it can simulate any TM $M$! Thus call it a “universal TM”

Design of Universal TM:

• On input $⟨M,x⟩$, use 3 tapes:
  • one for description of $M$
  • one for $M$’s work tape contents
  • one for $M$’s current state
• Transitions: $⟨\text{state, char, newstate, newchar, direction}⟩$
• Legal to say “simulate execution of $M$ on input $x$” in our TM pseudocode! – If $M$ halts on $x$, the simulation will also halt – “Simulate execution of $M$ on input $x$ for $t$ steps” also possible (always halts)
  • Can simulate $t$ steps of a TM in $O(t\log t)$ steps

Diagonalization and Reduction (Lecture 2 & 3)Permalink

Diagonalization:

• $L_{acc}=\{⟨M,x⟩|M\text{ is a TM that accepts }x\}$ is not Turing-decidable (“recursive”)
  • Likewise, $L_{halt}=\{⟨M,x⟩|M\text{ is a TM that halts }x\}$
• 这里的 $L_{acc}$ 即前面 Jeff Ullman 的 $L_u$

(Turing) Reductions:

• Motivation:
  • Let’s not use diagonalization technique every time to prove something undecidable!
  • Instead, “reduce” one problem to another.
• What does “Alg decides lang” mean?
  • Language $L=\{x|x\text{ is/satisfies blab blah blah}\}$ is a collection of yes-instances.
    • An $x$ that is/satisfies “blab blah blah” is a yes-instance.
  • An algorithm is in nature a TM, so we can say “an algorithm $M$”.
  • If we say “$M$ decides $L$”, it means:
    • $L(M)=L$
    • Imagine $M$ as a function,
      • The datatype of the parameter to $M$ is the the one of the elements of $L$. E.g.
        • if $L=\{x|\dots \}$, elements are $x$’s. Therefore the function signature is $M(x)$;
        • if $L=\{⟨x,y⟩|\dots \}$, elements are $⟨x,y⟩$’s. Therefore the function signature is $M(⟨x,y⟩)$.
      • $M(x)=\text{yes}$ if $x$ is/satisfies “blab blah blah”
      • $M(x)=\text{no}$ otherwise
  • If we say “go find an algorithm for language”, it means:
    • go find an $M$ such that $L(M)=L$
    • go find an $M$ such that $M(x)=\text{yes}$ if $x$ is/satisfies “blab blah blah”
• Definition:
  • We say $L_1{\le }_T{L}_2$ (“$L_1$ Turing-reduces to $L_2$”) if there is an algorithm that decides $L_1$ using a (hypothetical) algorithm that decides $L_2$.
• Inference:
  • CASE 1: implication
    • Ground Truth: $L_2$ is decidable
    • Goal: To prove $L_1$ is also decidable
    • Method: Construct an algorithm $M_1$ for $L_1$ which satisfies $L_1{\le }_T{L}_2$
      • $L_2$ is decidable so there must exist an algorithm $M_2$ for $L_2$
      • Call $M_2$ inside $M_1$
      • In this way we prove that $L_1{\le }_T{L}_2$ holds.
  • CASE 2: contrapositive
    • Ground Truth: $L_1$ is undecidable
    • Goal: To prove $L_2$ is also undecidable
    • Method: Assume $L_2$ is decidable. Under this assumption, show we can construct an algorithm $M_1$ for $L_1$ which satisfies $L_1{\le }_T{L}_2$, i.e. $L_1{\le }_T{L}_2$ holds.
      • In this way we imply that $L_1$ is decidable.
      • However, we already know that $L_1$ is undecidable.
      • Therefore the assumption is invalid.
• E.g. show that $L_{empty}=\{⟨M⟩|M\text{ is a TM and }L(M)=\mathrm{\varnothing }\}$ is undecidable.
  • Choose $L_{acc}=\{⟨M,x⟩|M\text{ is a TM that accepts }x\}$ as $L_1$
  • $L_{empty}$ is $L_2$.
    • Assume there exists an algorithm $M_{empty}$.
  • Construct an algorithm $M_{acc}$ using $M_{empty}$:
    • Signature: $M_{acc}(⟨M,x⟩)$
    • For every single pair of input $⟨M_i,x_j⟩$:
      • Construct an TM $M_{ij}^{\star }(z)=\{\text{ignore }z;\text{return }{M}_i(x_j)\}$
        • 根据 $L_{acc}$ 的语义，$M_i$ 要么 accept $x_j$，要么 reject
        • CASE 1: If $M_i$ accepts $x_j$, $M_i(x_j)=\text{yes}$.
          • Therefore $M_{ij}^{\star }(z)=\{\text{ignore }z;\text{return yes}\}$.
          • I.e. $M_{ij}^{\star }$ accept every $z$.
          • I.e. $M_{ij}^{\star }$ accept everything.
          • I.e. $L(M_{ij}^{\star })=\mathrm{\Omega }$ (全集)
          • I.e. $⟨M_{ij}^{\star }⟩\notin L_{empty}$.
          • I.e. $M_{empty}(⟨M_{ij}^{\star }⟩)=\text{no}$.
        • CASE 2: If $M_i$ rejects $x_j$, $M_i(x_j)=\text{no}$.
          • Therefore $M_{ij}^{\star }(z)=\{\text{ignore }z;\text{return no}\}$.
          • I.e. $M_{ij}^{\star }$ rejects every $z$.
          • I.e. $M_{ij}^{\star }$ accept nothing.
          • I.e. $L(M_{ij}^{\star })=\mathrm{\varnothing }$
          • I.e. $⟨M_{ij}^{\star }⟩\in L_{empty}$.
          • I.e. $M_{empty}(⟨M_{ij}^{\star }⟩)=\text{yes}$.
      • If $M_{empty}(⟨M_{ij}^{\star }⟩)=\text{yes}$
        • I.e. $⟨M_{ij}^{\star }⟩\in L_{empty}$
        • 一路反推到 CASE 2，我们有 $M_i$ rejects $x_j$
        • 此时我们的 $M_{acc}(⟨M_i,x_j⟩)$ 要 return no
      • If $M_{empty}(⟨M_{ij}^{\star }⟩)=\text{no}$
        • I.e. $⟨M_{ij}^{\star }⟩\notin L_{empty}$
        • 一路反推到 CASE 1，我们有 $M_i$ accepts $x_j$
        • 此时我们的 $M_{acc}(⟨M_i,x_j⟩)$ 要 return yes
  • Now we showed $L_{acc}{\le }_T{L}_{empty}$. We assumed $L_{empty}$ is decidable, so $L_{acc}$ is also decidable, which is against the truth. Therefore the assumption is invalid and $L_{empty}$ is undecidable.
  • 最难的地方在 “Construct an algorithm $M_{acc}$ using $M_{empty}$” 这一步，请结合 $M_{acc}$ 和 $M_{empty}$ 综合考虑。一般的的套路是：
    • 根据 $L_1$ 的输入做一个临时变量，然后把这个临时变量当做 $L_2$ 的输入。
      • 这个临时变量要满足 $M_2$ 的 signature
      • 如果临时变量是一个 TM，比如上面的 $M_{ij}^{\star }$，在处理自身的输入 $z$ 时要见机行事
        • 如果能直接 $\text{return }{M}_i(x_j)$ 或者 $\text{return }!M_i(x_j)$ 无疑是最好的
        • 如果不能，考虑 $\text{if }{M}_i(x_j)=\text{yes},\text{return }function(z)$ 这样的形式
    • 然后根据 $L_2$ 的输出决定 $L_1$ 的输出。

// Reduce L_acc to L_empty
M_acc(<M_i,x_j>) {
	M*_ij = TurningMachine(z) {
		return M_i(x_j)
	}
	
	return !M_empty(M*_ij)
}

// General form of reduction algorithm for L_acc
M_acc(<M_i,x_j>) {
	M*_ij = TurningMachine(z) {
		if(M_i(x_j) = yes) {
			return f_1(z)
		} else {
			return f_2(z)
		}
	}
	
	return f_3(M_2(M*_ij))
}

Rice’s Theorem (Lecture 4)Permalink

Rice’s Theorem. $\{⟨M⟩|L(M)\text{ has property }P\}$ is undecidable if $P$ is non-trivial.

• Non-trivial means:
  • $\mathrm{\exists }$ $M_Y$ that $L(M_Y)$ has property $P$;
  • also $\mathrm{\exists }$ $M_N$ that $L(M_N)$ does not has property $P$.
  • I.e. “是否有 property $P$” 这个问题并不是永真或者永假

In other words, given encoding of $M$:

• Can’t decide whether $L(M)$ is empty
• Can’t decide whether some special $x\in L(M)$
• Can’t decide whether $L(M)$ is finite
• etc.

Define $L_P=\{⟨M⟩|L(M)\text{ has property }P\}$.

Claim. $L_{acc}{\le }_T{L}_P$.

Proof.

• By “non-trivial”:
  • Suppose $\mathrm{\varnothing }$ does not have property $P$.
  • $\mathrm{\exists }$ $M_Y$ that $L(M_Y)$ has property $P$.
• For every single pair of input $⟨M_i,x_j⟩$, construct an TM $M_{ij}^{\star }(z)$, such that on input $z$
  • If $M_i(x_j)=\text{yes}$
    • return $M_Y(z)$
  • else return No
• If $M_{ij}^{\star }\in L_P$, $M_{acc}(⟨M_i,x_j⟩)$ return Yes; else No
• 逻辑是：
  • If $M_i$ accepts $x_j$, $M_{ij}^{\star }$ 等价于 $M_Y$，此时 $M_{ij}^{\star }$ 应该具有 property $P$.
  • If $M_i$ rejects $x_j$, $M_{ij}^{\star }$ 等价于 $\mathrm{\varnothing }$，此时 $M_{ij}^{\star }$ 应该不具有 property $P$

$◼$

Kolmogorov Complexity (or, “optimal compression is hard!”) (Lecture 5 & 6) @ Algorithmic Information Theory and Kolmogorov ComplexityPermalink

Problem:

• 假设 compress $x$ 得到 $y$，decompress $y$ 得到 $x$
• 假设有一个 decompression algorithm $U$ that $U(y)=x$
• $K_U(x)=min\{|y||U(y)=x\}$
  • How small $x$ can be compressed?
  • Here $|y|$ denotes the length of a binary string $y$
• In other words, the complexity of $x$ is defined as the length of the shortest description of $x$ if each binary string $y$ is considered as a description of $U(y)$

Optimal decompression algorithm:

• The definition of $K_U$ depends on $U$.
• For the trivial decompression algorithm $U(y)=y$ we have $K_U(x)=|x|$.
• One can try to find better decompression algorithms, where “better” means “giving smaller complexities”

Definition 1. An algorithm $U$ is asymptotically not worse than an algorithm $V$ if $K_U(x)\le K_V(x)+C$ for some constant $c$ and for all $x$.

Theorem 1. There exists an decompression algorithm $U$ which is asymptotically not worse than any other algorithm $V$.

Such an algorithm is described as asymptotically optimal.

• The complexity $K_U$ with respect to an asymptotically optimal $U$ is called Kolmogorov complexity.
• Assume that some asymptotically optimal decompression algorithm $U$ is fixed, the Kolmogorov complexity of a string $x$ is denoted by $K(x)$ ($=K_U(x)$).
  • The complexity $K(x)$ can be interpreted as the amount of information in $x$ or the “compressed size” of $x$.

The construction of optimal decompression algorithm:

• The idea of the construction is used in the so-called “self-extracting archives”. Assume that we want to send a compressed version of some file to our friend, but we are not sure he has the decompression program. What to do? Of course, we can send the program together with the compressed file. Or we can append the compressed file to the end of the program and get an executable file which will be applied to its own contents during the execution.
• 待补充。

Basic properties of Kolmogorov complexity:

• 待补充。

Algorithmic properties of $K$

• 结合 Berry Paradox 补充

Complexity and incompleteness:

• 不懂

Algorithmic properties of $K$ (continued):

• 不懂

An encodings-free definition of complexity:

• 不懂

Axioms of complexity:

• 不懂

Kolmogorov Complexity (or, “optimal compression is hard!”) (Lecture 5 & 6) @ WikipediaPermalink

DefinitionPermalink

If $P$ is a program which outputs a string $x$, then $P$ is a description of $x$. The length of the description is just the length of $P$ as a character string, multiplied by the number of bits in a character (e.g. 7 for ASCII).

We could, alternatively, choose an encoding for Turing machines $⟨M⟩$. If $M$ is a Turing Machine which, on input $w$, outputs string $x$, then the concatenated string $⟨M⟩w$ is a description of $x$.

Any string $s$ has at least one description, namely the program:

function GenerateFixedString()
    return s

If a description of $s$, $d(s)$, is of minimal length (i.e. it uses the fewest bits), it is called a minimal description of $s$. Thus, the length of $d(s)$ (i.e. the number of bits in the description) is the Kolmogorov complexity of $s$, written $K(s)$. Symbolically, $K(s)=|d(s)|$.

Invariance theoremPermalink

Informal treatmentPermalink

Theorem. Given any description language $L$, the optimal description language is at least as efficient as $L$, with some constant overhead.

Proof: Any description $D$ in $L$ can be converted into a description in the optimal language by first describing $L$ as a computer program $P$ (part 1), and then using the original description $D$ as input to that program (part 2). The total length of this new description $D^{\prime }$ is (approximately): $|D^{\prime }|=|P|+|D|$.

The length of $P$ is a constant that doesn’t depend on $D$. So, there is at most a constant overhead, regardless of the object described. Therefore, the optimal language is universal up to this additive constant. $◼$

A more formal treatmentPermalink

Theorem. If $K_1$ and $K_2$ are the complexity functions relative to Turing complete description languages $L_1$ and $L_2$, then there is a constant $c$ – which depends only on the languages $L_1$ and $L_2$ chosen – such that

Proof: By symmetry, it suffices to prove that there is some constant $c$ such that for all strings $s$, $K_1(s)\le K_2(s)+c$.

Now, suppose there is a program in the language $L_1$ which acts as an interpreter for $L_2$:

function InterpretL2(string p)
    return p()

Running InterpretL2 on input p returns the result of running p.

Thus, if $P$ is a program in $L_2$ which is a minimal description of $s$, then InterpretL2(P) returns the string $s$. The length of this description of $s$ is the sum of

• The length of the program InterpretL2, which we can take to be the constant $c$.
• The length of $P$ which by definition $=K_2(s)$.

This proves the desired upper bound. $◼$

Basic resultsPermalink

In the following discussion, let $K(s)$ be the complexity of the string $s$.

Theorem. There is a constant $c$ such that $\mathrm{\forall }s,K(s)\le |s|+c$.

Theorem. There exist strings of arbitrarily large Kolmogorov complexity. Formally: for each $n\in \mathbb{N}$, there is a string $s$ with $K(s)\ge n$.

Proof: Otherwise all of the infinitely many possible finite strings could be generated by the finitely many programs with a complexity below $n$ bits. $◼$

Theorem. $K$ is not a computable function. In other words, there is no program which takes a string $s$ as input and produces the integer $K(s)$ as output.

Chain rule for Kolmogorov complexity:

It states that the shortest program that reproduces $x$ and $Y$ is no more than a logarithmic term larger than a program to reproduce $x$ and a program to reproduce $Y$ given $X$. Using this statement, one can define an analogue of mutual information for Kolmogorov complexity.

CompressionPermalink

A string $s$ is compressible by a number $c$ if it has a description whose length does not exceed $|s|-c$ bits. This is equivalent to saying that $K(s)\le |s|-c$. Otherwise, $s$ is incompressible by $c$.

A string incompressible by 1 is said to be simply incompressible––by the pigeonhole principle, which applies because every compressed string maps to only one uncompressed string, incompressible strings must exist, since there are $2^n$ bit strings of length n, but only $2^n-1$ shorter strings.

There are $2^n$ bitstrings of length $n$. The number of descriptions of length not exceeding $n-c$ is given by the geometric series:

There remain at least $2^n-2^{n-c+1}+1$ bitstrings of length $n$ that are incompressible by $c$. To determine the probability, divide by $2^n$.

Chaitin’s incompleteness theoremPermalink

We know that, in the set of all possible strings, most strings are complex in the sense that they cannot be described in any significantly “compressed” way. However, it turns out that the fact that a specific string is complex cannot be formally proven, if the complexity of the string is above a certain threshold.

Theorem. There exists a constant $L$ (which only depends on the particular axiomatic system and the choice of description language) such that there does not exist a string $s$ for which the statement

can be proven within the axiomatic system $s$.

Proof by contradiction using Berry’s paradox. 略

Time/space complexity classes: P & NP @ class (Lecture 7)Permalink

Resource bounds:

• $M$ has (worst case) running time $T$ if $\mathrm{\forall }$ string $x$, $M$ halts after at most $T(|x|)$ steps.
• $M$ has (worst case) space usage $s$ if $\mathrm{\forall }$ string $x$, $M$ writes on at most $S(|x|)$ tape cells.

Basic Complexity Class:

• $\text{DTIME}(f(n))=\{L|L\text{ decided by a (deterministic) TM with running time }O(f(n))\}$
  • $\text{D}$ for “deterministic”
  • Formally, $L\in TIME(f(n))$ if there is a TM $M$ and a constant $c$ such that
    1. $M$ decides $L$, and
    2. $M$ runs in time $c\cdot f$;
       • i.e., for all $x$ (of length at least 1), $M(x)$ halts in at most $c\cdot f(|x|)$ steps.
  • E.g. $\text{DTIME}(n^2)=\text{set of all problems that can be solved in quadratic time}$
• $\text{DSPACE}(f(n))=\{L|L\text{ decided by a TM that uses spaces }O(f(n))\}$
• Language / decision problem = set of strings (yes-instances)
• Complexity class = set of languages

Standard Complexity Classes:

• $\text{P}=\{\text{problems that can be solved (by a deterministical TM) in poly time}\}$
  • $\text{P}=\bigcup _{k=1,2,\dots }\text{DTIME}(n^k)$
    • 如果把 $P$ 看做 property 的话，$P$ 可以简单描述为 “deterministic poly time”
    • “deterministic” = “deterministically solvable in time” = “solvable in time by a deterministical TM”
• $\text{PSPACE}=\{\text{problems that can be solved using poly space}\}$ $\text{PSPACE}=\bigcup _{k=1,2,\dots }\text{DSPACE}(n^k)$
• $\text{EXP}=\{\text{problems that can be solved by in exponential time}\}$
  • $\text{EXP}=\bigcup _{k=1,2,\dots }\text{DTIME}(2^{n^k})$
• $\text{L}=\{\text{problems that can be solved using log space}\}$
  • $\text{L}=\text{DSPACE}(\log n)$

Translating from “Complexity Theory Speak”:

• Is $X\in \text{PSPACE}$?
  • Can problem $x$ be solved using polynomial space?
• Is $\text{PSPACE}\subseteq P$?
  • Can every problem solvable in polynomial space also be solved in polynomial time?
• This is true: $P\subseteq \text{PSPACE}$

Relationships between Complexity Classes:

• $\mathrm{\forall }f(n),\text{DTIME}(f(n))\subseteq \text{DSPACE}(f(n))$
  • This follows from the observation that a TM cannot write on more than a constant number of cells per move.
• If $f(n)=O(g(n))$, then $\text{DTIME}(f(n))\subseteq \text{DTIME}(g(n))$

Complementation @ Complement Classes and the Polynomial Time Hierarchy:

• 这里先声明下，全集可以表示为 $\mathrm{\Omega }$、$\sum ^{\star }$ 或者 $\{0,1{\}}^{\star }$
• The complement of a decision problem $\mathcal{L}$, denoted $co\mathcal{L}$, is the set of “No”-instances of $\mathcal{L}$.
  • 一般来说，我们可以认为 $co\mathcal{L}=\bar{\mathcal{L}}=\mathrm{\Omega }\setminus \mathcal{L}$
  • 严格来说，$\mathcal{L}\cup co\mathcal{L}=W{F}_{\mathcal{L}}\subseteq \mathrm{\Omega }$ where $W{F}_{\mathcal{L}}$ is the set of well-formed strings describing “Yes” and “No” instances. That is, $co\mathcal{L}=W{F}_{\mathcal{L}}-\mathcal{L}$.
    • 只是通常会限定 $W{F}_{\mathcal{L}}=\mathrm{\Omega }$
  • 举个例子:Every positive integer $x>1$ is either composite (合数) or prime (质数)
    • 如果限定 $\mathrm{\Omega }=W{F}_{\mathcal{L}}=\{x|x\text{ is a positive integer and }x>1\}$
      • $\mathcal{L}=\{x|x\text{ is prime }\}$
      • $co\mathcal{L}=\bar{\mathcal{L}}=\{x|x\text{ is not prime }\}=\{x|x\text{ is composite }\}$
    • 如果仅限定 $\mathrm{\Omega }=W{F}_{\mathcal{L}}=\{x|x\text{ is a positive integer }\}$
      • $co\mathcal{L}=\bar{\mathcal{L}}=\{x|x\text{ is not prime }\}\ne \{x|x\text{ is composite }\}$
      • 因为 1 既不是 prime 也不是 composite
• The complement of a complexity class is the set of complements of languages in the class.
  • $\mathcal{C}=\{\mathcal{L}|\mathcal{L}\text{ has complexity }\mathcal{C}\}$
  • $co\mathcal{C}=\{co\mathcal{L}|\mathcal{L}\in \mathcal{C}\}$
  • 注意 $co\mathcal{C}$ 和 $\bar{\mathcal{C}}$ 没有半毛钱的关系
    • $\bar{\mathcal{C}}=\{\mathcal{L}|\mathcal{L}\text{ does NOT have complexity }\mathcal{C}\}$
    • $co\mathcal{C}=\{\mathcal{L}|\mathcal{L}\text{‘s complement has complexity }\mathcal{C}\}$
      • $\mathcal{L}\text{‘s complement has complexity }\mathcal{C}$ 并不能说明 $\mathcal{L}\text{ has }\mathcal{C}\text{ or not}$
• Theorem 1. ${\mathcal{C}}_1\subseteq {\mathcal{C}}_2\Rightarrow co{\mathcal{C}}_1\subseteq co{\mathcal{C}}_2$
• Theorem 2. ${\mathcal{C}}_1={\mathcal{C}}_2\Rightarrow co{\mathcal{C}}_1=co{\mathcal{C}}_2$
• Closure under complementation means: $\mathcal{C}=co\mathcal{C}$
  • We say such class $\mathcal{C}$ are “closed under complementation”.
• Theorem 3. If $\mathcal{C}$ is a deterministic time or space complexity class, then $\mathcal{C}=co\mathcal{C}$.
  • E.g.
    • $co\text{TIME}(f(n))=TIME(f(n))$
    • $coP=P$
      • 翻译一下：如果 $\mathcal{L}$ can be solved by in poly time $\Rightarrow$ $co\mathcal{L}$ can also be solved by in poly time
      • vise versa
    • $co\text{PSPACE}=\text{PSPACE}$
  • Why? For any class $\mathcal{C}$ defined by a deterministic TM $M$, just switch accpet/reject behavior and you get a TM $coM$ that decide $co\mathcal{C}$
    • i.e. $M(\mathcal{L})=\text{yes}\Rightarrow coM(co\mathcal{L})=\text{yes}$, in the same bound of time or space.