《自动机理论、语言和计算导论》学习第 12 天，p352-P401 总结，总计 50 页。

一、技术总结

1.Turing Machine(TM)

2.undecidability

​ a.Ld(the diagonalization language)

3.reduction

p392, In general, if we have an algorithm to convert instances of a problem P1 to instances of a problem P2 that have the same answer, then we say that P1 reduces to P2。

二、英语总结

1.strict vs restrict

(1)strict: adj. strongly limiting sb's freedom to behave as they wish。只能做形容词。

(2)restrict: vt. to limit the movements of sb。adj. restricted; n. restriction。

示例 1： First, we restrict the tapes of the TM to behave like stacks。

2.plausibility

(1)plausible: plaus-(to applaud)。 adj. seeming likely to be true or believed。

(2)plausibility: plausible + -ity。u. the quality of seeming likely to be true, or possible to believe。

3.rigorous

rigor(stiffness, firmness)。 adj. careful to consider every part of sth to make certain it is correct。

4.diagonalization

(1)diagonal: c. a straight line that joins two opposite corners of a four-sided flat shape, such as a square。

(2)diagonalize: vt. to put(a matrix) in a form with all the nonzero elements along the diagonal from upper left to lower right。

(3)diagonalizable: adj。

(4)diagonalization: n。

5.vital

vita(life), 后面引申出“essential to life”的之意。adj. necessary for existence of sth; extremely important。

eg: p381, Now, we can make a vital definition。

三、其它

无。

四、参考资料

1. 编程

(1)Eric S.Roberts，《自动机理论、语言和计算导论(英文版.第 3 版)》：https://book.douban.com/subject/2274854/

2. 英语

(1)Etymology Dictionary：https://www.etymonline.com

(2) Cambridge Dictionary：https://dictionary.cambridge.org

欢迎搜索及关注：编程人(a_codists)