圖靈機模型及數(shù)據(jù)編碼課件

圖靈機模型及數(shù)據(jù)編碼1概述2圖靈機3數(shù)據(jù)在計算機中的表示圖靈機模型及數(shù)據(jù)編碼1概述2圖靈機3數(shù)據(jù)在計算機中1概述

圖靈機模型理論是計算機學科最核心的理論之一，它是在總結(jié)前人制造計算機思想的基礎上提出的理論計算模型，它不僅指導了現(xiàn)代電子計算機的設計，為計算機設計指明了方向，并且是算法分析和程序語言設計的基礎理論。盡管如此，圖靈機模型卻并不復雜，也許正因為如此，才注定了其在計算學科中所具有的強大生命力。掌握了圖靈機理論，等于獲得了學習計算機系統(tǒng)知識的“金鑰匙”。1概述圖靈機模型理論是計算機學科最核心的2圖靈機

在第一臺電子計算機ENIAC誕生的10年前即1936年，英國數(shù)學家圖靈發(fā)表了題為“論可計算數(shù)及其在判定問題中的應用”﹙OnComputerNumbersWithanApplicationtotheEntscheidungsProblem﹚的學術(shù)論文，奠定了學術(shù)界公認的現(xiàn)代電子計算機的理論和模型基礎。1、希爾伯特綱領

20世紀初，逐步形成了關于數(shù)學基礎研究的邏輯主義、直覺主義和形式主義三大流派。其中，形式主義流派的代表人物是數(shù)學家希爾伯特﹙D．Hilbert﹚。他在數(shù)學基礎的研究中提出了一個設想，其大意是：將每一門數(shù)學的分支形式化，構(gòu)成形式系統(tǒng)或形式理論，并在以此為對象的元理論即

2圖靈機在第一臺電子計算機ENIAC誕生的10年前元數(shù)學中，證明每一個形式系統(tǒng)的相容性，從而導出全部數(shù)學的相容性，希爾伯特的這一設想，就是所謂的“西爾伯特綱領”?！拔鳡柌鼐V領”的目標，其實質(zhì)就是要尋找通用的形式邏輯系統(tǒng)，該系統(tǒng)應當是完備的，即在該系統(tǒng)中，可以機械地判定任何給定命題的真?zhèn)巍?/p>

D．Hilbert

希爾伯特元數(shù)學中，證明每一個形式系統(tǒng)的相容性，從而導出全部D．Hil“西爾伯特綱領”的研究基礎是邏輯和代數(shù)，主要源于19世紀英國數(shù)學家喬治·布爾﹙G．Boole﹚所創(chuàng)立的邏輯代數(shù)體系﹙即布爾代數(shù)﹚。1854年，布爾在他的著作中成功地將“真”、“假”兩種邏輯值和“與”、“或”、“非”3種邏輯運算歸結(jié)為一種代數(shù)。這樣，形式邏輯系統(tǒng)中的任何命題都可用數(shù)學符號表示出來，并能按照一定的規(guī)則推導出結(jié)論。盡管布爾沒有將“布爾代數(shù)”與計算機聯(lián)系起來，但他的工作卻為現(xiàn)代計算機的誕生作了重要的理論準備。G．Boole喬治·布爾“西爾伯特綱領”的研究基礎是邏輯和代數(shù)，主要源于19世紀G．希爾伯特的工作建立在布爾工作的基礎上，并使其進一步具體化。希爾伯特對實現(xiàn)自己的綱領充滿信心。然而，1931年，奧地利25歲的數(shù)理邏輯學家哥德爾﹙K．G?del﹚提出的關于形式系統(tǒng)的“不完備性定理”中指出，這種形式系統(tǒng)是不存在的，從而宣告了著名的“西爾伯特綱領”的失敗。希爾伯特綱領的失敗同時也暴露了形式系統(tǒng)的局限性，它表明形式系統(tǒng)不能窮盡全部數(shù)學命題，任何形式系統(tǒng)中都存在著該系統(tǒng)所不能判定其真?zhèn)蔚拿}。希爾伯特的工作建立在布爾工作的基礎上，并使其進一步具

“西爾伯特綱領”雖然失敗了，但它仍然不失為人類抽象思維的一個偉大成果，它的歷史意義是多方面的。

首先，“西爾伯特綱領”是在保全古典數(shù)學的前提下去排除集合論悖論的，它給數(shù)學基礎問題的研究帶來了全新的轉(zhuǎn)機。其次，希爾伯特綱領的提出使元數(shù)學得到了確立和發(fā)展。最后，對計算學科而言，最具意義的是，希爾伯特綱領的失敗啟發(fā)人們應避免花費大量的精力去證明那些不能判定的問題，而應把精力集中于解決具有能行性的問題?！拔鳡柌鼐V領”雖然失敗了，但它仍然不失為人類抽象2、圖靈對計算本質(zhì)的揭示在哥德爾研究成果的影響下20世紀30年代后期，圖靈﹙A．M．Turing﹚從計算一個數(shù)的一般過程入手對計算的本質(zhì)進行了研究，從而實現(xiàn)了對計算本質(zhì)的真正認識。根據(jù)圖靈的研究，直觀地說，所謂計算就是計算者﹙人或機器﹚對一條兩端可無限延長的紙帶上的一串0和1執(zhí)行指令，一步一步地改變紙帶上的0或1，經(jīng)過有限步驟，最后得到一個滿足預先規(guī)定的符號串的變換過程。圖靈用形式化方法成功表述可計算這一過程的本質(zhì)。圖靈的研究成果是哥德爾研究成果的進一步深化，該成果不僅再次表明了某些數(shù)學問題是不能用任何機械過程來解決的思想，而且還深刻揭示可計算所具有的“能行過程”的本質(zhì)特征。2、圖靈對計算本質(zhì)的揭示

圖靈的描述是關于數(shù)值計算的，不過，我們知道英文字母表的字母以及漢字均可以用數(shù)來表示，因此，圖靈機同樣可以處理非數(shù)值計算。不僅如此，更為重要的是，由數(shù)值和非數(shù)值﹙英文字母、漢字等﹚組成的字符串，既可以解釋成數(shù)據(jù)，又可以解釋成程序，從而計算的每一過程都可以用字符串的形式進行編碼，并存放在存儲器中，以后使用時譯碼，并由處理器執(zhí)行，機器碼﹙結(jié)果﹚可以從高級符號形式﹙即程序設計語言﹚機械地推導出來。圖靈的研究成果是：可計算性＝圖靈可計算性。在進行可計算性問題的討論時，不可避免地要提到一個與計算具有同等地位和意義的基本概念，那就是算法。算法也稱為能行圖靈的描述是關于數(shù)值計算的，不過，我們知道英文方法或能行過程，是對解題﹙計算﹚過程的精確描述，它由一組定義明確且能機械執(zhí)行的規(guī)則﹙語句、指令等﹚組成。根據(jù)圖靈的論點，可以得到這樣的結(jié)論：任一過程是能行的﹙能夠具體表現(xiàn)在一個算法中﹚，當且僅當它能夠被一臺圖靈機實現(xiàn)。圖靈機等計算模型均是用來解決問題的，理論上的能行性隱含著計算模型的正確性，而實際實現(xiàn)中的能行性還包含時間與空間的有效性。方法或能行過程，是對解題﹙計算﹚過程的精確描述，它由3、圖靈機為紀念圖靈對計算機的貢獻，美國計算機博物館于1966年設立了“圖靈獎”計算機是使用相應的程序來完成任何設定好的任務。圖靈機是一種思想模型，它由三部分組成：一個控制器，一條可以無限延伸的帶子和一個在帶子上左右移動的讀寫頭。3、圖靈機為紀念圖靈對計算機的貢獻，計算機是使用相應的程序來

