第8章 空间复杂性 (学生讨论用ＰPT 素材)
作为教学科研的基本训练的一个重要环节，学生应该能根据教材，作出有自己特色的PPT 发言稿. 这里提供一些素材，试图减小学生的工作难度。
PPT 不能仅仅是剪报。一份好的讨论班PPT 应该有同学的理解和创新.
(素材节选自教材 但不能代替教材)
从素材作PPT 一般 需要用 读 --减 ---加 三个过程。
（a ） 先充分阅读理解 教材，
（b ） 从此素材中删去次要语句，
（c ） 增加自己的心得，理解方法，解释和图形。
PPT 应该突出思路，突出要点, 适当的比喻可以帮助理解。
定义8.1 令M 是—个在所有输入上都停机的确定型图灵机。M 的空间复杂度(space complexity ) 是一个函数f ：N →N ，其中f (n )是M 在任何长为n 的输入上扫描带方格的最大数。若M 的空间复杂度为()n f ，则称M 在空间()n f 内运行。
定义8.2 令f ：N →R +是一个函数。空间复杂性类SPACE （()n f ）和NSPACE （()n f ）定义如下：
SPACE(()n f ) = {L |L 是被O(f (n ))空间的确定型图灵机判定的语言}
NSPACE(()n f ) = {L |L 是被O(f (n ))空间的非确定型图灵机判定的语言}
例8.3 第7章介绍了NP 完全问题SAT ，现在证明用线性空间算法能求解SAT 问题。因为SAT 是NP 完全的，所以SAT 不能用多项式时间算法求解，更不能用线性时间算法求解。因为空间可以重用，而时间不能，所以空间的能力显得比时间强得多。
M l ＝“对输入＜φ＞，φ是布尔公式：
1）对于φ中变量x 1，x 2…，x m 的每个真值赋值
2） 计算φ在该真值赋值下的值。
3）若φ的值为l ，则接受；否则拒绝。”
显然机器M 1是在线性空间内运行，这是因为每一次循环都可以复用带子上的同一部分。该机器只需存储当前的真值赋值，则只需要消耗O (m )空间。因为变量数m 最多等于输入长度n ，所以该机器在空间O (n )内运行。
例8.4 这个例子分析了一个语言的非确定性空间复杂性。在下一小节将说明测定非确定性空间复杂性后，对于测定它的确定性空间复杂性是有很大帮助的。下面分析判定一个非确定型有穷自动机是否接受所有字符串的问题。令
(){}
*=><=∑A L NFA A |A ALL NFA 且是一个
首先给出一个非确定型线性空间算法来判定该语言的补NFA ALL 。算法的思想是非确定性猜测一个被NFA 拒绝的字符串，然后用线性空间跟踪该NFA ，看它在特定时刻会处在什么状态。需要注意的是此时还不知道该语言是否在NP 或coNP 中。
N =“对于输入
1）置标记于NFA 的起始状态。
2）重复执行下面的语句2q 次，这里q 是M 的状态数。
3） 非确定地选择一个输入符号并移动标记到M 的相应状态，来模拟读取那
个符号。
4）如果步骤2步骤3表明M 拒绝某些字符串，即如果在某一时刻所有标记都不落在M 的接受状态上，则接受；否则拒绝。”
8.1 萨维奇定理
定理8.5萨维奇定理
对于任何1函数f ：N →R +，其中f (n )≥n ，
()()()()n f SPACE n f NSPACE 2
? 证明思路：需要确定地模拟一个)(n f 空间的NTM 。最简单的方法就是逐个地尝试NTM 的所有计算分支。这种模拟要求记录当前正在尝试的是哪一个分支，以便能够过渡到下一个分支。但是消耗)(n f 空间的一个分支可能运行))((2n f Ο步，每一步都可能是非确定的选择。顺序地考察每一个分支要求记录某个具体分支上所做的所有选择，以便能找到下一个分支。所以该方法可能会用掉))((2n f Ο空间，超过了))((2n f O 空间。
考虑到更具—般性的问题，这里采用了另一种不同的方法。给定NTM 的两个格局c 1和c 2，以及一个整数t ，要求判定该NTM 能否在t 步内从c 1变到c 2，称该问题为可产生性问题(yieldability problem )。如果令c 1是起始格局，c 2是接受格局，t 是非确定型机器所使用的最大步数，那么通过求解可产生性问题，就能够判定机器是否接受输入。
下面给出一个确定的递归算法来求解可产生性问题。它的运算过程为：寻找一个中间格局c m ，递归地检查c 1能否在t /2步内到达c m ，以及c m 能否在t /2步内到达c 2。重复使用两次递归检查的空间即可显著节省空间开销。
该算法需要用来存储递归栈的空间。递归的每一层需要()()n f O 空间来存储一个格局。递归的深度是log t ，这里t 是非确定型机器在所有分支上可能消耗的最大时间。因为))((2n f Οt =，所以log t=()()n f O 。因此确定的模拟过程需要()()n f O 2
空间。 证明 设N 是在空间f (n )内判定语言A 的NTM 。构造一个判定A 的确定型TM M 。机器M 使用过程CANYIELD ，该过程检查N 的一个格局能否在指定的步数内产生另一个格局，它求解了在证明思路中所描述的可产生性问题。
设w 是输入到N 的字符串。对于N 在w 上的格局c 1，c 2以及整数t ，如果
1在8.4节，证明只要f (n )≥log( n )萨维奇定理就能成立。
从格局c 1出发，N 有一系列非确定的选择能使它在t 步内进入格局c 2，则
()t c c C A N YI E LD 21，，输出接受，否则，CANYIELD 输出拒绝。
CANYIELD=“对输入c 1，c 2和t ：
1）若t ＝1，则直接检查是否有c 1＝c 2，或者根据N 的规则检查c 1能否在一步内
产生c 2。如果其中之一成立，则接受；如果两种情况都不成立，则拒绝。
2）若t ＞1，则对于N 在w 上消耗空间f (n )的每一个格局c m ：
3）运行()2t m ，，c c 1CANYIELD
4）运行()2t ，，c c 2m CANYIELD
5）若第3和第4步都接受，则接受。
6）若此时还没有接受，则拒绝。”
现在定义M 来模拟N 。首先修改N ，当它接受时，把带子清空并把读写头移到最左边的单元，从而进人称为c accept 的格局。令c start 是N 在w 上的起始格局。选一个常数d ，使得N 在)(n f 空间上的格局数不超过)(2n df ，其中n 是w 的长度。)(2n df 是N 在所有分支上的运行时间的上界。
M ＝“对输入w ：
1）输出()()n df accept start 2c c GANYIELD ，，的结果。
” 算法CANYIELD 显然求解了可产生性问题。因此M 正确地模拟了N 。下面需要分析M ，确信它在()()n f O 2
空间内运行。 CANYIELD 在递归调用自己时，它都把所处的步骤号、c 1、c 2和t 的值都存储在栈中，所以递归调用返回时能够恢复这些值。因此在递归的每一层需要增加()()n f O 空间。此外，递归的每一层把t 的值减小—半。开始时t 等于)(2n df ，所以递归的深度是O (log2d f (n))或))((n f O 。因此总共消耗的空间是()()n f O 2
，正如断言所述。 在这个论证过程中产生了一个技术难点，其原因是算法M 在调用CANYIELD 时需要知道f (n )的值。修改M 可以克服这个因难，方法是对f (n )不断赋值使)(n f ＝l ，2，3，…。对于每个值f (n )＝i ，修改后的算法利用GANYIELD 来确定接受格局是否可达。除此之外，利用该过程，还可通过检查N 能否从起始格局出发到达某个长度为i + 1的格局来确定N 是否至少需要空间大小i + 1。如果接受格局可达，则M 接受；如果没有长为i + 1的格局可达，M 拒绝；否则M 继续尝试)(n f ＝i + 1(也可以用另—种办法来克服这个困难，即假定M 能在空间()()n f O 内计算出)(n f ，但是那样就需要把这个假定加入定理的陈述中)。
8.2 PSPACE 类
与定义P 类相似，下边为空间复杂性定义PSPACE 类。
定义8.6 PSPACE 是在确定型图灵机上、在多项式空间内可判定的语言类。换言之，
()
.n PSPACE PSPACE k k =
PSPACE 类的非确定型版本NPSPACE ，可以类似地用NSPACE 类来定义。然而，任何多项式的平方仍是多项式，根据萨维奇定理，则NPSPACE ＝PSPACE ，。
例8.3已经说明了SAT 属于SPACE （n ）。例8.4说明了ALL NFA 的补属于()n coNSPACE ，根据萨维新定理，确定型空间复杂度对补运算封闭，所以ALL NFA 属于SPACE （n 2）。所以这两个语言都在PSPACE 中。
现在考察PSPACE 与P 和NP 的关系。显而易见，PSPACE P ?，因为运行得快的机器不可能消耗大量的空间。更精确地说，当t (n )≥n 时，由于在每个计算步上最多能访问一个新单元，因此，任何在时间t (n )内运行的机器最多能消耗t (n )的空间。与此类似，NPSPACE NP ?，所以PSPACE NP ?。
反过来，根据图灵机的空间复杂性也可以界定它的时间复杂性。对于n n f ≥)(，通过简单推广引理5.7的证明可知，一个消耗)(n f 空间的TM 至多有))((2)(n f Οn f 个不同的格局，图灵机的停机计算不能出现重复格局。因此消耗空间f (n )的图灵机1必定在时间))((2)(n f Οn f 内运行，得出()k
n k 2PSPACE EXPTIME PSPACE =?。
用下面的一系列包含式总结迄今为止所定义的复杂性类之间的关系：
EXPTIME NPSPACE PSPACE NP P ?=??
这些包含式中，还不知道某一个是否为等式。也许有人会发现一个类萨维奇定理的方法，使得这里的某些类能够合并为一个类。但是在第9章将证明P ≠EXPTIME ，所以上面的包含式中至少有一个是真包含，但还不能确定哪一个！实际上，大部分研究者相信所有包含式都是真包含。图8-l 描绘了这些类之间的关系，假设所有类是不同的。
8.3 PSPACE 完全性
定义8.7 语言B 是PSPACE 完全的。若它满足下面两个条件：
1）B 属于PSPACE 。
2）PSPACE 中的每一个语言A 多项式时间可归约到B 。
若B 只满足条件2），则称它为PSPACE 难的。
义类本身的模型更加受限。
8.3.1 TQBF 问题
PSPACE 完全问题的第一个例子是可满足性问题的推广。回忆以前的内容，布尔公式(Boolean formula )是一个包含布尔变量、常数0和l 以及布尔运算符∧，∨，﹁的表达式。
1当8.4节介绍消耗亚线性空间的图灵机时，这里的要求f (n )≥n 被推广为f (n )≥log n 。
现在定义更一般形式的布尔公式。
量词(quantifiers )?(对所有)和?(存在)在数学命题中经常出现。语句?x ф的含义是，对于变量x 的每个值，语句ф都是真。类似地，语句?x ф的含义是，对于变量x 的某个值，语句ф是真。有时，把?称为全称量词(universal quantifier )，把?称为存在量词(existential quantifier )，紧跟在量词后面的变量x 受到该量词约束。
例如，对于自然数，语句?x [x ＋1> x ]的含义是：每一个自然数x 的后继x +1都比它大。显然这个命题为真。然而，语句? y [y + y =3]显然是假的。当解释包含量词的语句的含义时，必须考虑所取值的域。在这个例子中，域是自然数，但是，如果改用实数，则带存在量词的语句就变成真的了。
语句可以包含多个量词，如?x ?y [y > x ]对于自然数域，该语句的语义是每一个自然数都有另一个自然数比它大。量词的次序很重要。颠倒次序，如语句? y ?x [y >x ]，则给出完全不同的含义，即存在某个自然数比所有其它数都大。显然，第一个语句为真，第二个语句为假。
量词可以出现在数学语句中的任何地方。它的作用范围是跟在量化变量后的一对匹配的括弧内出现的话句段。该段称为量词的辖域(scope )。通常，要求所有变量都出现在语句的开头会很方便，这时每个量词的辖域就是其后的所有语句成分。这种语句称为前束范式(prenex normal form )。很容易把任何语句都写成前束范式。如不特别指明，只考虑这种形式的语句。
带量词的布尔公式称为量词化布尔公式(quantified Boolean formulas )。对于这种公式，域是{0，1}。例如：
()()[]y x y x y x ∨∧∨??=φ
是量词化布尔公式。这里，ф是真。但是如果颠倒量词?x 和?y 的次序，就变成假了。 如果公式的每个变量都出现在某一量词的辖域内，该公式就称为全量词化的(fully quantified )。全量词化的布尔公式有时称为句子，它要么是真，要么是假。例如，前面的公式ф是全量词化的。但是，如果删去ф的开头部分，该公式就不再是全量词化的.它既不是真，也不是假。
TQBF 问题就是要判定一个全量词化的布尔公式是真还是假。定义语言
TQBF = {＜ф＞|ф是真的全量词化的布尔公式}
定理8.8 TQBF 是PSPACE 完全的。
证明思路 为了证明TQBF 属于PSPACE ，给出一个简单的算法。该算法首先给变量赋值，然后递归地计算公式在这些值下的真值。从这些信息中算法就能确定原量化公式的真值。
为了证明PSPACE 中的每个语言A 在多项式时间内可归约到TQBF ，从判定A 的多项式空间界限图灵机开始。然后给出多项式时间归约，它把一个字符串映射为一个量词化的布尔公式ф，ф模拟机器对这个输入的计算。公式为真的充分必要条件是机器接受。
作为这一构造的首次尝试，模仿库克一列文定理的证明思路，即定理7.30。可以构造公式ф，通过描绘接受画面（tableau ）来模拟M 在输入w 上的计算。M 在w 上的画面宽度是)(k n O 即M 消耗的空间。因为M 可能运行指数长的时间，所以它的高度是n k 的指数。因此，如果直接用公式表示画面，就可能导致指数长的公式。然而，多项式归约不能产生指数长的结果，所以这种尝试不能证明TQBF A P ≤。
下边改用一种与萨维奇定理的证明相关的技术来构造公式。该公式把画面分成两半，利
用全称量词的功能，用公式的同一部分来代表每一半。结果实产生短得多的公式。
证明 首先，给出一个判定TQBF 的多项式空间算法：
T =“对输入＜ф＞，ф是一个全量词化布尔公式：
1）若ф不含量词，则它是一个只有常数的表达式。计算ф的值，若为真，则接受；否则，拒绝。
2）若ф等于?x Ψ，在Ψ上递归地调用T ，首先用0替换x ，然后用1替换x 。只要有—个结果是接受，则接受；否则，拒绝。
3）若ф等于?x Ψ．在Ψ上递归地调用T ，首先用0替换x ，然后用1替换x 。若两个结果都是接受，则接受；否则，拒绝。”
算法T 显然判定TQBF 。为了分析它的空间复杂性，我们发现它递归的深度最多等于变量的个数。在每一层只需存储一个变量的值，所以空间总消耗是O (m )，其中m 是ф中出现的变量的个数。因此T 在线性空间内运行。
接下来，证明TQBF 是PSPACE 难的。设A 是一个由TM M 在n k 空间内判定的语言，k 是某个常数。下面给出一个从A 到TQBF 的多项式时间归约。
该归约把字符串w 映射为一个量词化的布尔公式ф。ф为真的充分必要条件是M 接受w 。为了说明怎样构造ф，需解决一个更一般的问题。利用两个代表格局的变量集合c 1和c 2及一个数t ＞0，构造—个公式t ，，21c c φ。如果把c 1和c 1赋为实际的格局，则该公式为真的充分必要条件是M 能够在最多t 步内从c 1到达c 2。然后，可以令ф是公式t ，，accept start c c φ，其中)(2h n df =)
，d 是—个选取的常数，使得M 在长为n 的输入上可能的格局数不超过)(2n df 。这里，令k n )(=n f 。为了方便，假设t 是2的幂。
类似库克-列文定理的证明，该公式对带单元的内容进行了编码。对应于单元的可能设置，每个单元有几个相关的变量，每个带符号和状态都有一个变量对应。每个格局有n k 个单元，所以)(k n O 个变量编码。
若t = l ，则容易构造t ，，21c c φ。设计公式，使之表达要么c 1等于c 2，要么c 1能在M 的一步内变到c 2。为了表达相等性，使用—个布尔表达式来表示代表c 1的每一个变量与代表c 2的相应变量包含同样的布尔值。为表达第二种可能性，利用库克—列文定理的证明技巧，构造布尔表达式表示代表c 1的每个三元组的值能正确地产生相应的c 2的三元组的值，从而就能够表达c 1在M 的一步内产生c 2。
若t ＞l ，递归地构造t ，，21c c φ。作为预演，先尝试一种不是很好的想法，然后再修正它。
令 ??
????
∧?=2t ,c ,2t ,m ,m 2m 1c 1t ,c ,c 1121φφφ 符号m 1表示M 的一个格局。? m 1是?x 1，…，x l 的缩写，其中l ＝()k n O ，x 1，…，x l 是对m 1编码的变量。所以，t ，，21c c φ的这个构造的含义是：如果存在某个中间格局m 1，使得M 在至多2t 步内从c 1到m 1，并且在至多2
t 步内从m 1变到c 2，那么M 就能在至多t 步内从c 1变到c 2 。然后再递归地构造2t m c 11，，φ和2t c m 21，，φ这两个公式。
公式t ,c ,c 21φ具有正确值。换言之，只要M 能在t 步内从c 1变到c 2，它就是TRUE 。然而，它太长了。构造过程中涉及的递归的每一层都把t 的值减小一半，但却把公式的长度增加了大约—倍，最后导致公式的长度大约是t ，开始时t ＝)(2n df ，所以这种方法给出的公式是指数长的。
为了缩短公式的长度，除了使用?量词以外，再利用?量词。令
{}
????????∈??=2t c c 1c c 4321114321)c ,(),c ()c ,c (，，，，，φφm m m t 新引入的变量代表格局c 3和c 4，它允许把两个递归的了公式“折叠”为一个子公式，而保持原来的意思。通过写成?(c 3，c 4)∈{ (c 1，m 1)，(m 1，c 2)}，就指明了代表格局c 3和c 4的变
量可以分别取c 1和m 1的变量的值，或者m 1和c 2的变量的值，结果公式2t c c 43，，φ
在两种情况下都为真。可以把结构?x ∈{ y ，z }[…]替换为等价的结构?x [(x = y ∨ x = z )→ …]，从而得到语法正确的量化布尔公式。回忆第0章的内容，在0.2节中证明了布尔蕴涵(→)和布尔相等(＝)可以用AND 和NOT 来表达。这里，为了清晰，使用符号＝表示布尔相等，而没使用等价符号?。
为了计算公式t ，，accept start c c φ的长度，其中)(2h n df =，注意到递归增加的那部分公式的长度与格局的长度呈线性关系，所以长度是()()n f O 。递归的层数是()()n df 2
log ，或()()n f O 。所以所得到的公式的长度是()()n f O 2
。 8.3.2博弈的必胜策略
例8.9设φ1是公式
()()()[]
323221321x x x x x x x x x ∨∧∨∧∨???
在φ1的公式博弈中，选手E 挑选x 1的值，选手A 挑选x 2的值，最后选手E 挑选x 3的值。 举一个该博奕游戏过程的例子。照例，用1表示布尔值TRUE ，用0表示FALSE 。设选
手E 挑选x 1＝l ，然后选手A 挑选x 2＝0。最后选手E 挑选x 3＝l 。当x 1、x 2和x 3取这些值时，子公式()()()
323221x x x x x x ∨∧∨∧∨是1，所以选手E 赢。实际上，选手E 总可以赢得这场博弈，只要它挑选x 1＝l ，然后不论选手A 给x 2选什么值，它都给x 3选与x 2相反的值。称选手E 有这场博弈的必胜策略。如果双方都下出最佳步骤时，某个选手能赢，则该选手有该博弈的必胜策略。
现在稍微修改一下公式，得到一个博弈，使得选手A 有必胜策略。设φ2是公式 ()()()[]323221321x x x x x x x x x ∨∧∨∧∨???
现在选手A 有必胜策略，因为不论选手E 为x 1选什么值，选手A 可以选x 2＝0，从而使量词后面出现的那部分公式为假，而不论选手E 在最后—步选什么值。
下面考虑判定在与某个具体的公式相关联的公式博弈中哪一方有必胜策略的问题。令 FORMULA-GAME ={<φ>|在与φ相关联的公式博弈中选手E 有必胜策略}
定理8.10 FORMULA-GAME 是PSPACE 完全的。
证明思路 FORMULA-GAME 是PSPACE 完全的，理由很简单，即它和TQBF 是一样的。为了看出FORMULA-GAME ＝TQBF ，注意到一个公式恰好当选手E 在相关联的公式博弈中有必胜策略时为TRUE ，因为两种情况有同样的含义。
证明 公式φ=? x 1? x 2? x 3…Q x k [ψ]是TRUE 的条件是：存在x 1的某种赋值，使得对于x 2的任意赋值，存在x 3的某种赋值，使得…，等等，其中ψ在这些变量的赋值下为TRUE 。类似地，选手E 在与φ关联的博弈φ有必胜策略的条件是：选手E 可以给x 1赋某个值，使得对于x 2的任意赋值，选手E 可以给x 3赋一个值，使得…，等等，ψ在变量的这些赋值下为TRUE 。
当公式不在存在量词与全称量词之间交替时，同样的推理也能成立。如果φ的形式为][,,,654321ψx x x x x x ???，选手A 在公式博弈中走头三步，给x 1，x 2和x 3赋值；然后选手走E 两次，给x 4和x 5赋值；最后选手A 给x 6赋一个值。
因此，φ∈ TQBF 恰好当φ∈FORMULA-GAME 时成立，由定理8.8，本定理成立。
8.3.3 广义地理学
判定在广义地理学游戏中哪—方有必胜策略的问题是PSPACE 完全的。令
GG ＝{＜G ，b ＞| 在图G 上以节点b 起始的广义地理学游戏中，选手I 有必胜策略} 定理8.11 GG 是PSPACE 完全的。
证明思路 用与定理8.8中判定TQBF 时所用的算法相似的—个递归算法就能判定哪方有必胜策略。该算法在多项式空间内运行，所以GG ∈PSPACF 。
为了证明GG 是PSPACE 难的，给出一个从FORMULA-GAME 到GG 的多项式时间归约。该归约把一个公式博弈转化为一个广义地理学图，使得图上的游戏过程模拟公式博弈的游戏过程。实际上，广义地理学游戏的选手就是在玩—种编码形式的公式博弈。
证明 下面的算法判定在广义地理学实例中，选手I 是否有必胜策略。换句话说，它判定GG 。现证明它在多项式时间内运行。
M =“对输入＜G ，b ＞，G 是有向图，b 是G 的节点：
1) 若b 出度为0，则拒绝，因为选手I 立即输。
2) 删去节点b 以及与它关联的所有箭头．得到一个新图G 1。
3) 对于b 原先指向的每个节点b 1，b 2，…，b k ，在＜G 1，b i ＞上递归地调用M 。
4) 若所有调用都接受，则选手Ⅱ在原先博弃中有必胜策略，所以拒绝。否则，选手Ⅱ没有必胜策略，而选手I 有必胜策略，因此接受。”
本算法仅需要用来存储递归栈的空间。递归的每一层给栈中添加一个节点，最多可能有m 层，m 是G 的节点数。因此算法在线性空间内运行。
为了证明GG 的PSPACE 难解性，证明FORMULA-GAME 多项式时间可归约到GG 。归约把公式
φ=? x 1? x 2? x 3…Q x k [ψ ]
映射为广义地理学的一个实例＜G ，b ＞。为了简单，这里假定φ的量词以?开头，以?结尾，并且?和?严格地交替出现，不符合这个假定的公式可以转化为稍长—些的符合假定的公式，这只需添加一些额外量词，约束一些在别处不使用的变量（或称“哑”变量）。还假定ψ是合取范式的(参见问题8.12)。
归约构造图G 上的地理学游戏，其中最优走步模拟φ上的公式博弈的最优走步。地理学游戏中的选手I 扮演公式博弈中的选手E 的角色，选手Ⅱ扮演选手A 的角色。
图G 的结构部分地示于图8-4中。游戏从节点b 开始，它出现在G 的顶层左边。在b 下面是一列钻石结构，φ的每一个变量对应一个。在描述G 的右边之前，先看游戏在左边如何进行。
原书第322页
图8-4 模拟公式博弈的地理学游戏的部分结构
游戏从b 开始。选手I 必须选择从b 出发的两条边之一。这两条边对应于选手E 在公式博弈开始时的可能选择。选手I 选择左边，对应于公式博弈中选手E 选择TRUE ，选择右边对应于FALSE 。在选手I 已经选择了一条边之后，设是左边那条，该选手Ⅱ走步了。因为只有一条出边，所以这—步没有选择。类似地，选手I 的下一步也没有选择，游戏从第二个钻石的顶部继续进行。现在再次有两条边，但是轮到选手Ⅱ选择了。这次选择对应于在公式博弈中选手A 的第一步。随着游戏以这种方式继续进行，选手I 和Ⅱ选择向右或向左的路径通过每个钻石结构。
在游戏经过所有钻石以后。路径的末端在最后—个钻石的底部节点，而且轮到选手I 走步了，因为假定最后一个量词是?。选手I 的下一步没有选择。然后它们到达图8-4的节点c ，轮到选手Ⅱ走下一步。
地理学游戏走到这一步对应于公式博弈过程的结束。所选择的通过钻石的路径对应于给φ的变量的赋值。在该赋值下，如果ψ是TRUE ，则选手E 赢得公式博弈；如果ψ是FALSE ，则选手A 赢。图8-5所示的右边结构保证当选手E 赢时选手I 能赢，而且当选手A 赢时选手Ⅱ能赢，说明如下。在节点c ，选手Ⅱ可以选择一个对应ψ的某个子句的节点。然后选手I 可以选择一个对应该子句中的一个文字的节点。对应不带非的文字的节点连接到对应有关变量的钻石的左边(TRUE)，对于带非的文字和右边(FALSE)情况类似，如图8-5所示。
原书第323页
图8-5 模拟公式游戏的地理学游戏的全部结构，其中
()()()[]∧∧∨∨∧∨∨??......x x x x x x ...x x 32321k 21Q
如果φ是FALSE ，则选手Ⅱ可以选择不满足的子句而取胜。选手I 此时可以选择的文字都是FALSE ，并被连到钻石中还未走过的那一边。于是选手Ⅱ可以选择钻石中的那个节点，而选手I 无法走步了，从而输掉。如果φ是TRUE ，则选手Ⅱ挑选的所有子句都包含TRUE 文字。选手I 在选手Ⅱ走步后选择那个文字。因为该文字是TRUE ，所以它被连到钻石中已
经走过的那一边，因此选手Ⅱ无法走步，输掉。
定理8.11说明在广义地理学中，不存在计算最佳走步的多项式时间算法，除非P ＝PSPACE 。我们希望在计算如国际象棋这一类棋盘博弈的最佳走步方面能够证明类似的难解性定理，但是存在一个障碍。采用标准的8 ? 8国际象棋棋盘，只能出现有穷个不同的棋局。理论上，所有这些棋局以及它们的最佳走步可以放在一张表里。这张表会大到整个星系都放不下，但它却是有穷的，可以存放在图灵机的控制单元中(甚至有穷自动机的控制单元中！)于是机器就可以通过查表在线性时间内走出最佳步。也许在将来会有办法度量有穷问题的复杂性，但是目的的办法是渐近的，因此只能用来度量复杂性随着问题规模的增加而变化的增长率—而不能用于任何固定规模。不过，通过把许多棋盘博弈推广到n ? n 棋盘上，可以就计算它们的最佳走步的难解性给出某些证据。这种推广的国际象棋、跳棋和GO 已被证明是PSPACE 难的，甚至对于更大的复杂性类是难的。这有赖于推广的细节。
8.4 L 类和NL 类
到目前为止，只考虑了时间和空间复杂性界限至少是线性的情况，即界限()n f 至少是n 。现在考察更小的亚线性（sublinear ）空间界限。在时间复杂性中，亚线性界限还不够读完输入，所以这里不考虑它们。在亚线性空间复杂性中机器可以读完整个输入，但是它没有足够的空间存贮输入。为了使对这种情况的考虑有意义，必须修改计算模型。
下面引入一种有两条带的图灵机：一条只读输入带和一条读写工作带。在只读带上输入头能读取符号，但不能改变它们。这个头必须停留在包含输入的那部分带子上。可以给机器提供一个方法，使它能够检测读写头处于输入的左端和右端的时刻。工作带可以用通常的方式读写。只有工作带上被扫描的单元才构成这种形式的图灵机的空间复杂性。
可以把只读输入带想象成CD-ROM 即一种在许多个人计算机上用于输入的设备。通常，CD-ROM 包含的数据比计算机能存放在主存中的数据更多。亚线性空间算法允许计算机处理没有全部存放在主存中的数据。
对于至少是线性的空间界限，两带TM 模型等价于标准的单带模型(参见练习8.1)。对于亚线性空间界限，只采用两带模型。
定义8.12 L 是确定型图灵机在对数空间内可判定的语言类。换言之
L ＝SPACE(()n log )
NL 是非确定型图灵机在对数空间内可判定的语言类。换言之，
NL ＝NSPACE(()n log )
关注()n log 空间，而不关注如n 或n log 2空间的理由与选择多项式时空界限的理由相
似。对数空间足以求解许多有趣的计算问题，而且其数学性质也富有吸引力，比如当机器模型和输入的编码方法改变时仍保持稳健性。指向输入的指针可以在对数空间内表示，所以考虑对数空间算法的计算能力的—种方式是考虑固定数目的输入指针的计算能力。
例8.13 语言A ＝{0k 1k |k ≥0}是L 的成员。在7.1节中描述了一个判定A 的图灵机，它左右来回扫描输入，删掉匹配的0和l 。该算法用线性空间记录哪些位置已经被删掉了，但可以修改为只使用对数空间。
判定A 的对数空间TM 不能删除输入带上已经匹配的0和l ，因为该带是只读的。机器在工作带上用二进制分别数0和1的数目。唯一需要的空间是用来记录这两个计数器。在二
进制形式下，每个计数器只消耗对数空间，因此算法在O(()n log )空间内运行。所以A ∈L 。
例8.14 回忆7.2节中定义的语言P ATH ＝{＜G ，s ，t ＞| G 是包含从s 到t 的有向路径的有向图}。定理7.12证明P ATH 属于P ，但是给出的算法消耗线性空间。还不清楚P ATH 是否能确定性地在对数空间内解决，但是的确知道一个判定P ATH 的非确定性的对数空间算法。
判定P ATH 的非确定型对数空间图灵机从节点s 开始运算，非确定地猜测从s 到t 的路径的每一步。机器在工作带上只记录每一步当前节点的位置，而不是整条路径（否则将超出对数空间的要求）。机器从当前节点所指向的节点中非确定地选择下一个节点。它反复执行这一操作，直至到达节点t 而接受，或者执行m 步以后拒绝，其中m 是图中的节点数。因此P ATH 属于NL 。
以前所做的关于()n f 空间界限的图灵机也在))n (f (Ο2空间内运行的断言，对于非常小的空间界限就不再成立。例如，消耗O (1)（即常数）空间的图灵机就可能运行n 步。为了获得适用于所有空间界限()n f 的运行时间界限，给出下面的定义。
定义8.15 若M 是一个有单独的只读输入带的图灵机，w 是输入，则M 在w 上的格局包含状态、工作带和两个读写头位置。输入w 不作为M 在w 上的格局的一部分。
如果M 在()n f 空间内运行，w 是长为n 的输入，则M 在w 上的格局数是))((2n f Ο。为了解释这一结果，设M 有c 个状态，g 个带符号。能够出现在工作带上的字符串的数目是)(g n f 。输入头可以处在n 个位置之一，工作带头可以处在()n f 个位置之一。因此M 在w
上的格局总数，也就是M 在w 上的运行时间的上界，等于())n (f g n f cn 或))((2n f Οn 。
我们几乎只关注不小于n log 的空间界限()n f 。对于这样的界限，前面关于机器的时间复杂性最多不超过它的空间复杂性的指数倍的断言依然成立，因为当()n f ≥)log(n 时，))((2n f Οn 等于))((2n f Ο。
萨维奇定理表明非确定型TM 可以转化为确定型TM ，而在()n f ≥n 时空间复杂性()n f 只增加平方。可以推广萨维奇定理，使它对于亚线性空间界限()n f ≥)log(n 也能成立。证明与7.1节给出的原始证明基本相同，只是采用有只读输入带的图灵机，在涉及N 的格局的地方改用N 在w 上的格局。存贮N 在w 上的格局需要log())((2n f Οn )＝()n log +()()n f Ο空间。如果()n f ≥()n log ，则存储消耗是()()n f Ο，证明的其余部分都相同。
8.5 NL 完全性
正如在例8.14中提到的，已知P ATH 问题属于NL ，但不知道它是否在L 中。人们相信P ATH 不属于L ，但是不知道怎样证明这一猜想。实际上，还不知道NL 中有哪一个问题可
以被证明不属于L 。类似于P ＝NP 是否成立的问题，也有L ＝NL 是否成立的问题。
作为解决L 与NL 问题的一个步骤，需要先证明某些语言是NL 完全的。正如其它复杂性类的完全语言—样，NL 完全语言在—定意义上是NL 中最困难的语言的样例。如果L 与NL 不相等，那么所有NL 完全语言就不属于L 。
如前面完全性的定义一样，NL 完全语言定义为属于NL ，并且NL 中的所有其它语言都可归约到它。但是这里不用多项式时间可归约性，这是因为所有NL 中的问题都在多项式时间内可解。除了?和∑*
以外，NL 中的任何两个问题都是互相多项式时间可归约的(参见8.3节PSPACE 完全性的定义中关于多项式时间可归约性的讨论)，所以多项式时间可归约性太强，不能把NL 中的问题彼此区分开。可以改用一种新型可归约性，称为对数空间可归约性。 定义8.16 对数空间转换器(log space transducer ) A 是有一条只读输入带、一条只写输出带和一条读写工作带的图灵机。工作带可以包含()()n log O 个符号。对数空间转换器M 计算一个函数f ：∑*→∑*，其中f (w )是把w 放在M 的输入带上启动M 运行，到M 停机时输出带上存放的字符串。称A 为对数空间可计算函数。如果语言A 通过对数空间可计算函数f 映射可归约到语言B ，则称A 对数空间可归约到B ，记为A ≤L B 。
现在已经做好定义NL 完全性的准备。
定义8.17 语言B 是NL 完全的，如果
1）B ∈NL ，并且
2）NL 中的每个A 对数空间可归约到B 。
如果一个语言对数空间可归约到另一个己知属于L 的语言，则这个语言也属于L ，如下述定理所阐明的。
定理8.18 A ≤L B 且B ∈L ，则A ∈L 。
证明 本定理的一个诱人的证明思路是仿照定理7.25的模式，那里证明了多项式时间可归约性的类似结果。按照这种思路，A 的对数空间算法首先用对数空间归约f 把输入w 映射为f (w )，然后应用B 的对数空间算法。但是存储f (w )的空间需求量可能太大，不能放进对数空间界限内，所以需要修改这种方法。
A 的机器M A 不再算出整个f (w )，而是当
B 的机器M B 需要的时候计算f (w )的个别符号。在模拟过程中，M A 记录M B 的输入头在f (w )上的位置。每一次M B 移动时．M A 重新开始在w 上计算f ，除了所需要的f (w )上的位置以外，其余输出全部忽略。这么做可能不时地要求重新计算f (w )的某些部分，因而在时间复杂性方面是低效的。这种方法的好处是在任何时刻只需存储f (w )的一个符号，其结果是用时间来换取空间。
推论8.19 若有一个NL 完全语言属于L ，则L ＝NL 。 图中的搜索
定理8.20 P ATH 是NL 完全的。
证明思路 例8.14证明了P ATH 属于NL ，所以只需证明P ATH 是NL 难的。换言之，必须证明NL 中的每个语言A 对数空间可归约到P ATH 。
从A 到P ATH 的对数空间归约背后的思想是构造一个图，用来表示判定A 的非确定型对数空间图灵机的计算过程。归约把字符串w 映射为一个图，图中节点对应于NTM 在输入w 上的格局。一个节点能指向另—个节点的条件是第一个节点对应的格局能在NTM 的一步内产生第二个节点对应的格局。因此只要从对应初始格局的节点到对应接受格局的节点之间存在—条路径，则机器接受w 。
证明 这里说明了怎样给出一个从NL 中的任意语言A 到P ATH 的对数空间归约。设NTM M 在)(log n O 空间内判定A 。给定输入w ，在对数空间内构造＜G ，s ，t ＞，其中G 为
有向图，G包含从s到t的路径的充分必要条件是M接受w。
G的节点是M在w上的格局。对于M在w上的格局c l和c2，如果c2是M从c l出发的下—个可能的格局，则(c l，c2)是G的—条边。更精确地说，如果M的转移函数指出，c l的状态和它的输入带头和工作带头下的符号一起能产生下一个状态和带头动作，使c l变成c2，那么(c l，c2)是G的一条边。节点s是M在w上的初始格局。机器M被修改为只有唯一的接受格局，把该格局指定为节点t。
该映射把A归约到P ATH，原因是只要M接受输入，它就有一个计算分支接受，这对应于G中一条从起始格局s到接受格局t的路径。反之，如果G中存在从s到t的路径，则M 在输入w上运行时，某个计算分支必定接受，从而M接受w。
为了证明该归约在对数空间内运算，给出一个对数空间转换器，它在输入w上输出G 的一个描述。该描述由两个表组成：G的节点和G的边。列出节点很容易，因为每个节点是M在w上的一个格局，可以在空间c log(n)内表示出来，c是某个常数。转换器顺序地走遍所有可能的长为c log(n)的字符串，检查每一个是否M在w上的合法格局，输出那些通过检查的字符串。类似地，转换器也列出边。对数空间足以验证M在w上的—个格局c l能否产生格局c2，因为转换器只需通过考察c l中读写头位置下的带内容来决定M的转移函数是否会产生格局c2作为结果。转换器依次检查所有的(c l，c2)，探知哪些是G的合格的边。那些合格的边被添加到输出带上。
定理8.20的一个直接的副产品是下面的推论，它称NL是P的子集。
推论8.21NL?P
证明定理8.20说明NL中的任何语言对数空间可归约到P ATH。前边讲过，消耗空间()n f的图灵机在时间()()n fΟ2n内运行，所以在对数空间内运行的归约器也在多项式时间内运行。因此NL中的任何语言多项式时间可归约到P ATH，由定理7.12知后者属于P。又知每一个多项式时间可归约到P中的语言的语言也在P中，所以证毕。
虽然对数空间归约限制更加严格，但是由于计算问题通常是简单的，对于复杂性理论中的大多数归约来说，它已经够用了。例如在定理8.8，已经证明了每一个PSPACE问题在多项式时间内归约到TQBF。在归约过程中产生了重复度高的公式，它们或许可在对数空间内计算，因此或许可以得出结论：利用对数空间，TQBF是PSPACE完全的。这个结论在推论9.6中证明NL?PSPACE时非常有用。这种分离和对数空间归约表明TQBF?NL。
8.6 NL等于coNL
本节包含有关复杂性类之间相互关系的已知结果中最惊人的结果之一。一般认为NP与coNP是不相等的。乍一看，同样的结果对于NL和coNL似乎也成立。
事实上，正如将要证明的，NL等于coNL。这说明关于计算的直觉仍有许多空白。
定理8.22NL＝coNL
证明思路为了证明coNL中的每个问题也在NL中，先证明PATH属于NL，因为P ATH 是NL完全的。所给出的判定PATH的NL算法M，在图G不包含从s到t的路径时，必须有一个接受计算。
首先解决一个容易些的问题。令c是G中从s可达的节点数。假定c作为输入提供给M，先说明怎样利用c求解PATH，然后再说明怎样计算c。
给定G，s，t和c，机器M如下运算。M逐个地走遍G的所有m个节点，非确定地猜测每个节点是否从s可达。一旦节点u被猜测为可达，M就通过猜测一条从s到u的路径来验证这一点。如果一个计算分支没能在m步内验证这一猜测，m是G的节点数，就拒绝。
另外，如果一个分支猜测t可达，就拒绝。机器M对那些已经被验证为可达的节点计数。当一个分支走遍G的所有节点后，它查验从s可达的节点数是否等于c，即实际可达的节点数，如果不等就拒绝。否则该分支接受。
换言之，如果M恰好非确定地挑选了从s可达的c个节点（不包括t），并且通过猜测路径证实了每一个都s从可达，则M就知道剩余的节点不包括t都不可达，所以它就可以接受。
接下来说明怎样计算c，即从s可达的节点数。描述一个非确定的对数空间过程，它至少有一个计算分支具有正确的c值，而所有其他分支都拒绝。
对于从0到m的每个值i，定义A i为G中与s的距离不超过i的节点的集合(即从s出发有一条长度不超过i的路径)。于是A0＝{s}，每个1+
A，A m包含从s可达的所有节点。
?i
i A
令c i是A i中的节点数。下面描述一个过程，从c i中计算出c i+1。反复应用这一过程就获得所需的值c＝c m。
从c i中计算出c i+1所用的思路与前面给出的思路相似。算法走遍G的所有节点，决定每一个节点是1+i A的成员与否，然后数成员的个数。
为了判定节点v是否在1+i A中，用一个内层循环走遍G的所有节点，猜测每一个节点是否在i A中。每一次成功的猜测是由猜测一条从s出发、长度至多为i的路径来证实。对于每个证实了在i A中的节点u，算法检查(u，v)是否是G的一条边。如果是其中的一条边，则v在1+i A中。另外，证实了在i A中的节点的数目也被计算出来。在内层循环结束时，如果证实属于i A的节点总数不等于c，，则i A的全部节点还没有被找完，所以该计算分支拒绝。如果总数的确等于c i，并且v还没有证实属于1+i A则可以下结论说它不在1+i A中。然后走到下一个v，开始外层循环。
证明判定PATH的算法如下。
M＝“对输入＜G，s，t＞
1)令c0＝1,d=0
2)For i＝0 to m-1
3)令1+i c＝1
4)对G中每个节点v（v≠s）
5)令d＝0
6) 对G中每个节点u
7) 非确定地执行或者跳过下列步骤
8) 非确定地沿着从s出发、长度至多为i的路径行进，如果没
有碰到节点u，就拒绝。
9) d加1
10) 如果(u，v)是G的一条边，则c i+1加1。v变为下一个节点，
转向步骤5。
11)若d≠i c，则拒绝。
12）令d＝0
13）对G中每个节点u
14）非确定地执行或跳过下列步骤：
15）非确定地沿着从s出发、长度至多为m的路径行进，如果没有碰到节点u
就拒绝。
16) 若u＝t，则拒绝。
17) d加1。
18）若d≠m
c，则拒绝；否则，接受。”
值得注意的是M也接受格式错误的输入。在任何时刻，本算法只需存储u，v，c i，c i+1，
d，i和一个指向路径末端的指针，所以它在对数空间内运行。
把当前已知的关于几个复杂性类之间相互关系的认识总结如下：
?
?
=
L?
NL
P
PSPACE
coNL
NL?。
还不知道这些包含关系是否有真包含，虽然在第9章推论9.6将证明PSPACE 所以coNL ?P和P?PSPACE1中一定至少有一个成立，但是不知道哪一个成立！大多数研究者推想所有这些包含义系都是真包含。
HUNAN UNIVERSITY 计算理论导引实验报告 题目：图灵机(Turing)的模拟学生姓名： 学生学号： 专业班级：计算机科学与技术2班上课老师： 实验日期：2014-1-6
一、实验目的 (2) 二、实验内容.......................................................................................... 错误！未定义书签。 三、实验代码.......................................................................................... 错误！未定义书签。 四、测试数据以及运行结果 (8) 五、实验感想 (9)
一、实验目的 1、掌握Turing机的概念。 2、掌握Turing机的运行过程，了解每一个格局的转化。 二、实验内容 对于任意给定的一台Turing机和任意给定的字符串w ( w不含空格)，编程模拟此Turing 机的运行过程，要求输出从开始运行起的每一格局。 三、实验代码 /***************************************************************** 图灵机的模拟过程 计科二班20110801212张琦佳 *****************************************************************/ # include
第二讲 原句：I seized the largest brush and fell upon my wretched victim with wild fury. 译文：我抓起那支最大的画笔，势不可挡扑向那全无招架之力的画布。 原文：There is a definite link between smoking and lung cancer. But this doesn’t make you too uncomfortable because you are in good company. 译文：吸烟肯定与肺癌有关，但这并不能使你感到太不舒服，因为吸烟的人不止你一个。 原文：Derek fancies himself as a ladies' man, but he spends too much time admiring himself in the mirror for my liking. 译文：德里克自以为是个讨女人喜欢的人，可是我不喜欢他花那么多的时间在镜子面前自我欣赏。 He is the last man to come. He is the last man to do it. He is the last person for such a job. He should be the last (man) to blame. 原文：John can be relied on. He eats no fish and plays the game. 译文：约翰为人可靠，他既忠诚又正直。 Literal translation takes sentences as its basic units and the whole text into consideration at the same time in the course of translation. It strives to reproduce both the ideological content and the style of the entire literary work and retain as much as possible the figures of speech. 死译：one-to-one translation: each SL word has a corresponding TL word. 硬译：word-for-word translation: Transfers SL grammar and word order, as well as the primary meanings of all the SL words, into translation. It is normally effective only for brief simple neutral sentences. Literal translation goes beyond one-to-one translation, ranges from one word to one word, through group to group, collocation to collocation, clause to clause, to sentence to sentence. Literal translation is the basic translation procedure both in communicative and semantic translation, in that translation starts from there. ---by Newmark Liberal Translation mainly conveys the meaning and spirit of the original without trying to reproduce its sentence pattern or figures of speech. 原文：我们的朋友遍天下。 错译：Our friends are all over the world. 译文: We have friends all over the world. 单词
英语翻译练习题20篇含解析 一、高中英语翻译 1．高中英语翻译题：Translate the following sentences into English, using the words given in the brackets. 1．这个专家所推荐的方法被证明是十分有效的。（prove) 2．对国家来说，保护生态环境和保持经济增长同样重要。（as...as) 3．如果有朝一日，学生能亲自参与到课程开发中，那该有多棒啊！（involve) 4．这本新发行的杂志不仅会影响青少年对时尚的看法，还会开启健康饮食的新潮流。(Not only) 【答案】 1．The method recommended by the expert proved (to be) very effective. 2．For/To a country, protecting the environment is as important as maintaining economic growth. 3．How great it is if one day students can be involved in the development of courses on their own. 4．Not only will the newly-released magazine influence teenager's opinions on fashion, but also it will start a new trend towards a healthy diet. 【解析】 【分析】 本题考查翻译句子，注意按括号内的要求翻译。 1．考查非谓语动词和prove的用法。The method 与recommend之间是逻辑上的动宾关系，表示被动，用过去分词作后置定语，prove用作连系动词，prove(to be)+adj表示“（被）证明是……的”，语境表明事情发生在过去，应该用一般过去时，故翻译为：The method recommended by the expert proved (to be) very effective 2．考查非谓语动词和as...as的用法。根据句意可知本句用动名词作主语，谓语动词用单数，as+adj+表示“同……一样……”，陈述的是客观事实，应该用一般现在时，故翻译为： For/To a country, protecting the environment is as important as maintaining economic growth. 3．考查感叹句和条件状语从句。根据句意可知本句用how+adj+it is形式的感叹句，同时用if引导条件状语从句，表示“如果”，be involved in表示“参与”，故翻译为：How great it is if one day students can be involved in the development of courses on their own. 4．考查倒装。not only…but also表示“不但……而且”，注意not only 和 but also后面都有主谓结构时，如果not only位于第一分句主语之前，则该分句要部分倒装；后一个分句，即but also后面不用倒装，故翻译为：Not only will the newly-released magazine influence teenager's opinions on fashion, but also it will start a new trend towards a healthy diet. 2．高中英语翻译题：Translate the following sentences into English, using the words given in the brackets. 1．他刚要关闭电脑，就在这时手机响了。(when) ________________________________
作文翻译 Unit 1 李明是学化学的，性格开朗幽默，颇有魅力，但英语成绩不佳，每次只能勉强及格。老师警告他，英语不好会阻碍他拿奖学金，并亮出了自己的王牌：如果李明不努力，就让他考试不过关。老师还告诉他，学习英语不能只为了文凭，否则他即使大学毕业，也还是个半文盲。李明虽然保持镇定，但他明白，他的学业生涯正在攸关之际，必须安心下来埋头学习，坚持不懈。 Li Ming was a chemistry major, a charmer noted for his easygoing and humorous temperament. However, his English was so poor that he always barely got by. The teacher admonished him that his poor English would be an impediment to scholarship. What’s more, she showed her trump card: if Li Ming did not work hard. She would flunk him. He was also told that he should not learn English merely for the sake of his diploma. otherwise, even after graduation from university, he would still be semiliterate. Although Li Ming did not lose his composure, he was well aware that he had to settle down to work and follow through because his academic life was at stake. Unit2 我的朋友琳达接受过良好的教育，既美丽又端庄，三十好几依然没有人向她求婚。究其原因，她的事业心极强，整日扑在工作上，每天来往于住处和公司之间，根本没有时间和异性交往。一想到女儿这么大了还单身一人，她父母就焦虑不安。他们不知道该如何是好，甚至还去咨询一些社会学专家。 但是事情在上个月出现了转机，公司的总部调琳达到培训部。在新的工作岗位上，琳达遇到了第一个触动她心弦的男人。从此，他们几乎每天约会，琳达意识到她会不顾一切地爱这个男人。决定嫁人的时候，她告诉了我这个好消息。 虽然琳达的爱情让人想起电影中才会有的浪漫故事，我也担忧未来究竟会怎样，但我还是表达了我由衷的祝福，并爽快答应在婚礼那天做他们的伴娘和伴郎随从中的一员。 Linda, my good friend, has received good education and is both beautiful and elegant. She was not proposed to even when she was well over thirty. The reason is that she, as a career –oriented woman, is devoted to her work. Navigating between home and the company, she had hardly any time to socialize with people of the opposite sex. Her parents were gripped by anxiety at the thought of their daughter still remaining single at such an age. They did not know what to do and even consulted with some sociologists. But the situation began to change last month, when the headquarters of the company transferred Linda to the training department. On the new post, Linda met a man who tugged on her heartstrings for the first time. Ever since then, they dated virtually on a daily basis, and Linda realized that she would love the man beyond all reason. When she decided to take the matrimonial plunge, she informed me. Though Linda’s love is reminiscent of the romance that we see only in movies and I don’t know what the future will hold for her, I give her my heart-felt wishes and agree readily to be a member of the entourage of bridesmaids and groomsmen. Unit 3 食品供应商缺乏诚信已经成为当今社会的一大问题。部分企业欺骗公众，故意散布假消息，颂扬食品添加剂是食品工业的伟大成就，并声称适量的添加剂对健康有益无害。部分有良知的科学家对食品添加剂的含量和毒性展开了深入的病理学研究。研究结果表明，部分常见的食品添加剂经长期，可能会对健康产生危害，这被认为是食品安全研究方面极为重要的
谈严复翻译 翻译，作为一种实践活动，在人类文化的交流中一直在广泛进行着。丰富的翻译活动，有利于我们科学系统地对翻译进行研究，也有利于我们形成独特的中西文化观。严复就是中国近代第一个学贯中西的人，他的翻译对中国近代思想有着深远的影响。 严复曾在福州马尾船厂船政学堂学习了五年，他学习了英文，几何，代数，电磁学，光学等新科学知识，到过新加坡，日本等地考察，后又到英国学习考察政治，经济，法律和社会制度，“了解中西政教，风俗之差异，关心世界大事。”回国后，他翻译了向国人敲起危亡警钟的《天演论》。揭示了自然界和人类社会“物竞天择，适者生存”的客观规律，宣传了进化思想。 下面研究一下严复的翻译思想和特点。在词法和句法结构中，他模仿先秦文体的词法句法结构，桐城派古文的优点，其他文体的积极因素，在此基础上进行创造性转化，创造了独具个人特色的新型文体。在《天演论》的手稿初稿中，他直接引用先秦散文中的句子并标明出处，虽然后来他觉得译作中放入中国古书的名字，中国古人的名字明显不妥，使读者感到彷徨，于是在改稿过程中将正文中出现的中国特色的专有名词尽皆删去，但导言仍保留部分如《导言十三》中的“以其所爱，及其所弗爱”一句系取自《孟子》；《导言十二》中的“诱然
皆生，而不知其所以生；同然皆生，而不知其所以得”系庄子所云，“自营为私”是韩非所言，“人之性恶”出自《荀子》。译文中多用单音节词，双音节词很少。而且他的翻译话语中有很多词类活用的范例。 1. 辨物穷微，明揭天道必不可知说。（《天演论·论六》） 2.不见夫业真者乎？（《原富》） 微是形容词，在句1中活用为动词。句2的业本来为名词，但在句中担任动词职务。同时，严复话语中疑问代词宾语前置，否定句中代词宾语前置的例子也不少。如： 何以明之？（《天演论·人群》） 人弗之觉也，觉亦弗之异也。（《天演论·能实》） 其少见的被动句主要采用先秦的“见”字句结构，如： 特在人者，每为气禀所拘。（《天演论·论八》） 而为是幻且虚者之所主。（《天演论·论九》) 若是物特为天下只所厚而择焉以存也者，夫是之谓天择。（《天演论·导言一》） 为了追求群内达旨，他用了很多排偶句： 小之极于跂行倒生，大之放乎日星天地；隐之则神思智识之所以圣狂，显之则政俗文章之所以沿革。（《天演论·导言二·广义》） 人，动物之灵者也，与不灵之禽兽鱼鳖昆虫对；动物者，生类之有知觉运动者也，与无知觉之指植物对；生类者，有质之物而具支体官理者也，与无支体官理之金石对。（《天演论·导言三·趋异》） 严复的翻译使用最多的策略当推意译，为了启发民智，在翻译过程中
最新英语翻译练习题20篇 一、高中英语翻译 1．高中英语翻译题：Translate the following sentences into English, using the words given in the brackets. 1．我习惯睡前听点轻音乐。(accustomed) 2．将来过怎样的生活取决于你自己。(be up to) 3．没有什么比获准参加太空旅行项目更令人兴奋的了。(than) 4．家长嘱咐孩子别在河边嬉戏，以免遭遇不测。(for fear) 5．虽然现代社会物资丰富，给予消费者更多的选择，但也使不少人变成购物狂。(turn) 【答案】 1．I’m accustomed to listening to some light music before sleep. 2．It’s up to you what kind of life will lead in the future. 3．There is nothing more exciting than being allowed to take part in the space travel programme. 4．Parents ask their kids not to play by the river for fear that something terrible might happen. 5．While modern society, rich in material resources,has given consumers more choice, it turns many of them into crazy shoppers. 【解析】试题分析： 1．翻译这句话的时候，注意词组：be accusto med to doing“习惯于做……”。 2．这句话使用了句型：It’s up to you +从句，“做….由某人决定”。这里what kind of life will lead in the future.是主语从句，it是形式主语。 3．这句话使用了There be句型， nothing 后面是形容词做定语，因为是比较的含义用形容词的比较级more exciting，还有词组“被允许做”be allowed to ，以及词组“参加”：take part in 。 4．这句话使用了for fear that 引导目的状语从句，和词组“让某人不要做……”ask sb. not to do. 5．这句话使用了连词While 表示“尽管，虽然”。词组“富含”be rich in ，主句中使用了词组turn…. into …..“将…变成…”。 考点：考查翻译句子 2．高中英语翻译题：Translate the following sentences into English, using the words given in the brackets. 1．今年元旦我们玩得很开心。(enjoy) 2．舅舅昨天寄给我一张卡片，祝贺我18岁生日。(congratulate) 3．经过多年的建设，这个小镇现在和地震前一样充满了活力。(as...as) 4．演出以一段五十多岁的人耳熟能详的经典音乐开始。(familiar) 5．她一看完那个关于已灭绝物种的电视节目，就立志加入野生动物保护组织。(No sooner)【答案】
Finding your true calling 找寻内心真实的呼唤 The very worst use of time in life is to stay for months or years at a job for which you are completely unsuited. However, a great number of people spend their whole lives doing something during the week so that they can somehow find some thing enjoyable to do on the weekend. 人们一生中利用时间最糟糕的莫过于经年累月地从事自己完全不合适的工作。可是，有相当多的人却一生都是如此度过的：工作日内做做事，周末找些乐子。 In every case, these are men and women with very little future before them.They look upon their jobs as a form of drudgery, a penance they have to pay in order to enjoy the rest of their lives. And because of this attitude, they will seldom advance or be promoted. They will stay pretty much at the same level, moving from job to job, and always wondering why other people seem to live the "good life" while they feel they are living lives of quiet desperation. 从各种情况看，这些人的前途黯淡。他们认为自己的工作是沉重的任务，是他们为了享受余生对自己的惩罚。正是由于这种态度，他们很少会有发展或得到提升。他们总是在原地踏步，工作换了一个又一个，
浙江广播电视大学 英语专业(开放本科) 《翻译理论与实践》期末复习 题型： 一、选择题（每小题2分，共20分） 二、翻译句子。（每小题3分，共30分） 三、篇章翻译（每小题40分，共40分） 四、案例分析题（每小题10分，共10分） 一、选择题（每小题2分，共20分） 1.美国语言学家罗曼.雅各布森把翻译分成__________。 A. 语内翻译 B. 语际翻译 C. 符际翻译 D. 以上选项都正确 2. 下面哪个选项是错误的？_________。 A. dry goods：纺织品B．white goods：白色的货物 C．white wine：白葡萄酒D．toilet water：花露水 3. “This is a special offer and is not subject to our usual discounts” 请问下面哪个译文最合适？________。 A. 这是特殊报盘，不以我方通常折扣为条件。 B. 这是特惠报盘，我方通常折扣不适应于此盘。 C. 此系特惠报盘，不另加我方通常折扣。 D. 这是特殊报盘，不局限于我们通常折扣。 4．下面哪句话的描述是错误的？________。 A．美国著名翻译理论家奈达提出了“动态对等”原则。 B．“动态对等”原则是指，运用交际理论和信息论的原理，将焦点从传统的译文与原文两个文本的比较转移到两个过程的比较，使人们注意到影响信息接收的各种语言和文化因素。C．奈达曾将“动态对等”的提法改成了“功能对等”原则。 D．翻译求的是“形式对等”，而非”动态对等”。
5．_________提出了“美化之艺术，创优似竞赛”的翻译理念。 A．尤金.奈达B．泰特勒 C．许渊冲D．鲁迅 6. 下面哪个配对是错误的？_____。 A．赤脚医生：barefoot doctor B．纸老虎：paper tiger C．to show one’s cards：摊牌D．大海捞针：look for a needle in sea D B C D C D 7.哪句话的描述是正确的？______。 A. 严复提出的翻译是：重神似不重形似 B. 傅雷的翻译标准是：信、达、雅 C. 许渊冲的翻译标准是：美化之艺术，创优似竞赛 D. 泰特勒的翻译标准是：通顺 8. 下面哪个选项是错误的？_________。 A. dry State：实行禁酒的州B．white goods：白色的货物 C．dry white wine：涩白酒D．toilet water：花露水 9. 泰特勒(Tytler)提出的著名翻译原则是：_______。 A. 译文应完整地再现原文的思想内容。 B. 译文的风格、笔调应与原文的性质相同。 C. 译文应像原文一样流畅自然。 D. 以上选项都正确。 10．下面哪个选项是正确的？________。 A．bring down the house 翻译为：“推倒房子” B．pull up one's socks 翻译为：鼓起勇气 C．think a great deal of oneself 翻译为：“为自己想得很多” D．an apple of love 翻译为：“爱情之果” 11．A book, tight shut, is but a block of paper.下面哪个译文是最合适的？_____。A．一本书，紧紧合上，只是一叠纸。 B．一本书，如果紧紧合上不读，只是一叠纸。 C．一本书，如果紧紧合上不读，只是一叠废纸。 D．闲置之书只是一叠废纸。
高考英语基础写作单句训练 1. 保持生态平衡很重要。 3. 夏天到湖里游泳多有趣呀！ 4. 我们多兴奋啊！ 5. 如何处理垃圾是个大问题。 6. 他的爱好是晚饭后下棋。 7. 我对他的话深感失望。 8. 他的演讲鼓舞人心。 10. 他认为帮助别人是他的责任。 11. 我盼望收到你的回信。 13. 请接受我诚挚的歉意，我昨晚没参加宴会。 14. 你在英语上给予我的帮助。 15. 我们听到他大声唱歌。 16. 我回到家时，发现客人已走了。 17. 她的房间总是收拾得井井有条。 18. 他总是第一个来，最后一个走。 20. 现在讨论的问题必须。 1. It is important to keep the balance of nature. 3. What fun/How interesting it is to swim in a lake in summer! 4. How excited we are! 5. How to get rid of rubbish is a big problem. 6. What he likes is playing chess after supper. 7. I was greatly disappointed at what he had said. 8. His speech is encouraging. 10. He feels it is his duty to help others. 11. I am looking forward to hearing from you. 13. Will you kindly accept an apology for my not being present at your party last evening? 14. Thank you for your great help with my English. 15. We heard him singing in a loud voice. 16. When I get home, I found the guests gone. 17. Her room is always in good order. 18. He is always the first to come and the last to leave. 20. The problem being discussed here must be kept secret
基础综合英语课文翻译 导语：《基础综合英语》综合听说读写四个方面。每单元前半 部分涉及听说技能，而后半部分突出读写技能。这四种技能都围绕同一主题展开，相互补充，协同提高。下面是由的关于基础综合英语课文第一单元部分课文的翻译。欢迎阅读！ 对F的赞美 今年将有好几万的十八岁青年毕业，他们都将被授予毫无意义 的文凭。这些文凭看上去跟颁发给比他们幸运的同班同学的文凭没什么两样。只有当雇主发现这些毕业生是半文盲时，文凭的效力才会被质疑。 最后，少数幸运者会进入教育维修车间——成人识字课程，我 教的一门关于基础语法和写作的课程就属于这种性质。在教育维修车间里，高中毕业生和高中辍学生将学习他们本该在学校就学好的技能，以获得同等学历毕业证书。他们还将发现他们被我们的教育体系欺骗了。 在我教课的过程中，我对我们的学校教育深有了解。在每学期 开始的时候，我会让我的学生写一下他们在学校的不快体验。这种时候学生不会有任何写作障碍！我希望有人能让我停止吸毒，让我学习。我喜欢参加派对，似乎没人在意。我是一个好孩子，不会制造任何麻烦，于是他们就让我考试通过，即使我阅读不好，也不会写作。很多诸如此类的抱怨。
我基本是一个空想社会改良家，在教这门课之前，我将孩子们 的学力能力差归咎于毒品、离婚和其它妨碍注意力集中的东西，要想学习好就必须集中注意力。但是，我每一次走进教室都会再度发现，一个老师在期望学生全神贯注之前，他必须先吸引学生的注意力，无论附近有什么分散注意力的东西。要做到这点，有很多种办法，它们与教学风格有很大的关系。然而，单靠风格无法起效，有另一个办法可以显示谁是在教室里掌握胜局的人。这个办法就是亮出失败的王牌。 我永远也忘不了一位老师亮出那张王牌以吸引我的一个孩子的 注意。我的小儿子是个世界级的万人迷，学习不怎么动脑筋却总能蒙混过关，直到施蒂夫特夫人当了他的老师，这种局面才彻底改变了。 当她教我儿子英语时，我儿子是一个高中高年级学生。他坐在 后排和他的朋友说话。她告诉我。你为什么不把他换到前排来？我恳求道，我相信令他难堪的做法会让他安心学习。史蒂夫特夫人从眼镜上方冷冷地看着我。我不会换高年级学生的座位。她说，我会给他们不及格的成绩。我大感紧张。我们儿子的学习生涯在我的眼前闪现。之前，没有老师以此威胁过他。我恢复镇定，艰难地表示我认为她是对的。到家时，我对此感觉良好。目前这是一种激进的做法，但是，嗯，为什么不这么做呢？她要给你不及格。我告诉我的儿我没有再多说什么。突然英语就在他的生活中成了头等大事。他期末得了一个A。 我知道一个例子不能说明问题，但我在夜校中看见了一群愤怒、怨恨的学生，他们愤恨的原因是学校让他们一路混，直到他们甚至都无法再假装跟得上。这些学生智力水平至少也算中等，但最终都退学
一、词语翻译选择（1分*15） 练习一： 1. 姜汁皮蛋: Preserved Eggs in Ginger Sauce 2. 凉拌金针菇: Golden Mushroom with Vegetable 3. 五香牛肉: Spiced Beef 4. 盐焗鸡:Salt Baked Chicken 5. 素鸭: Dried Tofu 6. 电脑盲: computer illiterate 7. 翻两番:quadruple 8. 光谷:optical valley 9. 黑客:hacker 10. 排外主义: exclusivism 练习二： 1. 我打算买辆汽车，可心里一直犹豫不定，不知道买那个牌子的好。 I’m thinking of buying a car, but I’m still of two minds. I can hardly decide as to which brand I should take. 2. 老板这几天沉默寡言，看起来好像是心事重重的。 The boss is quite down these days. He seems to have something weighing heavily on his mind. 3. 千万别得罪他，他会对你怀恨在心的。 Take care not to offend him, or he’ll bear you a grudge. 4. 当老板问起是谁把消息说出去的时候，他们两个人相互推卸责任。 When the boss was asking who had disclosed the news, the two of them began to pass the buck to each other. 5. 这几天不知是什么事把我搞得心烦意乱的。 I don’t know what has set my nerves on edge these days. 6. 火上浇油。To add fuel to the fire. 7. 混水摸鱼。Fish in troubled waters. 8. 小题大做。Make a mountain out of a molehill. 9. 口是心非。Say yes and mean no. 10. 胸有成竹。To have a well-thought plan before doing something.
英语翻译练习题20篇及解析 一、高中英语翻译 1．高中英语翻译题：Translate the following sentences into English, using the words given in the brakes. 1．网球运动在上海越来越流行了。（popular） 2．我认为你们的建议和他们的一样有价值。（as…as） 3．只喝一杯咖啡就会使我整晚睡不着。（keep） 4．为了纪念那些勇敢的消防战士，一部电影即将开拍。（memory） 5．过了三天她才想起把雨衣忘在语言实验室了。（remember） 6．尽管山高林密，医护人员还是迅速地赶到出事地点，试试救援。（despite） 【答案】 1．Tennis is getting more and more popular in Shanghai. 2．I think your suggestion is as valuable as theirs. 3．Drinking only a cup of coffee will keep me awake all night. 4．A film will be made/ shot in memory of those brave fire fighters. 5．It was three days later that she remembered leaving/having left her raincoat in the language lab. 6．Despite the high mountains and thick forests, the doctors and nurses rushed to the scene of the accident for the rescue/to carry out the rescue. 【解析】 【分析】 翻译题要力争做到译文的正确、准确、地道三个要求。正确就是译文没有明显的语言错误，准确是指考生能运用合适的词汇和句式完整的表述原意，地道是指译文不但无语言错误，而且用此选句符合英语习惯，意义表达生动灵活。所以，做翻译题时要综合运用词句知识，注意词汇的习惯搭配和句子时态、语态、人称和句式的选择。 1．表示“越来越……”，英语的表达方式为“比较级+and+比较级用于进行时里中。 2．表示“与……一样……”应该用“as+ adj./adv原级+as…”结构。 3．本句要注意两点：1. 动名词用作主语的用法；2. keep + sb./sth. + adj (做宾补)使……保持某种状态。 4．“为了纪念……”应选用“in the memory of”固定短语来表达。 5．解答本题要注意两点：1. 强调句型的运用；2. remember doing sth.记住做过某事。6．本句较为复杂，除了掌握despite作为介词可以接名词构成介词短语作状语外，还要注意句中谓语动词的准确选择和时态的确定，最后还要注意“实施援救”这一目的状语的表达。 2．高中英语翻译题：翻译句子 1．只有当我们了解了不同的肢体语言我们才可以很好地跟人们交流。(only＋状语从句) ________________________________________________________________________
基础综合英语课后习题翻译邱东林版 文档编制序号：[KKIDT-LLE0828-LLETD298-POI08]
Unit 1 1.Our youngest,a word-class charmer,did little to develop his intellectual talents but always got by Unti l . 我们的小儿子是个世界级的万人迷,学习不怎么动脑筋,但是总是能蒙混过关,直到成为他的老师,这种局面才得以改变. 2.No one seems to stop to think that ----no matter what environment they come from---most kids don’t put school first on their list unless they perceive something is at stake. 似乎没有人停下来想想看,无论还在来自何种环境,他们当中大多数若不是发现情况到了危机关头,才不会把功课当成头等大事呢。 3.Of average intelligence or above ,they eventually quit school,concluding they were too dumb to finish 这些学生智力水平至少也算中等,但是最终都退学,他们总结说自己太笨,学不下去了. 4.Young people generally don’t have the maturity to value education in the same way my adult students value it 年轻人往往不够成熟,不会像我的成年学生那样重视教育 5.It is an expression of confidence by both teachers and parents that student have the ability to learn the material presented to them. 这表明老师和家长都对学生有信心,相信他们能够学好发给他们的学习资料. 6.This means no more doing Scott’s assignments for him because he might fail . No more passing Jodi because she’s such a nice kid. 这意味着再也不要因为担心斯科特会不及格而替他做作业,再也不要因为朱迪是个乖孩子而放她过关. Unit 2 1.I had always dreamed of being proposed to in a Parisian cafe , under dazzling stars , like the one in a Van Gogh knockoff that hangs in my studio apartment .Instead , my boyfriend asked me to marry him while I was Windexing the bathroom mirror. 我一直有这样的梦想,星光灿烂的晚上,在一家巴黎咖啡馆就像梵高所画的“一夜的咖啡馆”我的工作室墙上就有一幅此画的翻本，然而我男朋友却在我用的“稳得新”擦洗卫生间镜子的时候叫我嫁给他。