Chapter12运算理论.ppt
《Chapter12运算理论.ppt》由会员分享,可在线阅读,更多相关《Chapter12运算理论.ppt(27页珍藏版)》请在三一文库上搜索。
1、Chapter 12 運算理論,12.1 函數及其運算 12.2 杜林機器 12.3 全能程式語言 12.4 不可計算函數 12.5 問題的複雜度 12.6 公開金鑰密碼學,12.1 函數及其運算,函數(function)是一種介於一群可能的輸入值與一群輸出值的對應關係,而使得每一個可能的輸入均可對應到一個唯一的輸出。 決定一個函數在指定特定輸入值之後會產生特定輸出值的過程,稱為函數計算(computing the function)。 這些函數的計算超出任何演算法系統的能力,這類函數稱為不可計算的(noncomputable),輸出值可以用演算法依輸入值決定的函數則稱為可計算的(comput
2、able)。,圖 12.1 試圖顯示出一個將碼的度量轉換成公尺,12.2 杜林機器,杜林機器基礎 一部杜林機器(Turing machine)具有一個控制單元,可以利用讀/寫頭在磁帶上讀寫符號(圖 12.2)。 任何時間,機器必須處於一組有限數量的狀況,稱為狀態(state)中的一種狀況。開始於起始狀態(start state),停止為停止狀態(halt state)。 機器的磁帶看起來如右圖:,圖 12.2 杜林機器的元件,圖 12.3 將其數值遞增的杜林機器,一個能用杜林機器計算出的函數即稱為杜林可計算(Turing computable)。 杜林機器的計算能力涵蓋了任何演算式機器的計算能
3、力。 這個假設稱為 Church-Turing 命題。 這個假說的重要性是,它使我們可以洞察計算機器的能力及極限。,12.3 全能程式語言,一個簡單的命令式程式語言,它足以讓我們表示出計算所有杜林可計算函數的程式。 稱為全能程式語言(universal programming language)。 精簡程式語言 clear name; incr name; decr name;,一個控制結構(control structure),以 while-end 表示:,用精簡程式語言寫程式 真正目標是探究哪些是可能的(possible),而不是研究哪些是實際可行的(practical)。 精簡程式語言
4、的全能性 研究學者已經證明,精簡程式語言可以用來表示各種能計算出杜林可計算函數的演算法。 隱喻著任何可計算函數都可以被以此精簡程式語言所寫的程式計算出來。,圖 12.4 用來計算 X Y 的精簡程式, 圖 12.5 將指令 “copy Today to Tomorrow” 轉換成精簡程式語言程式,12.4 不可計算函數,停止問題 停止問題是試圖預言,一個程式在某特定條件下啟動後是否會終結(或停止)的問題。 自我參用(self-reference)的技術亦即一個物件參用本身的觀念。 自我終結的(self-terminating):一個程式是自我終結的,如果其執行以其本身作為輸入而會終止時。,圖
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Chapter12 运算 理论
链接地址:https://www.31doc.com/p-2102160.html