根據(jù)圖靈的觀點可以得到這樣的結(jié)論：凡是能用算法方法解決的問題，也一定能用圖靈機解決；凡是圖靈機解決不了的問題，任何算法也解決不了。今天我們知道，圖靈機與當時提出的用于解決計算問題的遞歸函數(shù)、λ演算和POST規(guī)范系統(tǒng)等計算模型在計算能力上是等價的。它們于20世紀30年代共同奠定了計算科學的理論基礎。相比于其他幾種計算模型，圖靈機是從過程這一角度來刻畫計算的本質(zhì)，其結(jié)構(gòu)簡單，操作運行規(guī)則也較少，從而為更多的人所理解。圖靈機的特征①圖靈機由一條兩端可無限延長的帶子、一個讀寫頭以及一組控制讀寫頭工作的命令組成，如圖所示。圖靈機根據(jù)圖靈的觀點可以得到這樣的結(jié)論：凡是能用算的帶子被劃分為一系列均勻的方格。讀寫頭可以沿帶子方向左右移動，并可以在每個方格上進行讀寫。②寫在帶子上的符號為一個有窮字母表：｛S0,S1,S2,…,SP｝。通常，可以認為這個有窮字母表僅有兩個S0、S1字符，其中S0可以看作是“0”，S1可以看作是“1”，它們只是兩個符號，要說有意義的話，也只有形式的意義?！?/p>

bb10100010bbb

…

狀態(tài)q1讀—寫頭控制器的帶子被劃分為一系列均勻的方格。讀寫頭可以沿帶子方向左…由字符“0”和“1”組成的字母表可以表示任何一個數(shù)。③機器的控制狀態(tài)表為｛q1,q2,…qm,｝。通常，將一個圖靈機的初始狀態(tài)設為q1，在每一個具體的圖靈機中還要確定一個結(jié)束狀態(tài)qw。一個給定機器的“程序”認為是機器內(nèi)的五元組﹙qiSjSkR﹙或L或N﹚ql﹚形式的指令集，五元組定義了機器在一個特定狀態(tài)下讀入一個特定字符時所采取的動作。

5個元素的含義如下：

qi表示機器目前所處的狀態(tài)；

Sj表示機器從方格中讀入的符號；

Sk表示機器用來代替寫入方格中的符號；

R、L、N分別表示向右移一格、向左移一格、不移動；

ql表示下一步機器的狀態(tài)。由字符“0”和“1”組成的字母表可以表示任何一個數(shù)。圖靈機的工作原理機器從給定帶子上的某起始點出發(fā)，其動作完全由其初始狀態(tài)及機內(nèi)五元組來決定。就某種意義而言，一個機器其實就是它作用于紙帶上的五元組集。一個機器計算的結(jié)果是從機器停止時帶子上的信息得到的。4、馮·諾依曼型計算機

1946年2月14日，世界上第一臺數(shù)字電子計算機ENIAC在美國賓夕法尼亞大學研制成功。該機是使用電子線路來執(zhí)行算術(shù)和邏輯運算以及信息存儲的真正工作的計算機器，它的成功研制顯示了電子線路的巨大優(yōu)越性。但是，ENIAC的結(jié)構(gòu)在很大程度上是依照機電系統(tǒng)設計的，還存在重大的線路結(jié)構(gòu)等問題。在圖靈等人工作的影響下，1946年6月，美國杰出的數(shù)學家馮·諾依曼及其同事完成了關于《電子計算裝置邏輯結(jié)構(gòu)設計》的研究報告，具體圖靈機的工作原理介紹了制造電子計算機和程序設計的新思想，給出了由控制器、運算器、存儲器、輸入和輸出設備5類部件組成的，被稱為馮·諾依曼型計算機﹙或存儲程序式計算機﹚的組織結(jié)構(gòu)，以及實現(xiàn)它們的方法，為現(xiàn)代計算機的研制奠定了基礎，至盡為止，大多數(shù)計算機采用的仍然是馮·諾依曼型計算機的組織結(jié)構(gòu)，只是作了一些改進而已。因此，馮·諾依曼被人們譽為“計算機器之父”。介紹了制造電子計算機和程序設計的新思想，給出了由控內(nèi)存儲器運算器外存儲器輸入設備輸出設備控制器數(shù)據(jù)信號控制信號注：馮·諾依曼型計算機的組織結(jié)構(gòu)內(nèi)存儲器運算器外存儲器輸入設備輸出設備控制器數(shù)據(jù)信號控制信號JohnvonNeumann馮諾依曼1949EDSAC存儲程序工作原理計算機的兩個基本能力：一是能夠存儲程序，二是能夠自動地執(zhí)行程序。計算機是利用“存儲器”（內(nèi)存）來存放所要執(zhí)行的程序的，而稱之為CPU的部件可以依次從存儲器中取出程序中的每一條指令，并加以分析和執(zhí)行，直至完成全部指令任務為止。JohnvonNeumann1949EDSAC存儲程序香儂是現(xiàn)代信息論的著名創(chuàng)始人。1938年，香儂在發(fā)表的論文中，首次用布爾代數(shù)進行開關電路分析，并證明布爾代數(shù)的邏輯運算可以通過繼電器電路來實現(xiàn)。阿塔納索夫提出了計算機的三條原則：1）以二進制的邏輯基礎來實現(xiàn)數(shù)字運算，以保證精度；2）利用電子技術(shù)來實現(xiàn)控制、邏輯運算和算術(shù)運算，以保證計算速度；3）采用把計算功能和二進制數(shù)更新存儲功能相分離的結(jié)構(gòu)。ClaudeShannon奠定現(xiàn)代計算機發(fā)展的重要人物和思想ClaudeShannon奠定現(xiàn)代計算機發(fā)展的重要人物和思3數(shù)據(jù)在計算機中的表示

計算機中的數(shù)據(jù)和指令都是用二進制代碼表示的，這是因為計算機的各組成部分是僅具有兩個穩(wěn)定狀態(tài)的物理元件—電子開關線路所組成。為此，要想深入學習計算機的各個部分，必須掌握二進制代碼的有關知識。計算機中用二進制代碼表示數(shù)據(jù)信息有兩種方法：①按“值”表示：在選定的進位制中正確地表示出數(shù)值，包括數(shù)字、符號、小數(shù)點位置及正負號等。如“－9.5”可表示為二進制的“－1001.1”。②按“形”表示：按照一定的編碼方法來表示數(shù)據(jù)。如用ASCII碼表示“－9.5”，其形式為0101101、0111001、0101110、0110101。

3數(shù)據(jù)在計算機中的表示計算機中的數(shù)據(jù)和指令1、進位制數(shù)及其相互轉(zhuǎn)化

