演演算法不可解性

在計算機科學中，演演算法不可解性是指將某一個問題設計成一個演演算法，利用現有計算機技術，無法在有限時間或內存空間內求出問題的一個可行性解。演演算法不可解性一般是由兩個原因造成的：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)子半群是否有相同的元素。