一千萬個為什麽

搜索

使用負面結果證明可計算性理論的積極結果

密碼學中的許多結果取決於復雜性理論中的不可能性結果/猜想。例如,使用RSA的公鑰加密被認為是可能的,因為關於因子分解的不可行性(以及模塊化根發現問題)的猜想。

我的問題是:

我們在可計算性理論上有類似的結果嗎?是否有使用負面不可能性結果的有趣的積極結構?

例如,停止問題的不確定性是否允許我們執行如果停止問題是可判定的,我們將無法執行的任務?

最佳答案

從某種意義上說,這就是參數化理論的全部意義所在。

數據抽象是我們如何確保模塊的任何客戶端都不能訪問模塊的元素,除非根據模塊公開的接口。 我們依賴於此來確保模塊的客戶端不能破壞數據結構的內部不變量 - 例如,如果僅通過已發布的接口訪問平衡樹,則表明樹將始終保持平衡。

因此,我們使用負面屬性 - 沒有可能的客戶端可以打破抽象邊界 - 推斷出正面的 - 數據表示不變總是成立。

轉載註明原文: 使用負面結果證明可計算性理論的積極結果