(一)進位制數(shù)（進位計數(shù)制）數(shù)制的定義：用一組固定的數(shù)字(數(shù)碼符號)和一套統(tǒng)一的規(guī)則來表示數(shù)值的方法就叫做數(shù)制(numbersystem也稱計數(shù)制)。這一定義主要的內(nèi)涵是：(1)數(shù)制的種類很多，除了十進制數(shù)，還有二十四進制(24小時為一天)，六十進制(60分為1小時，60秒為1分)，二進制(鞋、襪、筷子等兩只為一雙)，等等。(2)在一種數(shù)制中，只能使用一組固定的數(shù)字來表示數(shù)的大小。數(shù)字在一個數(shù)中所處的位置稱為數(shù)位。具體使用多少個數(shù)字來表示一個數(shù)值的大小，就稱為該數(shù)制的基數(shù)(base)。例如，十進制數(shù)(Decimal)1、進位制數(shù)及其相互轉(zhuǎn)化的基數(shù)是10，使用0～9十個數(shù)字，二進制數(shù)(Binary)的基數(shù)為2，使用0，1兩個數(shù)字。在計算機文獻中，十進制數(shù)是在數(shù)的末尾加字母D來標識。例如，1989D，表示十進制數(shù)1989。一般情況下，1989就是一個十進制數(shù)，不在后面加D。二進制數(shù)是在數(shù)的末尾加字母B來標識。例如，101B，表示二進制數(shù)的101，即十進制數(shù)的5。(3)在一種數(shù)制中，有一套統(tǒng)一的規(guī)則。N進制的規(guī)則是逢N進1，或者借1為N。權(quán)或稱位權(quán)，是指數(shù)位上的數(shù)字乘上一個固定的數(shù)值。十制數(shù)是逢十進一，所以對每一位數(shù)可以分別賦以位權(quán)100，101，102，…。用這樣的位權(quán)就能夠表示十進制的數(shù)。的基數(shù)是10，使用0～9十個數(shù)字，二進制數(shù)(Binary)的基數(shù)某一基數(shù)中的最大數(shù)是“基數(shù)減1”，而不是基數(shù)本身，如十進制數(shù)中的最大數(shù)為(10－1＝)9，二進制數(shù)中的最大數(shù)為(2－1＝)1；最小數(shù)均為0。數(shù)位、基數(shù)和位權(quán)是進位計數(shù)制中的三個要素。采用二進制記數(shù)法原因目前，在計算機內(nèi)部，數(shù)據(jù)的計算和處理都采用二進制記數(shù)法，主要是由二進制數(shù)在技術(shù)操作上的可行性、可靠性、簡易性以及其邏輯性所決定的。(1)可行性若用十進制數(shù)，需要0，1，…，9等不同的10個基數(shù)，用電子技術(shù)實現(xiàn)這10種狀態(tài)就很困難。而用二進制數(shù)，則只需0，1兩個基數(shù)，要表示兩個狀態(tài)，這在電學技術(shù)上的基數(shù)實現(xiàn)最為容易。例如，電燈的亮和滅，晶體管的導通和截止，等等。(2)可靠性因二進制數(shù)只要兩個狀態(tài)，數(shù)字轉(zhuǎn)移和處理就不易出錯，這樣計算機工作的可靠性就高。(3)簡易性二進制數(shù)運算法則簡單。例如，二進制的加法、積法法則都只有三個。運算法則少，使計算機運算器結(jié)構(gòu)大大簡化，控制也可隨之簡化。(4)邏輯性由于二進制數(shù)只要0，1兩個數(shù)碼，可以代表邏輯代數(shù)中的“假”和“真”，這就是在計算機中使用二進制的邏輯性。實現(xiàn)最為容易。例如，電燈的亮和滅，晶體管的導通和截止，具體分析二進制、十進制、八進制、十六進制的性質(zhì)：①十進制﹙D﹚ⅰ具有十個數(shù)字符號0，1，2，3，…，9；

ⅱ逢十進一；

?；鶖?shù)為10，第i位的權(quán)為﹙10﹚i。舉例：﹙123.45﹚10＝1×102＋2×101＋3×100＋4×10-1

＋5×10-2表示方法：﹙123.45﹚10＝123.45D②二進制﹙B﹚ⅰ具有兩個數(shù)字符號0，1；

ⅱ逢二進一；

ⅲ基數(shù)為2，第i位的權(quán)為﹙2﹚i。具體分析二進制、十進制、八進制、十六進制的性質(zhì)：舉例：﹙101.101﹚2＝1×22＋0×21＋1×20＋1×2-1＋0×2-2

＋1×2-3表示方法：﹙101.101﹚2＝101.101B③八進制﹙Q﹚ⅰ具有八個數(shù)字符號0，1，2…，7；

ⅱ逢八進一；

?；鶖?shù)為8，第i位的權(quán)為﹙8﹚i。舉例：﹙137.43﹚8

＝1×82＋3×81＋7×80＋4×8-1

＋3×8-2表示方法：﹙137.43﹚8＝137.43Q舉例：﹙101.101﹚2＝1×22＋0×21＋1×20＋1④十六進制﹙H﹚?、【哂惺鶄€數(shù)字符號0，1，2…，9，A，B，C，D，E，F(xiàn)；

ⅱ逢十六進一；

?；鶖?shù)為16，第i位的權(quán)為﹙16﹚i。舉例：﹙147B.CD﹚16＝1×163＋4×162＋7×161＋

B×160＋C×16-1＋D×16-2表示方法：﹙147B.CD﹚16＝147B.CDH㈡進位制數(shù)的相互轉(zhuǎn)換

1、十進制數(shù)與二進制數(shù)間的相互轉(zhuǎn)換

①DB④十六進制﹙H﹚①D例1：﹙5﹚10＝﹙？﹚2﹙27﹚10＝﹙？﹚2251……0222……10……1227213……126……123……021……10……1即﹙5﹚10＝﹙101﹚2

﹙27﹚10＝﹙11011﹚2

例1：﹙5﹚10＝﹙？﹚2﹙27﹚10＝﹙？﹚2251例2：﹙0.625﹚10＝﹙？﹚2

0.625×21.250……1×20.50……0×21.0……1

即

﹙0.625﹚10＝﹙0.101﹚2

例3：﹙27.625﹚10＝﹙11011.101﹚2

口訣：整數(shù)部分，除2取余數(shù)，直到商為0。余數(shù)排列，由下到上；小數(shù)部分，乘2取整數(shù)，直到小數(shù)部分為0﹙或達到所求的精確度﹚。整數(shù)排列，由上到下。例2：﹙0.625﹚10＝﹙？﹚20.625×將二進制數(shù)的各位按權(quán)展開相加。例4：﹙101﹚2＝﹙？﹚10

﹙101﹚2＝1×22＋0×21＋1×20＝﹙5﹚10例5：﹙11011.101﹚2＝﹙？﹚10﹙11011.101﹚2＝1×24＋1×23＋0×22＋1×21＋1×20

＋1×2-1＋0×2-2＋1×2-3

＝27＋0.5＋0.125

＝﹙27.625﹚10②BD②BD2、十進制與八進制間的相互轉(zhuǎn)化①DQ

同與二進制間的轉(zhuǎn)化類似，整數(shù)部分除以8，取余數(shù)；小數(shù)部分則乘以8，取整數(shù)。此外，我們知道，八進制的基數(shù)8正好是二進制基數(shù)的3次冪，即81＝23，故八進制的一位相當于二進制的三位。因此在轉(zhuǎn)化時，也可以先將十進制數(shù)轉(zhuǎn)化為二進制數(shù)，而后在進一步轉(zhuǎn)化為八進制數(shù)。例﹙略﹚②QD將八進制數(shù)的各位按權(quán)展開相加。例﹙略﹚2、十進制與八進制間的相互轉(zhuǎn)化八進制與二進制的關系

八進制

對應二進制八進制對應二進制00004100100151012010611030117111八進制與二進制的關系八進制對應二進制八進制對應二進制003、十進制數(shù)與十六進制數(shù)間的相互轉(zhuǎn)化①DH

同與二進制間的轉(zhuǎn)化類似，整數(shù)部分除以16，取余數(shù)；小數(shù)部分則乘以16，取整數(shù)。十六進制的基數(shù)16正好是二進制基數(shù)的4次冪，即161＝24，故十六進制的一位相當于二進制的四位。因此在轉(zhuǎn)化時，也可以先將十進制數(shù)轉(zhuǎn)化為二進制數(shù)，而后在進一步轉(zhuǎn)化為十六進制數(shù)。例﹙略﹚②HD將十六進制數(shù)的各位按權(quán)展開相加。例﹙略﹚3、十進制數(shù)與十六進制數(shù)間的相互轉(zhuǎn)化十六進制與二進制的關系

十六進制

對應二進制

十六進制

對應二進制

0000081000100019100120010A101030011B101140100C110050101D110160110E111070111F1111十六進制與二進制的關系十六進制對應二進制十六進制對應二2、數(shù)據(jù)的長度單位

數(shù)據(jù)的長度單位有位、字節(jié)和字等。

(1)位

也稱比特，記為bit(binarydigit的縮寫)或小寫b，這是最小的信息單位，是用0或1來表示的1個二進制數(shù)位。

(2)字節(jié)

