算法不可解性（算法不可解性）

简介

在计算机科学中，算法不可解性是指将某一个问题设计成一个算法，利用现有计算机技术，无法在有限时间或内存空间内求出问题的一个可行性解。算法不可解性一般是由两个原因造成的：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)子半群是否有相同的元素。