【正文】 story is only Mainframe Computing Desktop Computing What’s Computer? Computing is being pervasive/ubiquitous Pervasive/Ubiquitous Computing Resource Poor Resource Rich ? － 1946 ? ENIAC ? Von Neumann Computer ? Modern Computers History of Computing Machines ? The Abacus ? The Mechanical Calculators ? The Electromechanical Machines History of Computing Machines:－ 1946 ? 算盤 ? 數(shù)字由算珠的數(shù)量表示 ? 數(shù)位由算珠的位置確定 ? 通過手動完成從低位到高位的數(shù)字傳送（十進制） ? 執(zhí)行運算就是按照一定的規(guī)則移動算珠的位置 History of Computing Machines:－ 1946 ? 機械時代 History of Computing Machines:－ 1946 ? 1642， Pascal（ 法）： Pascaline， 加法機 ? 1694， Leibnitz（ 德）： calculator， 加減乘除演算機 ? 1834， Babbage（ 英）： Difference Engine， 計算平方等 – 借助機械裝置 (齒輪、杠桿等 )傳送十進制位，機械裝置的動力來自計算人員的手 ? 機電時代 History of Computing Machines:－ 1946 ? 1886， Herman Hollerith： Tabulator ? 1944， Howard Aiken: Harvard Mark I – 使用電力做動力，但計算結(jié)構(gòu)本身還是機械式的 ? ENIAC： Electronic Numerical Integrator And Calculator (電子數(shù)字積分器和計算器 ) ? 1946， U Penn ? 170m2， 30 tons， 150kwatts, 18800 vacuum tubes， 5000 ps ? The first high speed general electronic puter History of Computing Machines:ENIAC ? ENIAC的 致命缺點：程序與計算兩分離 指揮近 2萬電子管 “ 開關(guān) ”工作的程序指令，存放在機器的外部電路里。s Law started to be described as the doubling of number of transistors on a chip every 18 months. – At the beginning of the 1990s, Moore39。(與、積、乘 ) and a unary operation –(非 ) – ( and ) represent the order of operations – 布爾表達式是由上述元素遞歸組合成的符號序 – 所有表達式構(gòu)成了布爾代數(shù)的元素空間 – 一個布爾表達式所代表的數(shù)學(xué)函數(shù)，叫布爾函數(shù) – 表達式的判別、優(yōu)化？ ——離散數(shù)學(xué) Boolean Algebra This algebra of twovalued logic has roots and applications in logic, set, topology, and ring theory 任何一個布爾表達式可以被等價地變換成下面的唯一表達式：它是若干積的和，而在每一個積中， xi 或 xi僅出現(xiàn)一次 。 Turing Machine Fundamentals 1 0 1 1 0 q1 q2 q3 q4 q5 q6 q7 0 0 1 1 0 q1 q2 q3 q4 q5 q6 q7 當(dāng)控制器前處于狀態(tài) q2， 磁頭所指的磁帶方格內(nèi)容為 1，現(xiàn)在要采取得動作是：將該磁帶方格的內(nèi)容改寫為 0，磁頭向右移動一格，控制器內(nèi)狀態(tài)變?yōu)?q5 Example Turing Machine 圖靈機的這種由狀態(tài)、符號確定的工作過程叫做圖靈機程序，可以由一個五元組序列來定義： q, b, a, m, q’ ? q： 當(dāng)前狀態(tài) ? b： 當(dāng)前方格中的符號 ? a： 當(dāng)前方格中修改后的符號 ? m： 磁頭移動的方向，左移 L（ Left）、 右移 R（ Right）， 不動 N（ Nomotion） ? q’： 下一狀態(tài) Turing Machine 前面例子中，圖靈機的一步動作可表示為： q2, 1, 0, R, q5 A Turing machine for incrementing a value 圖靈機計算實例 —— f(x) = 2x 在二進制圖靈機上計算函數(shù) f(x) = 2x，即 x， f(x)都用二進制表示，磁帶方格中只能用 0和 1兩個符號， B表示空白。 在前面的約定下，計算 f(x) = 2x的圖靈機程序如下，其中： Halt表示停機， Error表示在計算中不會出現(xiàn) 當(dāng)前狀態(tài) B被掃描時的寫、移動、狀態(tài)轉(zhuǎn)移 0被掃描時的寫、移動、狀態(tài)轉(zhuǎn)移 1被掃描時的寫、移動、狀態(tài)轉(zhuǎn)移 q1 1， L， q7 0， R， q1 1， R， q2 q2 B， R， q3 0， R， q2 1， R， q2 q3 0， L， q4 0， R， q3 Error q4 B， L， q5 0， L， q4 Error q5 Error 1， L， q5 0， L， q6 q6 B， R， q1 0， L， q6 1， L， q6 q7 Halt B， L， q7 Error 圖靈機計算實例 —— f(x) = 2x ? 為什么以 x的二進制數(shù)為符號作為磁帶初始值 ? ? 為什么停機后磁帶上的二進制值就是最終結(jié)果 ? ? 為什么有 7種狀態(tài) ? ? 為什么在每種狀態(tài)中要進行這些動作 ? 圖靈機程序設(shè)計 圖靈機計算實例 —— f(x) = 2x 1 0 q1 q2 q3 q4 q5 q6 q7 1 0 q1 q2 q3 q4 q5 q6 q7 1 0 q1 q2 q3 q4 q5 q6 q7 開始 第 1步 第 2步 圖靈機計算實例 —— f(x) = 2x 1 0 q1 q2 q3 q4 q5 q6 q7 1 0 0 q1 q2 q3 q4 q5 q6 q7 1 0 0 q1 q2 q3 q4 q5 q6 q7 第 5步