記為Byte或大寫B(tài)，這是計算機的最小存儲單元。PC機中由8個二進制位構(gòu)成一個字節(jié)，從最小的00000000到最大的11111111，即一個字節(jié)可有256個值。一個字節(jié)也可以表示由8個二進制位構(gòu)成的其它信息。一個字節(jié)可存放一個半角英文字符的編碼(ASCII碼)。兩個字節(jié)可存放一個漢字編碼，2、數(shù)據(jù)的長度單位1個漢字至少需要兩個字節(jié)或兩個字符來表示。這里所說的字符是指ASCII碼字符，即半角下的英文字母、數(shù)字或其它符號。位（Bit）：度量數(shù)據(jù)的最小單位字節(jié)（Byte）：最常用的基本單位K(KiloBytes，千)字節(jié) 1K=1024byte=210M（MegaBytes，兆）字節(jié) 1M=1024K=220G（GigaBytes，吉）字節(jié) 1G=1024M

=230T（TeraBytes，太）字節(jié) 1T=1024G=240P（PetaBytes，拍）字節(jié) 1T=1024G=2501個漢字至少需要兩個字節(jié)或兩個字符來表示。這里所說的位（Bi(3)字記為word或小寫w，是計算機信息交換、加工、存儲的基本單元。用二進制代碼表示，一個字由一個字節(jié)或若干字節(jié)構(gòu)成。它可以代表數(shù)據(jù)代碼、字符代碼、操作碼和地址碼或它們的組合。計算機的“字”用來表示數(shù)據(jù)或信息長度。3、數(shù)值的表示㈠機器數(shù)在計算機中，因為只有“0”和“1”兩種形式，為了表示數(shù)的正、負號，也必須以“0”和“1”表示。通常把一個數(shù)的最高位定義為符號位，用0表示正，1表示負，稱為數(shù)符；其余位仍表示數(shù)值。通常，把在機器內(nèi)存放的正負號數(shù)碼化的數(shù)成為機器數(shù)，把機器外部由正負表示的數(shù)稱為真值數(shù)。(3)字例如，若一個數(shù)占8位，真值數(shù)﹙－0101100﹚B的機器數(shù)為10101100，存放在機器中如圖示。機器數(shù)表示的范圍受到字長和數(shù)據(jù)類型的限制。字長和數(shù)據(jù)類型確定了，機器數(shù)表示的范圍也定了。㈡整數(shù)和實數(shù)在機器中，難以表示小數(shù)點，故在機器中通過對小數(shù)點的位置加以規(guī)定來表示。因此，就有整數(shù)和實數(shù)區(qū)分。10101100數(shù)符例如，若一個數(shù)占8位，真值數(shù)﹙－0101100﹚B的機器數(shù)11、整數(shù)整數(shù)是沒有小數(shù)部分的數(shù)，也可以認為小數(shù)點在數(shù)的最右邊。整數(shù)分為帶符號和不帶符號兩類。對帶符號的整數(shù)，符號位被放在最高位。整數(shù)表示的數(shù)是精確的，但數(shù)的范圍是有限的。根據(jù)存放數(shù)的字長，它們可以用8、16、32位等表示，各自表示數(shù)的范圍見下表。

不同位數(shù)和數(shù)的表示范圍

二進制位數(shù)

無符號整數(shù)的表示范圍

有符號整數(shù)的表示范圍

80～255﹙28—1﹚

－128～127﹙27—1﹚

160～65535﹙216—1﹚

－32768～32767﹙215—1﹚

320～﹙232—1﹚

－231～231—11、整數(shù)不同位數(shù)和數(shù)的表示范圍二進制位數(shù)無符號整數(shù)的表示2、實數(shù)計算機處理的數(shù)值大部分是實數(shù)，即帶有小數(shù)部分的數(shù)，尤其是在科學計算中。通常，為了能表示特大或特小的數(shù)，實數(shù)采用“浮點數(shù)”或稱“科學表示法”表示，“浮點數(shù)”由兩部分組成，即尾數(shù)和階碼。

任意二進制規(guī)格化浮點數(shù)的表示形式為：N＝±d×2±p,式中：d是尾數(shù)，前面的“±”表示數(shù)符；p是階碼，前面的“±”表示階符。它在計算機內(nèi)的存儲形式如圖示：階符Ef

階碼E

數(shù)符Sf

尾數(shù)S

浮點數(shù)存儲格式

2、實數(shù)階符Ef階碼E數(shù)符Sf尾數(shù)S

階碼通常用整數(shù)形式來表示，它指出的是小數(shù)點在數(shù)據(jù)中的位置，決定了浮點數(shù)的表示范圍；尾數(shù)通常用小數(shù)形式表示，給出了有效數(shù)字的位數(shù)，決定了浮點數(shù)的表示精度。所謂規(guī)格化的浮點數(shù)就是指尾數(shù)需滿足條件：≤S＜1。㈢二進制的原碼、反碼及補碼表示按值表示數(shù)需解決的一個問題是如何表示數(shù)的正負號。在計算機中，數(shù)的正負號是用“0”、“1”表示的。機器數(shù)在計算機時，若將符號同時和數(shù)值參加運算，則會產(chǎn)生錯誤的結(jié)果；否則要考慮計算機結(jié)果的符號問題，將增加計算機實現(xiàn)的難度。例如，－5＋4的結(jié)果應為－1，但在

階碼通常用整數(shù)形式來表示，它指出的是小數(shù)點在計算機中若按照上面講的符號和數(shù)值同時參加運算，結(jié)果為－9，顯然是錯誤的。若要考慮符號位的處理，則運算變得復雜。為了解決此類問題，在機器數(shù)中，數(shù)有三種表示法：原碼﹙primarycode﹚、反碼﹙one’scomplement﹚和補碼﹙tow’scomplement﹚。設計算機的字長為n位，它可表示的真值x＝±xn-2xn-3……x0,其中xi＝0或1﹙二進制數(shù)﹚，則有：1、真值x＝＋xn-2xn-3……x0時，原碼、反碼和補碼完全相同，即[x]原＝[x]反＝[x]補＝0xn-2xn-3……x0計算機中若按照上面講的符號和數(shù)值同時參加運算，結(jié)果

2、真值x＝－xn-2xn-3……x0

時，原碼、反碼和補碼與x的關系如下：

[x]原＝1xn-2xn-3……x0

[x]反＝1……[x]補＝1……(+1)

從而可知，在n位的機器數(shù)中，最高位為符號位，若該位為0真值為正，該位為1則真值為負；其余的﹙n－1﹚位為數(shù)值位，其取值為0或1。當真值為正時，原碼、反碼和補碼的數(shù)值位完全相同；當真值為負時，原碼的數(shù)值位保持真值的原樣，反碼的數(shù)值位為原碼的各位取反，補碼則是反碼的最低位加1。根據(jù)以上關系，很容易實現(xiàn)真值與機器數(shù)之間及三種機器數(shù)之間的相互。2、真值x＝－xn-2xn-3……x0時，原碼、反碼轉(zhuǎn)換。例1：已知計算機字長為8位，試寫出二進制數(shù)＋101010和－101010在機器中表示的原碼、反碼及補碼。首先寫出它們的真值。設該機器采用定點整數(shù)表示，則真值形式如下：

x＝＋0101010y＝－0101010真值x為正，故有[x]原＝[x]反＝[x][x]補＝00101010

真值y為負，有

[x]原＝10101010[x]反＝11010101

[x]補＝11010110轉(zhuǎn)換。例2：已知＝101101，求真值x。分析：最高位為符號位，先由[x]補求出[x]反

[x]反＝101101－1＝101100

[x]補＝110011從而有y＝－10011㈣運算基礎計算機中的運算有兩類，一是算術(shù)運算，另一類是邏輯運算。算術(shù)運算包括加、減、乘、除等四則運算。⒈邏輯運算常用的邏輯運算有邏輯乘﹙“與”運算﹚、邏輯加﹙“或”運算﹚、邏輯非﹙“非”運算﹚等運算，它們都是按位進行運算的，也稱邏輯操作。例2：已知＝101101，求真值x。①“與”運算﹙∧，·﹚“與”﹙AND﹚運算的規(guī)則如下：0∧0＝00∧1＝01∧0＝01∧1＝1式中，“∧”是“與”的運算符號，也可以用“·”代替?！芭c”運算的一般式為

