算法不可解性

算法（Algorithm）是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統的方法描述解決問題的策略機制。算法不可解性是指對於某個問題構造一個算法，通過這個算法可以決定任意給定的整係數多項式有無整數零點，很長一段時間，很多可判定問題沒有得到解決，即問題本質是不可判定性。

基本介紹

• 中文名：算法不可解性
• 外文名： algorithmic unsolvability
• 學科：計算機
• 定義：問題在有限時間內無法解決
• 有關術語：算法
• 領域：算法設計

簡介

在計算機科學中，算法不可解性是指將某一個問題設計成一個算法，利用現有計算機技術，無法在有限時間或記憶體空間內求出問題的一個可行性解。算法不可解性一般是由兩個原因造成的：1、當前計算機技術還不夠好，例如硬體處理速度，記憶體大小；2、有關理論還不夠完善，有待進一步發展。與算法不可解性相反的是，算法可計算性，即可計算性理論。

可計算性理論

可計算性理論，亦稱算法理論或能行性理論，計算機科學的理論基礎之一。是研究計算的一般性質的數學理論。可計算性理論通過建立計算的數學模型，精確區分哪些是可計算的，哪些是不可計算的。計算的過程是執行算法的過程。可計算性理論的重要課題之一，是將算法這一直觀概念精確化。算法概念精確化的途徑很多，其中之一是通過定義抽象計算機，把算法看作抽象計算機的程式。通常把那些存在算法計算其值的函式叫做可計算函式。因此，可計算函式的精確定義為：能夠在抽象計算機上編出程式計算其值的函式。這樣就可以討論哪些函式是可計算的，哪些函式是不可計算的。套用計算性理論是計算機科學的理論基礎之一。早在30年代，圖靈對存在通用圖靈機的邏輯證明表明，製造出能編程式來作出任何計算的通用計算機是可能的，這影響了40年代出現的存儲程式的計算機（即馮諾依曼型計算機）的設計思想。可計算性理論確定了哪些問題可能用計算機解決，哪些問題是不可能用計算機解決的。可計算性理論中的基本思想、概念和方法，被廣泛用用與計算機科學的各個領域。建立數學模型的方法在計算機科學中被廣泛採用。遞歸的思想被用於程式設計，產生了遞歸過程和遞歸數據結構，也影響了計算機的體系結構。

時間複雜度與空間複雜度

時間複雜度

算法的時間複雜度是指執行算法所需要的計算工作量。一般來說，計算機算法是問題規模n 的函式，算法的時間複雜度也因此記做：

因此，問題的規模n 越大，算法執行的時間的增長率與f(n) 的增長率正相關，稱作漸進時間複雜度（Asymptotic Time Complexity）。

空間複雜度

算法的空間複雜度是指算法需要消耗的記憶體空間。其計算和表示方法與時間複雜度類似，一般都用複雜度的漸近性來表示。同時間複雜度相比，空間複雜度的分析要簡單得多。

本質不可判定性

本質不可判定性(essential undecidability)一個不可判定的數學理論。若一個數學理論T是不可判定的，且其任意無矛盾擴張也是不可判定的.則稱其為本質不可判定的。本質不可判定的概念和思想對證明許多數學理論的不可判定性有很大作用。如果能證明某一本質不可判定理論T'可在理論T中解釋，則可知理論T是不可判定的.本質不判定理論的最某本的一個例子早佩亞諾算術系統。

判定性是指一個詢問真 / 假的問題是否可被回答。若不論一個問題答案為真或為假時均能得出該答案，則稱這個問題、或解決該問題時所用的算法為可判定的；若只能在答案為真時得出、但在答案為假時不能做出判斷，那么稱為半可判定的；若根本不能得出為真或為假的結論，那么稱為不可判定的。

不可判定問題列表

邏輯問題

大衛·希爾伯特的可判定性。

二階Λ演算的類型推論和型別檢查。

抽象機器問題

停機問題（決定圖靈機是否停機）

決定圖靈機是否Busy beaver（最長運行的圖靈機有相用的停機問題）

死亡率問題（mortality problem）

萊斯定理指出所有partial方程的非凡屬性，決定機器計算partial方程與其屬性是否未決定。

矩陣問題

矩陣的致命問題：表達，一個有限集合的n × n矩陣的整數項，是否能有規律地倍增，重複出現，生成零矩陣。（已知一組15個或更多的3 × 3的矩陣及2組的45 × 45矩陣是未決定問題）

決定一個有限集合的上三角形3 × 3矩陣與非負整數項能否組成一個自由半群。

決定兩個有限生成的Mn(Z)子半群是否有相同的元素。