可計算性簡介

導論篇 計算理論簡介 計算理論的歷史 可計算性 可計算性簡介 圖靈機 不可計算問題 遞歸可枚舉 不完備定理 複雜度 複雜度簡介 複雜度理論 NP-Complete 隨機複雜度 密碼學理論 趨近演算法 訊息 相關網站 參考文獻 最新修改 簡體版 English

文章 邏輯悖論 - 理髮師問題 有一個理髮師，宣稱為所有不自己剪頭髮的人剪髮，但不為所有自己剪頭髮的人剪髮 請問：該理髮師說的有可能是真的嗎? 答案：不可能，因為有矛盾，矛盾如下。 若該理髮師為自己剪髮，則該理髮師為一個自己剪髮的人剪髮，因而不符合宣稱的行為 若該理髮師不為自己剪髮，則該理髮師漏掉一個人，因而不符合宣稱的『所有』 電腦能力的極限 – 停止問題 若將資料 I 輸入到程式 P，則會有兩種可能的情形 (1) 在某個時間後停止了 (2) 永遠不會停止 (當機了) 停止問題 (Halting Problem) :我們能否設計一個程式Ｈ，判斷 P 在輸入 I 後會不會當機 Halting Problem 的數學描述 H(P,I) = "halt" if P(I) halt = "loop forever" if P(I) loop forever 假如 H 存在，則我們可以建立一個程式 K，使得 K(P) = if H(P,P)="halt" then loop forever else halt 如此、請問 H(K,K) 應該是甚麼呢? Halting Problem 不可解 If H(K,K)="halt" K(K) loop forever If H(K,K)="loop forever” K(K) halt H is not correct anyway. 用程式說明停止問題 K(P) { if H(P, P) == "halt" { while (true) { } } else { } } Facebook 留言 Facebook Wikidot Post preview: Close preview or Sign in as Wikidot user (will not be published) - + Help: wiki text quick reference 授權 本網頁的作者、授權與引用方式 作者 陳鍾誠，於金門大學資訊工程系，電子郵件：wt.ude.uqn|ccc#wt.ude.uqn|ccc，網站：http://ccckmit.wikidot.com。 授權 本文採用創作共用 (Creative Common) 3.0 版的 姓名標示─非商業性─相同方式分享 授權條款，歡迎轉載或修改使用，但若做為商業使用時必須取得授權，引用本文時請參考下列格式。 中文版 (APA格式) 陳鍾誠 (24 Aug 2010 12:49)，(網頁標題) 可計算性簡介，(網站標題) 陳鍾誠的網站，取自 http://ccckmit.wikidot.com/ct:computabilityintroduction ，網頁修改第 5 版。 英文版 (APA格式) Chung-Chen Chen (24 Aug 2010 12:49), Retrieved from http://ccckmit.wikidot.com/ct:computabilityintroduction , Page Revision 5.