C＝A∧B或C＝A·B＝AB②“或”運算﹙∨，＋﹚

“或”﹙OR﹚運算的規(guī)則如下：

0∨0＝00∨1＝11∨0＝11∨1＝1式中，“∨”是“或”的運算符號，也可以用“＋”代替?！盎颉边\算的一般式為

C＝A∨B或C＝A＋B①“與”運算﹙∧，·﹚③“非”運算“非”﹙NOT﹚運算的規(guī)則如下：＝1＝0式中，“ˉ”是“非”的運算符號。“非”運算的一般式為C＝④“異或”運算﹙﹚“異或”﹙EOR：ExclusiveOR﹚運算的規(guī)則如下：式中，“”是“異或”的運算符號。000=01=110=111=0“異或”運算的一般式為C＝AB③“非”運算000=01=110=111=0“異或”運算的一2、算術(shù)運算二進制的四則運算﹙按位進行運算﹚

例2：1110-0011＝？1110-001110111101×10011101000001101111010111010000001101例4：1000001101＝？例1：1001＋1000＝？

1001+100010001例3：1101×1001＝？100000110111011011101011011010002、算術(shù)運算例2：1110-0011＝？1110-

補碼加減運算⒈補碼加法設x,y為正或負整數(shù)的真值，則由補碼的定

[x]補＋[y]補＝[x+y]補﹙＊﹚應用這一公式很容易實現(xiàn)補碼的加法運算。例1：設x＝＋0110110,y＝－1111001。求x＋y＝？

解：在計算機中，真值x,y表示下列補碼形式

[x]補＝0,0110110[y]補＝1,0000111

根據(jù)﹙＊﹚式，有[x+y]補＝[x]補＋[y]補＝1，0111101

求得x＋y＝－1000011結(jié)果正確補碼加減運算例2：設x＝＋1010011,y＝＋0100101。求x＋y＝？解：[x]補＝0,1010011[y]補＝0,0100101

根據(jù)﹙＊﹚式，有[x+y]補＝[x]補＋[y]補＝0，1111000

求得x＋y＝＋1111000結(jié)果正確例3：設x＝－1000011,y＝－0100001。求x＋y＝？

[x]補＝1,0111101+[y]補＝1,1011111[x]補＋[y]補＝11,0011100丟失即[x]補＋[y]補＝[x+y]補＝1,0011100

求得x＋y＝－1100100結(jié)果正確該例中，因機器字長假定為8位，故[x]補＋[y]補的結(jié)果中最高位﹙“1”﹚無法保存，自動丟失，計算機中的實結(jié)果為1,0011100。例2：設x＝＋1010011,y＝＋0100101。求x＋y例4：設x＝＋1000101,y＝＋1100111。求x＋y＝？

解：[x]補＝0,1000101[y]補＝0,1100111[x]補＋[y]補＝1，0101100

即[x+y]補＝[x]補＋[y]補＝1,0101100

求得x＋y＝－1010100

顯然，該結(jié)果是錯誤的，因為兩個正數(shù)想加，其和不可能為負數(shù)。分析如下：

真值x和y所表示的十進制數(shù)分別為﹙＋69﹚10和﹙＋103﹚10，其和為﹙＋172﹚10。該十進制數(shù)所對應的二進制數(shù)為＋10101100，需用9位字長的機器數(shù)表示，現(xiàn)機器只有8位字長，無法表示，稱這種現(xiàn)象為“溢出﹙overflow﹚”。例4：設x＝＋1000101,y＝＋1100111。求x＋

在計算機中，一旦發(fā)生溢出，其運算結(jié)果肯定是錯誤的，機器將進行溢出處理。⒉補碼減法設x，y為正或負整數(shù)的真值，則可利用下列補碼關系求得x－y之值。

[x-y]補＝[x+(-y)]補＝[x]補＋[-y]補﹙＊＊﹚例如，設x＝＋1010101,y＝＋1100001。求x－y＝？

[x]補＝0,1010101－y＝-1100001

[-y]補＝1，0011111

故得[x-y]補＝[x+(-y)]補＝1，1110100

x－y＝－0001100在計算機中，一旦發(fā)生溢出，其運算結(jié)果肯定是錯誤的，機㈤字符的表示字符包括西文字符和中文字符。字符編碼的方法和簡單，首先確定需要編碼的字符總數(shù)，然后將每一個字符按順序編號，編號值的大小無意義，僅作為識別與使用這些字符的依據(jù)。

1、西文字符對西文字符編碼最常用的是ASCII字符編碼，即AmericanStandardCodeforInformationInterchange﹙美國信息交換標準代碼﹚。ASCII是用7為二進制編碼，它可以表示2即128個字符。每個字符用7位二進制碼表示，其排列次序為d6d5dd3d2d1d0，d6為高位，d0為低位。㈤字符的表示B6B5B4B3B2B1B0000001

010

011

100

101

110

111

0000

NUL

DLE

空格

0

@P

、p

0001

SOH

DC1

！

1

AQ

a

q

0010

STX

DC2

”

2

BRb

r

0011

ETX

DC3

#

3

CSc

s

0100

EOT

DC4

$

4

DT

d

t

0101

ENQNAK

%

5

EUeu

0110

ACKSYN

&

6

FVf

v

0111

BEL

ETB

'

7

GWg

w

1000

BS

CAN

（

8

HX

h

x

1001

HT

EM

）

9

IY

i

y

1010LF

SUB

*:

JZ

j

z

1011

VTESC+;K[k

{

1100FFFS,<L\

l|

1101CR

GS-

=

M]

m}

1110SO

RS·>

N^

n

～

1111SI

US

/

?O_

oDELB6B5B4000001

在ASCII碼表中，十進制碼值0～32和127﹙NUL～SP和DEL﹚共34個字符稱為非圖形字符﹙又稱為控制字符﹚其余94個字符稱為圖形字符﹙又稱為普通字符﹚。在這些字符中，從“0”～“9”、從“A”～“Z”、從“a”～“z”都是順序排列的，且小寫比大寫字母碼值大32，即位值d5為0或1，這有利于大、小寫字母之間的編碼轉(zhuǎn)換。計算機的內(nèi)部存儲與操作常以字節(jié)為單位，即8個二進制位為單位。因此，一個字符在計算機內(nèi)實際是用8位表示。正常情況下，最高位d7為“0”。在需要奇偶校驗時，這一位可用于存放奇偶校驗的值，此時稱這一位為校驗位。在ASCII碼表中，十進制碼值0～32和127﹙N

