Chapter 3: The Church-Turing Thesis
3.1 Turing Machines
We are now to a much more powerful model, first proposed by Alan Turing in 1936, called Turing Machine.
Similar to a finite automaton but with an unlimited and unrestricted memory, a Turing Machine is a much more accurate model of a general purpose computer.
Definition
A TM (Turing Machine) is a 7-tuple, \( (Q,\Sigma,\Gamma,\delta,q_0,q_{accept},q_{reject})\), where \( Q,\Sigma,\Gamma\) are all finite sets and
- Q is the set of states,
- \( \Sigma\) is the input alphabet not containing the blank symbol \( \sqcup\),
- \( \Gamma\) is the tape alphabet, where \( \sqcup \in F\) and \( \Sigma \subseteq \Gamma\),
- \( \delta:\ Q \times \Gamma \longrightarrow Q \times \Gamma \times \{L,R\}\) is the transition function,
- \( q_0 \in Q\) is the start state,
- \( q_{accept} \in Q\) is the accept state, and
- \( q_{reject} \in Q\) is the reject state, where \( q_{reject} \neq q_{accept}\).
Computation
Configuration
As a Turing machine computes, changes occur in the current state, the current tape contents, and the current head location.
A setting of these three items is called a configuration of the Turing machine.
Say that configuration \(C_1\) yields configuration \(C_2\) if the Turing machine can legally go from \(C_1\) to \(C_2\) in a single step:
\( uaq_ibv \quad \text{yields} \quad uacq_jv\),
if \( \delta(q_i,b) = (q_j,c,R)\).
The start configuration of M on input w is the configuration \(q_0w\).
In an accepting configuration, the state of the configuration is \(q_accept\).
In an rejecting configuration, the state of the configuration is \(q_reject\).
Accepting and rejecting configuration are halting configuration and do not yield further configurations.
Recognize and Decide
A Turing machine M accepts input w if a sequence of configuration \(C_1,C_2,\dots,C_k\) exists, where
1. \(C_1\) is the start configuration of M on input w,
2. each \(C_i\) yields \(C_{i+1}\), and
3. \(C_k\) is an accepting configuration.
The collection of strings that M accepts is the language of M, or the language recognized by M, denoted L(M).
Call a language Turing-recognizable if some Turing machine recognizes it. (is also called a recursively enumerable language)
Call a Turing machine decider if the machine halts on all inputs.
A decider that recognizes some language also is said to decide that language.
Call a language Turing-decidable or simply decidable if some Turing machine decides it. (is also called a recursive language)
简单的说，recognizers可能会被某些输入弄得死循环，永远都无法accept或reject，而deciders则不会
那么问题来了，怎么判断一台机器是不是在死循环呢？可能下一秒它就停机了，也可能永远都不停,这就是大名鼎鼎的停机问题了
Compared with Finite Automata
Turing machines have the following differences:
- unrestricted access to unlimited memory.
- A Turing machine can both write on the tape and read from it.
- The read-write head can move both to the left and to the right.
- The tape is infinite.
- The special states for rejecting and accepting take effect immediately.
Terminology for describing Turing Machines
The lowest level is the formal description that spells out in full the Turing machine’s states, transition function, and so on.
The higher level is the implementation description, in which we use English prose to describe the way that the Turing machine moves its head and the way that it stores data on its tape. At this level we do not give details of states or transition function.
The highest level is the high-level description, wherein we use English prose to describe an algorithm, ignoring the implementation details. At this level we do not need to mention how the machine manages its tape or head.
（当输入是一个对象，而不是一个字串的时候：
需要先把对象转化成字串 (notation: <O> or <\( O_1,O_2,\dots,O_k\)>)
A Turing machine may be programmed to decode the representation so that it can be interpreted in the way we intend.）
最低级那个有点像 CPU 微指令，直接控制机器
再高一级那个有点像汇编语言，间接控制机器
最高级那个有点像伪代码，体现的是算法思路
（可以放心这样做是因为有丘奇——图灵命题）
3.2 Variants of Turing Machines
Alternative definitions of Turing Machines abound, including versions with multiple tapes or with nondeterminism.
They are called variants of the Turing machine model.
However, the original model and its reasonable variants all have the same power–they recognize the same class of languages.
We call this variance to certain change in the definition robustness.
Both finite automata and pushdown automata are somewhat robust models, but Turing machines have an astonishing degree of robustness.
Multitape Turing Machines
Transition Function
\( \delta:\ Q \times \Gamma^k \longrightarrow Q \times \Gamma^k \times \{L,R,S\}^k\).
\( \delta(q_i,a_1,\dots,a_k) = (q_j,b_1,\dots,b_k,L,R,\dots,L)\)
where k is the number of tapes.
Equivalence with Turing Machines
Nondeterministic Turing Machines
Transition Function
\( \delta:\ Q \times \Gamma \longrightarrow P(Q \times \Gamma \times \{L,R\})\).
Equivalence with Turing Machines
首先，非确定性图灵机会生成一个决策树，不同的分支对应不同的选择
所以证明的总体思路就是要把决策树跑一遍，每种决策都试一下
但是非确定性图灵机有可能会在某些分支陷入死循环
如果用 DFS，则可能会在某个分支直接陷入死循环，而把其他分支忽略了
其实，我们要的仅仅是能让确定性图灵机在有限步内把非确定性图灵机 accept 的结点跑一遍
所以，可以用 BFS，层次遍历，先跑计算次数少的结点，再跑计算次数多的结点
Enumerators
Definition
As we mentioned earlier, some people use the term recursively enumerable language for Turing-recognizable language.
That term originates from a type of Turing machine variant called an enumerator.
Loosely defined, an enumerator is a Turing machine with an attached printer.
The enumerator can use that printer as an output device to print strings at any time.
The language enumerated by E is the collection of all the strings that it eventually prints out.
Equivalence with Turing Machines
say that we have an enumerator E, A Turing machine M.
E \( \longrightarrow\) M:
M = “On input w:
1.Run E. Every time that E outputs a string, compare it with w.
2.If w ever appears in the output of E, accept.”
E \( \longleftarrow\) M:
Say that \(s_1, s_2, s_3, \dots\) is a list of all possible strings in \(\Sigma^*\).
E = “Ignore the input.
1.Repeat the following for i = 1, 2, 3, \( \dots\)
2.Run M for i steps on each input, \( s_1,s_2,\dots,s_i\).
3.If any computations accept, print out the corresponding sj.”
在 M 里面 run E，和在 E 里面 run M，似乎有点不可思议，毕竟我们是在证 M 与 E 的等价性
但其实上述证明体现的只是思路，具体实现顺着这个思路也不难想出
Equivalence with other models
The above variants all share the essential feature of Turing machines–namely, unrestricted access to unlimited memory–distinguishing them from weaker models such as finite automata and pushdown automata.
Remarkably, all models with that feature turn out to be equivalent in power, so long as they satisfy reasonable requirements.
For example, one requirement is the ability to perform only a finite amount of work in a single step.
3.3 The Definition of Algorithm
The Church-Turing Thesis
The intuitive concept may have been adequate for giving algorithms for certain tasks, but it was useless for showing that no algorithm exists for a particular task. Proving that an algorithm does not exist requires having a clear definition of algorithm.
The definition came in the 1936 papers of Alonzo Church and Alan Turing. Church used a notational system called the λ-calculus to define algorithms. Turing did it with his “machines.” These two definitions were shown to be equivalent. This connection between the informal notion of algorithm and the precise definition has come to be called the Church–Turing thesis.
Hilbert’s tenth problem