西文字符除了常用的ASCII編碼外，還有另一種EBCDIC碼。這種字符編碼主要用在大型機器中。EBCDIC代碼，即ExtendedBinaryCodedDecimalInterchangeCode﹙擴展的二—十進制交換碼﹚。EBCDIC碼采用8位二進制碼表示，有256個編碼狀態(tài)，但只選用其中一部分。1、漢字編碼英文是拼音文字，采用不超過128種字符的字符集就滿足英文處理的需要，編碼容易，而且在一個計算機系統(tǒng)中，輸入、內(nèi)部處理和存儲都可以使用同一編碼﹙一般為ASCII碼﹚。漢字是象形文字，種類繁多，編碼比較困難，而且在一個漢字處理系統(tǒng)中，輸入、內(nèi)部處理、輸出對漢字編碼的要求不盡相同。因此進行一系列的漢西文字符除了常用的ASCII編碼外，還有另一種字編碼轉(zhuǎn)換，用戶用輸入碼輸入漢字，系統(tǒng)由輸入碼找到相應的內(nèi)碼，內(nèi)碼是計算機內(nèi)部對漢字的表示，要在顯示器上顯示或在打印機上打印出用戶所輸入的漢字，需要漢字的字形碼，系統(tǒng)由內(nèi)碼找到相應的字形碼。全稱是GB2312—80《信息交換用漢字編碼字符集—基本集》，1980年發(fā)布，是中文信息處理的國家標準，也稱漢字交換碼，簡稱GB碼。一個國標碼占兩個字節(jié),每個字節(jié)最高位仍為“0”；英文字符的機內(nèi)碼是7位ASCII碼，最高位也是“0”。因為西文字符和漢字都是字符，為了在計算機內(nèi)部能夠區(qū)分是漢字編碼還是ASCII碼，將國標碼的每個字節(jié)的最高位由“0”變?yōu)椤?”，變換后的國標碼稱為漢字機內(nèi)碼。由此可知漢字機內(nèi)碼的每個字節(jié)都大于128，字編碼轉(zhuǎn)換，用戶用輸入碼輸入漢字，系統(tǒng)由輸入碼找而每個西文字符的ASCII碼值均小于128。漢字輸入碼是一種用計算機標準鍵盤上按鍵的不同排列組合來對漢字的輸入設計的編碼，目的是進行漢字的輸入，那么對于輸入碼，要求編碼要盡可能的短，從而輸入時擊鍵的次數(shù)就比較少；另外重碼要盡量少，這樣輸入時就可以基本上實現(xiàn)盲打；再者，輸入編碼還要容易學容易上手，以便推廣。為了漢字的輸出顯示和打印，需要描述漢字的字形，即對漢字的字形進行編碼，稱為漢字的字形碼，也稱為漢字字模。漢字字形碼通常有兩種表示方式：點陣方式和矢量方式。用點陣表示字形時，漢字字形碼指的就是這個漢字字形點陣的代碼。點陣規(guī)模越大，字形就越美觀，同時其編碼也就越長，所需的存儲空間也就越大。矢量表示方式存儲的是而每個西文字符的ASCII碼值均小于128。漢字輸入碼是一描述漢字字形的輪廓特征，當要輸出漢字時，通過計算機的計算，由漢字字形描述生成所需要大小和形狀的漢字點陣。二者的區(qū)別在于：前者編碼、存儲方式簡單、無需轉(zhuǎn)換直接輸出，但字形放大后產(chǎn)生效果差，而且同一種字體不同的點陣需要不同的字庫。矢量方式特點正好與前者相反。

描述漢字字形的輪廓特征，當要輸出漢字時，通過計算機

圖靈機模型及數(shù)據(jù)編碼1概述2圖靈機3數(shù)據(jù)在計算機中的表示圖靈機模型及數(shù)據(jù)編碼1概述2圖靈機3數(shù)據(jù)在計算機中1概述

圖靈機模型理論是計算機學科最核心的理論之一，它是在總結(jié)前人制造計算機思想的基礎上提出的理論計算模型，它不僅指導了現(xiàn)代電子計算機的設計，為計算機設計指明了方向，并且是算法分析和程序語言設計的基礎理論。盡管如此，圖靈機模型卻并不復雜，也許正因為如此，才注定了其在計算學科中所具有的強大生命力。掌握了圖靈機理論，等于獲得了學習計算機系統(tǒng)知識的“金鑰匙”。1概述圖靈機模型理論是計算機學科最核心的2圖靈機

在第一臺電子計算機ENIAC誕生的10年前即1936年，英國數(shù)學家圖靈發(fā)表了題為“論可計算數(shù)及其在判定問題中的應用”﹙OnComputerNumbersWithanApplicationtotheEntscheidungsProblem﹚的學術(shù)論文，奠定了學術(shù)界公認的現(xiàn)代電子計算機的理論和模型基礎。1、希爾伯特綱領

20世紀初，逐步形成了關于數(shù)學基礎研究的邏輯主義、直覺主義和形式主義三大流派。其中，形式主義流派的代表人物是數(shù)學家希爾伯特﹙D．Hilbert﹚。他在數(shù)學基礎的研究中提出了一個設想，其大意是：將每一門數(shù)學的分支形式化，構(gòu)成形式系統(tǒng)或形式理論，并在以此為對象的元理論即

2圖靈機在第一臺電子計算機ENIAC誕生的10年前元數(shù)學中，證明每一個形式系統(tǒng)的相容性，從而導出全部數(shù)學的相容性，希爾伯特的這一設想，就是所謂的“西爾伯特綱領”?！拔鳡柌鼐V領”的目標，其實質(zhì)就是要尋找通用的形式邏輯系統(tǒng)，該系統(tǒng)應當是完備的，即在該系統(tǒng)中，可以機械地判定任何給定命題的真?zhèn)巍?/p>

D．Hilbert

希爾伯特元數(shù)學中，證明每一個形式系統(tǒng)的相容性，從而導出全部D．Hil“西爾伯特綱領”的研究基礎是邏輯和代數(shù)，主要源于19世紀英國數(shù)學家喬治·布爾﹙G．Boole﹚所創(chuàng)立的邏輯代數(shù)體系﹙即布爾代數(shù)﹚。1854年，布爾在他的著作中成功地將“真”、“假”兩種邏輯值和“與”、“或”、“非”3種邏輯運算歸結(jié)為一種代數(shù)。這樣，形式邏輯系統(tǒng)中的任何命題都可用數(shù)學符號表示出來，并能按照一定的規(guī)則推導出結(jié)論。盡管布爾沒有將“布爾代數(shù)”與計算機聯(lián)系起來，但他的工作卻為現(xiàn)代計算機的誕生作了重要的理論準備。G．Boole喬治·布爾“西爾伯特綱領”的研究基礎是邏輯和代數(shù)，主要源于19世紀G．希爾伯特的工作建立在布爾工作的基礎上，并使其進一步具體化。希爾伯特對實現(xiàn)自己的綱領充滿信心。然而，1931年，奧地利25歲的數(shù)理邏輯學家哥德爾﹙K．G?del﹚提出的關于形式系統(tǒng)的“不完備性定理”中指出，這種形式系統(tǒng)是不存在的，從而宣告了著名的“西爾伯特綱領”的失敗。希爾伯特綱領的失敗同時也暴露了形式系統(tǒng)的局限性，它表明形式系統(tǒng)不能窮盡全部數(shù)學命題，任何形式系統(tǒng)中都存在著該系統(tǒng)所不能判定其真?zhèn)蔚拿}。希爾伯特的工作建立在布爾工作的基礎上，并使其進一步具

“西爾伯特綱領”雖然失敗了，但它仍然不失為人類抽象思維的一個偉大成果，它的歷史意義是多方面的。

首先，“西爾伯特綱領”是在保全古典數(shù)學的前提下去排除集合論悖論的，它給數(shù)學基礎問題的研究帶來了全新的轉(zhuǎn)機。其次，希爾伯特綱領的提出使元數(shù)學得到了確立和發(fā)展。最后，對計算學科而言，最具意義的是，希爾伯特綱領的失敗啟發(fā)人們應避免花費大量的精力去證明那些不能判定的問題，而應把精力集中于解決具有能行性的問題?！拔鳡柌鼐V領”雖然失敗了，但它仍然不失為人類抽象2、圖靈對計算本質(zhì)的揭示在哥德爾研究成果的影響下20世紀30年代后期，圖靈﹙A．M．Turing﹚從計算一個數(shù)的一般過程入手對計算的本質(zhì)進行了研究，從而實現(xiàn)了對計算本質(zhì)的真正認識。根據(jù)圖靈的研究，直觀地說，所謂計算就是計算者﹙人或機器﹚對一條兩端可無限延長的紙帶上的一串0和1執(zhí)行指令，一步一步地改變紙帶上的0或1，經(jīng)過有限步驟，最后得到一個滿足預先規(guī)定的符號串的變換過程。圖靈用形式化方法成功表述可計算這一過程的本質(zhì)。圖靈的研究成果是哥德爾研究成果的進一步深化，該成果不僅再次表明了某些數(shù)學問題是不能用任何機械過程來解決的思想，而且還深刻揭示可計算所具有的“能行過程”的本質(zhì)特征。2、圖靈對計算本質(zhì)的揭示

圖靈的描述是關于數(shù)值計算的，不過，我們知道英文字母表的字母以及漢字均可以用數(shù)來表示，因此，圖靈機同樣可以處理非數(shù)值計算。不僅如此，更為重要的是，由數(shù)值和非數(shù)值﹙英文字母、漢字等﹚組成的字符串，既可以解釋成數(shù)據(jù)，又可以解釋成程序，從而計算的每一過程都可以用字符串的形式進行編碼，并存放在存儲器中，以后使用時譯碼，并由處理器執(zhí)行，機器碼﹙結(jié)果﹚可以從高級符號形式﹙即程序設計語言﹚機械地推導出來。圖靈的研究成果是：可計算性＝圖靈可計算性。在進行可計算性問題的討論時，不可避免地要提到一個與計算具有同等地位和意義的基本概念，那就是算法。算法也稱為能行圖靈的描述是關于數(shù)值計算的，不過，我們知道英文方法或能行過程，是對解題﹙計算﹚過程的精確描述，它由一組定義明確且能機械執(zhí)行的規(guī)則﹙語句、指令等﹚組成。根據(jù)圖靈的論點，可以得到這樣的結(jié)論：任一過程是能行的﹙能夠具體表現(xiàn)在一個算法中﹚，當且僅當它能夠被一臺圖靈機實現(xiàn)。圖靈機等計算模型均是用來解決問題的，理論上的能行性隱含著計算模型的正確性，而實際實現(xiàn)中的能行性還包含時間與空間的有效性。方法或能行過程，是對解題﹙計算﹚過程的精確描述，它由3、圖靈機為紀念圖靈對計算機的貢獻，美國計算機博物館于1966年設立了“圖靈獎”計算機是使用相應的程序來完成任何設定好的任務。圖靈機是一種思想模型，它由三部分組成：一個控制器，一條可以無限延伸的帶子和一個在帶子上左右移動的讀寫頭。3、圖靈機為紀念圖靈對計算機的貢獻，計算機是使用相應的程序來

根據(jù)圖靈的觀點可以得到這樣的結(jié)論：凡是能用算法方法解決的問題，也一定能用圖靈機解決；凡是圖靈機解決不了的問題，任何算法也解決不了。今天我們知道，圖靈機與當時提出的用于解決計算問題的遞歸函數(shù)、λ演算和POST規(guī)范系統(tǒng)等計算模型在計算能力上是等價的。它們于20世紀30年代共同奠定了計算科學的理論基礎。相比于其他幾種計算模型，圖靈機是從過程這一角度來刻畫計算的本質(zhì)，其結(jié)構(gòu)簡單，操作運行規(guī)則也較少，從而為更多的人所理解。圖靈機的特征①圖靈機由一條兩端可無限延長的帶子、一個讀寫頭以及一組控制讀寫頭工作的命令組成，如圖所示。圖靈機根據(jù)圖靈的觀點可以得到這樣的結(jié)論：凡是能用算的帶子被劃分為一系列均勻的方格。讀寫頭可以沿帶子方向左右移動，并可以在每個方格上進行讀寫。②寫在帶子上的符號為一個有窮字母表：｛S0,S1,S2,…,SP｝。通常，可以認為這個有窮字母表僅有兩個S0、S1字符，其中S0可以看作是“0”，S1可以看作是“1”，它們只是兩個符號，要說有意義的話，也只有形式的意義。…

bb10100010bbb

…

狀態(tài)q1讀—寫頭控制器的帶子被劃分為一系列均勻的方格。讀寫頭可以沿帶子方向左…由字符“0”和“1”組成的字母表可以表示任何一個數(shù)。③機器的控制狀態(tài)表為｛q1,q2,…qm,｝。通常，將一個圖靈機的初始狀態(tài)設為q1，在每一個具體的圖靈機中還要確定一個結(jié)束狀態(tài)qw。一個給定機器的“程序”認為是機器內(nèi)的五元組﹙qiSjSkR﹙或L或N﹚ql﹚形式的指令集，五元組定義了機器在一個特定狀態(tài)下讀入一個特定字符時所采取的動作。

5個元素的含義如下：

qi表示機器目前所處的狀態(tài)；

Sj表示機器從方格中讀入的符號；

Sk表示機器用來代替寫入方格中的符號；

R、L、N分別表示向右移一格、向左移一格、不移動；

ql表示下一步機器的狀態(tài)。由字符“0”和“1”組成的字母表可以表示任何一個數(shù)。圖靈機的工作原理機器從給定帶子上的某起始點出發(fā)，其動作完全由其初始狀態(tài)及機內(nèi)五元組來決定。就某種意義而言，一個機器其實就是它作用于紙帶上的五元組集。一個機器計算的結(jié)果是從機器停止時帶子上的信息得到的。4、馮·諾依曼型計算機

1946年2月14日，世界上第一臺數(shù)字電子計算機ENIAC在美國賓夕法尼亞大學研制成功。該機是使用電子線路來執(zhí)行算術(shù)和邏輯運算以及信息存儲的真正工作的計算機器，它的成功研制顯示了電子線路的巨大優(yōu)越性。但是，ENIAC的結(jié)構(gòu)在很大程度上是依照機電系統(tǒng)設計的，還存在重大的線路結(jié)構(gòu)等問題。在圖靈等人工作的影響下，1946年6月，美國杰出的數(shù)學家馮·諾依曼及其同事完成了關于《電子計算裝置邏輯結(jié)構(gòu)設計》的研究報告，具體圖靈機的工作原理介紹了制造電子計算機和程序設計的新思想，給出了由控制器、運算器、存儲器、輸入和輸出設備5類部件組成的，被稱為馮·諾依曼型計算機﹙或存儲程序式計算機﹚的組織結(jié)構(gòu)，以及實現(xiàn)它們的方法，為現(xiàn)代計算機的研制奠定了基礎，至盡為止，大多數(shù)計算機采用的仍然是馮·諾依曼型計算機的組織結(jié)構(gòu)，只是作了一些改進而已。因此，馮·諾依曼被人們譽為“計算機器之父”。介紹了制造電子計算機和程序設計的新思想，給出了由控內(nèi)存儲器運算器外存儲器輸入設備輸出設備控制器數(shù)據(jù)信號控制信號注：馮·諾依曼型計算機的組織結(jié)構(gòu)內(nèi)存儲器運算器外存儲器輸入設備輸出設備控制器數(shù)據(jù)信號控制信號JohnvonNeumann馮諾依曼1949EDSAC存儲程序工作原理計算機的兩個基本能力：一是能夠存儲程序，二是能夠自動地執(zhí)行程序。計算機是利用“存儲器”（內(nèi)存）來存放所要執(zhí)行的程序的，而稱之為CPU的部件可以依次從存儲器中取出程序中的每一條指令，并加以分析和執(zhí)行，直至完成全部指令任務為止。JohnvonNeumann1949EDSAC存儲程序香儂是現(xiàn)代信息論的著名創(chuàng)始人。1938年，香儂在發(fā)表的論文中，首次用布爾代數(shù)進行開關電路分析，并證明布爾代數(shù)的邏輯運算可以通過繼電器電路來實現(xiàn)。阿塔納索夫提出了計算機的三條原則：1）以二進制的邏輯基礎來實現(xiàn)數(shù)字運算，以保證精度；2）利用電子技術(shù)來實現(xiàn)控制、邏輯運算和算術(shù)運算，以保證計算速度；3）采用把計算功能和二進制數(shù)更新存儲功能相分離的結(jié)構(gòu)。ClaudeShannon奠定現(xiàn)代計算機發(fā)展的重要人物和思想ClaudeShannon奠定現(xiàn)代計算機發(fā)展的重要人物和思3數(shù)據(jù)在計算機中的表示

計算機中的數(shù)據(jù)和指令都是用二進制代碼表示的，這是因為計算機的各組成部分是僅具有兩個穩(wěn)定狀態(tài)的物理元件—電子開關線路所組成。為此，要想深入學習計算機的各個部分，必須掌握二進制代碼的有關知識。計算機中用二進制代碼表示數(shù)據(jù)信息有兩種方法：①按“值”表示：在選定的進位制中正確地表示出數(shù)值，包括數(shù)字、符號、小數(shù)點位置及正負號等。如“－9.5”可表示為二進制的“－1001.1”。②按“形”表示：按照一定的編碼方法來表示數(shù)據(jù)。如用ASCII碼表示“－9.5”，其形式為0101101、0111001、0101110、0110101。

3數(shù)據(jù)在計算機中的表示計算機中的數(shù)據(jù)和指令1、進位制數(shù)及其相互轉(zhuǎn)化

(一)進位制數(shù)（進位計數(shù)制）數(shù)制的定義：用一組固定的數(shù)字(數(shù)碼符號)和一套統(tǒng)一的規(guī)則來表示數(shù)值的方法就叫做數(shù)制(numbersystem也稱計數(shù)制)。這一定義主要的內(nèi)涵是：(1)數(shù)制的種類很多，除了十進制數(shù)，還有二十四進制(24小時為一天)，六十進制(60分為1小時，60秒為1分)，二進制(鞋、襪、筷子等兩只為一雙)，等等。(2)在一種數(shù)制中，只能使用一組固定的數(shù)字來表示數(shù)的大小。數(shù)字在一個數(shù)中所處的位置稱為數(shù)位。具體使用多少個數(shù)字來表示一個數(shù)值的大小，就稱為該數(shù)制的基數(shù)(base)。例如，十進制數(shù)(Decimal)1、進位制數(shù)及其相互轉(zhuǎn)化的基數(shù)是10，使用0～9十個數(shù)字，二進制數(shù)(Binary)的基數(shù)為2，使用0，1兩個數(shù)字。在計算機文獻中，十進制數(shù)是在數(shù)的末尾加字母D來標識。例如，1989D，表示十進制數(shù)1989。一般情況下，1989就是一個十進制數(shù)，不在后面加D。二進制數(shù)是在數(shù)的末尾加字母B來標識。例如，101B，表示二進制數(shù)的101，即十進制數(shù)的5。(3)在一種數(shù)制中，有一套統(tǒng)一的規(guī)則。N進制的規(guī)則是逢N進1，或者借1為N。權(quán)或稱位權(quán)，是指數(shù)位上的數(shù)字乘上一個固定的數(shù)值。十制數(shù)是逢十進一，所以對每一位數(shù)可以分別賦以位權(quán)100，101，102，…。用這樣的位權(quán)就能夠表示十進制的數(shù)。的基數(shù)是10，使用0～9十個數(shù)字，二進制數(shù)(Binary)的基數(shù)某一基數(shù)中的最大數(shù)是“基數(shù)減1”，而不是基數(shù)本身，如十進制數(shù)中的最大數(shù)為(10－1＝)9，二進制數(shù)中的最大數(shù)為(2－1＝)1；最小數(shù)均為0。數(shù)位、基數(shù)和位權(quán)是進位計數(shù)制中的三個要素。采用二進制記數(shù)法原因目前，在計算機內(nèi)部，數(shù)據(jù)的計算和處理都采用二進制記數(shù)法，主要是由二進制數(shù)在技術(shù)操作上的可行性、可靠性、簡易性以及其邏輯性所決定的。(1)可行性若用十進制數(shù)，需要0，1，…，9等不同的10個基數(shù)，用電子技術(shù)實現(xiàn)這10種狀態(tài)就很困難。而用二進制數(shù)，則只需0，1兩個基數(shù)，要表示兩個狀態(tài)，這在電學技術(shù)上的基數(shù)實現(xiàn)最為容易。例如，電燈的亮和滅，晶體管的導通和截止，等等。(2)可靠性因二進制數(shù)只要兩個狀態(tài)，數(shù)字轉(zhuǎn)移和處理就不易出錯，這樣計算機工作的可靠性就高。(3)簡易性二進制數(shù)運算法則簡單。例如，二進制的加法、積法法則都只有三個。運算法則少，使計算機運算器結(jié)構(gòu)大大簡化，控制也可隨之簡化。(4)邏輯性由于二進制數(shù)只要0，1兩個數(shù)碼，可以代表邏輯代數(shù)中的“假”和“真”，這就是在計算機中使用二進制的邏輯性。實現(xiàn)最為容易。例如，電燈的亮和滅，晶體管的導通和截止，具體分析二進制、十進制、八進制、十六進制的性質(zhì)：①十進制﹙D﹚ⅰ具有十個數(shù)字符號0，1，2，3，…，9；

ⅱ逢十進一；

?；鶖?shù)為10，第i位的權(quán)為﹙10﹚i。舉例：﹙123.45﹚10＝1×102＋2×101＋3×100＋4×10-1

＋5×10-2表示方法：﹙123.45﹚10＝123.45D②二進制﹙B﹚ⅰ具有兩個數(shù)字符號0，1；

ⅱ逢二進一；

?；鶖?shù)為2，第i位的權(quán)為﹙2﹚i。具體分析二進制、十進制、八進制、十六進制的性質(zhì)：舉例：﹙101.101﹚2＝1×22＋0×21＋1×20＋1×2-1＋0×2-2

＋1×2-3表示方法：﹙101.101﹚2＝101.101B③八進制﹙Q﹚ⅰ具有八個數(shù)字符號0，1，2…，7；

ⅱ逢八進一；

?；鶖?shù)為8，第i位的權(quán)為﹙8﹚i。舉例：﹙137.43﹚8

＝1×82＋3×81＋7×80＋4×8-1

＋3×8-2表示方法：﹙137.43﹚8＝137.43Q舉例：﹙101.101﹚2＝1×22＋0×21＋1×20＋1④十六進制﹙H﹚?、【哂惺鶄€數(shù)字符號0，1，2…，9，A，B，C，D，E，F(xiàn)；

ⅱ逢十六進一；

?；鶖?shù)為16，第i位的權(quán)為﹙16﹚i。舉例：﹙147B.CD﹚16＝1×163＋4×162＋7×161＋

B×160＋C×16-1＋D×16-2表示方法：﹙147B.CD﹚16＝147B.CDH㈡進位制數(shù)的相互轉(zhuǎn)換

1、十進制數(shù)與二進制數(shù)間的相互轉(zhuǎn)換

①DB④十六進制﹙H﹚①D例1：﹙5﹚10＝﹙？﹚2﹙27﹚10＝﹙？﹚2251……0222……10……1227213……126……123……021……10……1即﹙5﹚10＝﹙101﹚2

﹙27﹚10＝﹙11011﹚2

例1：﹙5﹚10＝﹙？﹚2﹙27﹚10＝﹙？﹚2251例2：﹙0.625﹚10＝﹙？﹚2

0.625×21.250……1×20.50……0×21.0……1

即

﹙0.625﹚10＝﹙0.101﹚2

例3：﹙27.625﹚10＝﹙11011.101﹚2

口訣：整數(shù)部分，除2取余數(shù)，直到商為0。余數(shù)排列，由下到上；小數(shù)部分，乘2取整數(shù)，直到小數(shù)部分為0﹙或達到所求的精確度﹚。整數(shù)排列，由上到下。例2：﹙0.625﹚10＝﹙？﹚20.625×將二進制數(shù)的各位按權(quán)展開相加。例4：﹙101﹚2＝﹙？﹚10

﹙101﹚2＝1×22＋0×21＋1×20＝﹙5﹚10例5：﹙11011.101﹚2＝﹙？﹚10﹙11011.101﹚2＝1×24＋1×23＋0×22＋1×21＋1×20

＋1×2-1＋0×2-2＋1×2-3

＝27＋0.5＋0.125

＝﹙27.625﹚10②BD②BD2、十進制與八進制間的相互轉(zhuǎn)化①DQ

同與二進制間的轉(zhuǎn)化類似，整數(shù)部分除以8，取余數(shù)；小數(shù)部分則乘以8，取整數(shù)。