先定义这么一些东西：
由此可知，T(L) 中图灵机的数量有不等式： 。
另一方面，函数 S(t) 与 S(L) 都是不可计算的，这点很容易证明：
假定 S(t) 是可计算的，那么我们可以构造如下程序：
很显然， paradox(paradox) 是一个矛盾，因为对于程序 paradox 的任意输入程序 t，它都会在执行 步后停机，因此 paradox(paradox) 会在执行 步后停止。但 本就是程序 paradox 执行步骤，从而构成矛盾 。
同理，构造如下程序：
这就构成了一个停机判定函数，因为对于任意输入的程序 t，都可以通过 t 自身的长度 l 来利用程序 S 获得长度不超过 l 的可停机图灵机的最大执行步骤 S(l)，那么如果在 S(l) 步内都没停机的话，就肯定不会停机了。
但我们知道，停机判定函数是不可计算的，因此 S(L) 必然也是不可计算的，从而上述程序无法在图灵机体系内被表达出来。
非但如此，我们由此也可以证明， 的上界，也是不可计算的，这点很显然。
但，我们可以构造一个有意思的程序：
这个程序的作用，是判断程序 t 在 s 步内是否会停机，但即便在 s 步内不会停机，我们也不能说 t 就不会停机。我们将这个程序记为符号 ，因此停机判定函数可以形式地记为 。
下面来看另一个问题，就是我们能否确定 的下界？虽然它本身及它的上界都是不可计算的，但我们能否推算出它的下界呢？
可以构造如下程序：
这个程序的作用很明显，就是在执行 s + 1 步后停机。下面，我们如果通过图灵机之外的手段计算出了长度不超过 L 的可停机图灵机的最大执行次数 的话，将其输入到程序 loop 中，自然会在执行 步后停机了，那么此时这个程序自己长多少呢？
loop(s) 的长度为 ，其中 n 是程序所选语言的字母表中用于表示数字的符号数，c 是与 s 无关而只与所选语言相关的常数。从而如果 ，则会出现矛盾，因为此时这个程序本身需要执行的步骤数应该不大于 L，但这个步骤数为 L + 1，从而是矛盾的，由此可知，唯一的可能就是 。
事实上，我们可以将上述程序中的外源常数 s 替换为能生成 s 的最短程序，那么此时就有不等式：
其中第二个不等式是由于数字 s 至少可以表达为在 loop 程序中直接写 s，而这么做的长度为 。
我们不妨将 K 氏复杂度写为 ，且 ，从而可得：
由此我们可以得到 S(L) 的下界——当然，实际上的 S(L) 可以比这个下界大很多。
现在我们换一个角度来看这个问题，有没有可能把这个下界进一步往上推？比如下面这段程序：
其中程序 generate 可以生成自然数。而这段那程序的执行步骤数为 s = generate() + 1。假定这段程序的长度是 L，那么存在只与语言相关的常数 c，使得 generate 程序的长度为 L - c，从而我们有不等式 。
也就是说，对于长度不超过 L 的图灵机能生成的最大自然数 与长度不超过 L 的可停机图灵机的最大执行步骤数 之间存在如下关系：
长度为 L 的图灵机能生成的最大自然数，最少也是直接用所有 L 位都来表达数字所得的自然数，所以有：
因此， 是比 更大的下界。
那，这个数可以有多大呢？这取决于语言中允许的数学运算算符有哪些，当然更重要的是我们如何写生成程序（循环和递归可以产生很大的数，只要写得好）。
比如说，加法运算中，生成结果的算式的总长度总是大于最终结果的；而在乘法运算中，算式长度等于结果加上乘法数量；幂次运算可以大幅减少算式长度，如果只是高阶幂次的话，就可以用少量算式得到更大的数值。比如下面这种情况：
这里的运算是从右往左。
如果一门语言支持上述这种三目运算 ，则如下程序可以输出极大值：
当然，这还不是能构造的最大输出结果，随着 L 的增加，可以有更复杂的形式，输出更大的结果。
回到之前的结果，最大执行步骤数比程序能表达的最大自然数还要大，这点也从侧面说明了这个最大执行步骤数是不可计算的。
而这点从另一面反应出，当 L 趋向无穷时，T(L) 中的图灵机会以图灵机无法计算的方式更快地趋向无穷。换言之，我们无法使用任何图灵机来给出一个完备的计算，其中包含所有 L 趋向无穷时能停机的图灵机。
也就是说：
故而，所有基于 集的计算， 要么是不完备的（即不可能遍历这个集合的所有元素），要么是图灵机无法实现的 。
接下来，再看一个问题：长度不超过 L 的图灵机，执行 T 步时正好停机的图灵机的数量记为 ，则 Q 是否是可计算的？
若 可计算，则我们可以构造如下一段程序：
这段程序很有意思，其中 c 是一个常数，它存在一个特殊的不等式（其中 L = Qs.length）：
其中 e 是一个只与语言本身有关的常数。这里不等式左侧源自 Q 的定义所要求的“长度不超过 L”，而右侧是程序 temp 的长度，其中第二项源自输入的参数 s。
如果该不等式满足，则可以构造出这么一个矛盾：此时 for 循环中的每个 temp 函数都是长度不超过 L + c 且都执行 T 步就会停机的程序，而这样的程序总共至少有 q + 1 个，其中 q 是目标 Q 程序计算出来的这样的程序的数量上限，因此就存在矛盾。
也就是说，只要能找到 c 让上述不等式成立，则 就必然是不可计算的因为能构造出矛盾。
而我们又知道， 存在一个天然上限，那就是 L 个字符能构成的所有可能图灵机的总量 ，因此我们有：
由于 L 和 e 在这里都是确定的常数，而当 c = 0 时该不等式不成立，同时右侧的增涨速度在 c 大于 1 后必然大于左侧，所以只要 c 足够大右侧必然会超过左侧使得不等式成立，所以总能找到 c 使得这个不等式成立。
因此，这就证明了， 是不可计算的。
这点其实也很自然，因为 可以给出 Chaitin 常数，而后者是不可计算的。
而且，非但 是不可计算的，它的任何小于自然上界的上界函数也是不可计算的。
虽然 是不可计算的，但我们依然可以设法找出它的下界。
把上面那段程序略作修改：
对于这个函数，我们可以输入任意足够大的 L 与任意 T，而 s 是任意字符串，满足下面的关系即可（取 ）：
接着，如果我们将 L 和 s 这两个输入参数作为程序中的常数，而 T 作为输入用来给出输出，那么这样的程序满足长度为 L 与执行步骤为 T 这两个要求，而这样的程序本身随着输入 s 的不同而不同，所以总共有 个。
因此，我们有：
事实上，这个结果可以进一步提升为（从而从可计算变成了不可计算）：
这里函数 表示要生成数值 x 所需的最短程序的长度，包括直接外部输入 x 这一方式在内，从而它和 x 的 K 氏复杂度其实是一回事，只不过专注于输出 x 为自然数的情况。
接着，由于 Chaitin 不完备定理：
我们可以得到一条等价的不完备定理：
这个证明很简单。假定这条命题可证，则我们实际上便证明了某个 T 使得 Q 的下界小于足够小的 q。而，我们知道 ，因此有：
由 Chaitin 不完备定理可知，我们无法证明对一个足够大的 m，能找到某个 T 满足 ，这就是说，我们无法证明对于一个足够小的 M，某个 T 使得 成立。由于 L 和 q 都是有限的，而对于任意有限的 T，对应的 也都必然是一个有限值，且只要 L 足够大则 必然大于 0，所以这就等于说，我们无法证明对于一个足够小的 m，能找到某个 T 使得 Q 小于 m ——否则我们实际上就能证明 Q 的上述下界小于 m，从而证明 Chaintin 不完备定理已经证明了的我们不能构造性地证明的 了。
更进一步，这条不完备性定理其实是说， 当 L 足够大时，对于任意 T 我们只能证明 T(L,T) 要么是 0 要么不是，但无法证明它小于某个大于 0 的值 。
我们还可以进一步得到如下这条不完备定理：
这是因为，如果这个定理不成立，则我们可以证明执行次数超过 T 的图灵机的数量足够少，假定这个足够少的数量是 M，即 。
那么，由于 Q 至少不小于 0，这就表示 。而我们知道，对于足够小的 m 我们无法构造性地证明存在 T 使这个不等式成立，从而证明了不存在这样一个 T，容许我们构造性地证明执行次数超过 T 的图灵机的数量是足够少的。
这里岔开一下，说一下 Chaitin 不完备定理。
对于任意给定自然数 n，事实上我们可以证明必然存在某个字符串 s 使 ，因为如果不存在这样的 s，那就表示我们可以用最多 个字符串（这里 d 表示字符集字符数）来生成所有可能出现的无穷多的字符串，这显然是不合理的。
但 Chaintin 不完备定理则告诉我们另一件事：当 n 足够大时（且 n 只与所选语言有关，是一个语言的常数），我们无法在一个足够强的形式系统中形式化地找出这样一个 s 来满足上面这个不等式。
换言之， 对于足够大的 n（且 n 是只与语言有关的常数），所有我们可以构造出来的字符串 s 都无法满足 。
这里的关键就是“构造性”这个限定，即我们可以证明 s 的存在，但永远找不到这样一个 s。
让我们来看一下这个颇神奇的类似 Berry 悖论的 Chaitin 不完备性的证明过程。
我们可以通过哥德尔编码在自然数与形式证明过程之间建立对应，同时我们又总可以验证给定的形式证明过程是否证明了上述不等式。现，假定程序 process(i) 将自然数 i 映射为形式证明过程 p， available(p,n) 验证形式证明过程 p 是否是关于上述不等式的有效验证过程， proof(p,n) 则判断形式证明过程 p 是否证明了某个字符串 s 的 K 氏复杂度大于自然数 n，最后程序 string(p) 则是将证明过程 p 中证明的字符串 s 提取出来。
接着，我们可以构造如下程序：
显然， find 程序的作用，就是遍历所有可能自然数，找出其中关于上述不等式的形式证明，并且当该形式证明证明该不等式成立时，返回这个形式证明过程中用到的字符串 s。
也就是说，这个程序的作用，就是遍历所有形式证明，然后返回被证明 K 氏复杂度大于 n 的字符串 s。
接着，这个程序多长？其中输入参数 n 之外的部分的长度假定为 P，而输入参数 n 的长度为 ，因此这个程序的总长度为 。
有趣的地方来了——它本身也可以返回字符串 s，且该字符串被证明 K(s) > n，但生成 s 的这段程序本身的长度为 ，且根据 K 氏复杂度的定义我们有 ，而很显然，总存在 n 使得 ，这里就出现了矛盾。
因此，这就表示说，要么不存在这样的证明也即该命题不可证，要么这个证明过程中没有构造性地给出字符串 s。前者表示 if 判断的第二个条件永远无法满足，所以程序不停机，故而无输出；后者则表示形式证明 p 虽然证明了 s 的存在，但并没有构造出这样的 s，所以 string(p) 无输出。
当然，还有另一种可能，就是 available(p,n) 永远不返回 true，即我们要么永远无法判断一个证明过程是否是关于上述不等式的，要么就是不存在这样的证明。或者就是这个程序并不存在。
事实上，由此就可以证明，不存在证明某个 s 满足上述不等式的证明，因为只要存在这样的证明，就可以被上面构造的悖论函数枚举出来，从而构造出悖论。
现在回到函数 上来。
对于前面提到的下界函数 ，显然当 时该下界为 0，但在这个极限 T 之前，当 L 足够大且 n 至少为 2 的情况下，则有：
这个下界很有意思，因为这就表示， 当 L 趋向无穷时，执行不超过任意有限 T 步便可停机的图灵机的总数，占所有可停机图灵机的比重会趋向于 0 。
也就是说，从全局看，执行有限步就停机的图灵机永远是稀疏的。
使用 函数我们可以估算 Chaitin 常数的下限（ 为长度不超过 L 的图灵机的总数）：
而由于 ，再利用斯特灵公式可得：
也就是说，在长度不超过 L 的所有图灵机中，随便一个图灵机会停机的概率（L 阶 Chaitin 常数）下限可以通过语言相关的常数 n 和 q 决定，也由此可以得出 Chaitin 常数的下限为：
当然，这个值非常非常小，比如以 ASCII 码来编写的话，n = 128，q 则差不多为 40，所以这个值小得可以忽略，从而从侧面作证了可停机图灵机有多稀疏。
有人估算 Chaitin 常数差不多是 0.007875，比这里计算的下限大了很多，由此可见这里计算的 Q 的下限果然比实际的 Q 小了很多。
我们可以取 为所有长度不超过 L、执行步骤不超过 T 便能停机的图灵机在所有长度不超过 L 的图灵机中的比例，则有如下下界（取 ）：
当 L 很大时，这个下限可以写为：
这就表示，当 L 足够大时，不那么大的 T 所对应的执行次数不超过它便停机的图灵机的数量的占比，几乎为 0。
或者，更进一步说，就是在“所有图灵机”这个集合中，对于任意有限次执行后便能停机的图灵机数量的占比，几乎为 0。
而，由于 Q 本质上是不可计算的，Q 的上限也是不可计算的，所以我们无法通过任何遍历可枚举语言告诉图灵机随着 L 的增长，T 的上限应该怎么取，才能使得不大于 T(L) 的可停机图灵机的总数能不“几乎为零”。
还有一些很有趣的问题，涉及到一些很有趣的 AIT 函数。
比如，令 代表字符串 s 是否可压缩的函数，即：
以及，将字符串根据其哥德尔数进行排序，函数 代表不大于 n 的自然数通过哥德尔解码所得的字符串中能被压缩的字符串的数量，而用 代表长度不超过 l 的所有字符串中能被压缩的字符串的数量。
这两个函数是否可计算呢？
让我们先来看“压缩判定函数” 。我们可以构造如下程序：
其中参数 c 是程序 find 的长度。因此，如果压缩判定函数存在且可计算，则上述程序会找出第一个被判定为不可压缩且长度大于这段程序长度的字符串，并返回——这样就构成了矛盾，这个程序可以生成该字符串，而生成的条件是这个字符串不可压缩且长度大于这段程序，因此这段生成该字符串的程序本身就是这段程序的一个压缩，从而构成矛盾。
这就是说，我们非但无法通用地计算一个字符串的不可压缩长度，而且甚至无法通用地判断该字符串是否可压缩。
因此，也就很容易证明， 也是不可计算的，因为如果它是可计算的，我们便可以利用哥德尔编解码与 函数来构造出压缩判定函数 ，而后者已经被证明是不可计算的了，所以 也只能是不可计算的。
下面就是那个有趣的问题：长度不超过 L 的字符串中，可压缩的字符串的数量 是多少？
我们可以先来算一下它的上限——当然，它当然不会大于 ，这是长度不超过 L 的所有字符串的数量。
在最好情况下，我们可以这么来想：每个长度不足 L 的字符串，都是更长字符串的不可压缩表示。我们甚至认为如果一个字符串 A 可以用另一个字符串 B 生成（即 B 作为程序运行，生成结果为 A），那么 B 的不可压缩表示也可以是 A 的表示，即此时允许两个字符串有一个共同的不可压缩表示。
在这个情况下，那么最优情况下，长度为 L 的所有字符串中，可以被压缩的字符串的数量上限为 。因此，长度不超过 L 的所有字符串中，可以被压缩的字符串的一个很自然的上限就是：
如果考虑到程序表达一个字符串至少需要一个函数前缀与后缀，将这两个的总长度记为 q，则有：
所以，当 L 很大时，长度不超过 L 的字符串可以被压缩的概率上限约为：
实际情况中，压缩概率当然是远小于这个上限的。
这个值还有很多别的估算方法。
比如说，上面所计算的，是每个长度不足 L 的字符串都可以对应到图灵机，从而生成一个长度为 L 的字符串，且该字符串还可以被作为图灵机继续生成字符串。
但图灵机生成的结果依然是图灵机的概率，是很低的，更不说生成图灵机的图灵机了。所以，我们可以近似地用 Chaitin 常数来对上限进行下调：
这里第二步的近似是因为 C 已知非常小，第三步的近似是考虑 L 很大的情况。
相应的，此时压缩概率为：
由此我们可以看到，任意一段字符串可以被压缩的概率的上限，比这段字符串对应的图灵机可以停机的概率小很多。
下面取一个有趣的比值——
将上面计算的长度不超过 L、执行次数不超过 T 即停机的图灵机数量的数量比例下限 ，与这里求的压缩概率上限 的比 ，其在 L 趋向无穷大、n 也远大于 1 时的下限为：
接着，我们取 ，则有：
这便是说，该下限严重依赖于 T 随 L 增大的方式，尤其与“长度不大于 L 的图灵机能表达的最大自然数”这一一个不可计算数密切相关，因为这里我们取的是它的下限 来作下限计算的。
这也就从侧面说明了，对于这类涉及到 L 趋向无穷时、长度不超过 L 的图灵机所构成的集合这一对象的计算，其结果在很大程度上都与相关量在 L 趋向无穷时的行为相关。
当然，上面的结果其实只是在重复这么一个事实：在所有可以写出的图灵机中，能停机的图灵机是非常稀少的，能被压缩的更加稀少，且绝大多数可停机图灵机都会需要在执行不可计算多步后才能停机。
我们真正感兴趣的，是所有图灵机这个集合本身所具有的一些特殊结构，尤其是在图灵机本身足够大的情况下，是否存在一些特殊的结构——当然，这些结构显然都是不可计算的。
所以，这一目标类似于在使用没有调焦的显微镜查看被一团迷雾包裹的培养皿，并试图画出其中细菌组成的纹路结构。
尤其是，上面构造的许多悖论式的程序来论证某些数是不可能通过图灵机计算得到的，这些悖论式结构本身有种“车轱辘话”的感觉，我们如果采用多值逻辑，或者引入别的数学结构，很可能会得到不同的东西。
下面我们来尝试构造一下遍历可枚举语言中更有趣的一些结构。
这里，我们将图灵机及输入参数合在一起构成一个字符串，比如如下这样：
这样，当选择要一种遍历可枚举语言或者说一种通用图灵机后，就可以将其中的所有程序与字符串等同。我们称字符串 A “描述”了图灵机 T，如果字符串 A 可以对应到上述程序加输入参数的形式。如果 A 描述了 T，则反过来称 T “实现”了 A。
进一步，如果 T 最终可以以接受状态停机，则称 T 是一台“良性图灵机”，对应的 A 称为“良性字符串”。
作为字符串，可以自然构造任意两个有限长字符串 A 和 B 之间的“距离”：
定义操作 为对字符串 s 进行下列四个操作中的任意一种：
因此，如果 即对字符串 A 进行 n 次 O 操作后得到字符串 B，则这样 n 个操作构成了一条从 A 到 B 的“路径”，该路径长度为 n。
于是，我们定义定义：从 A 到 B 的所有路径的最短长度，为 A 到 B 的距离，记为 。
容易证明，上述定义的距离是对称的，任意两个不同有限长字符串之间如上定义的距离总是一个自然数，且满足三角不等式。
然后，上述字符操作总是可以通过图灵机实现的，因此每条从 A 到 B 的路径 P 都对应一组图灵机，之所以是一组而非一个，是因为即便是确定的操作也可以有大量不同的写法，所以一条路径对应的往往不是一台而是一组图灵机，记为 。
所以，从 A 到 B 的所有路径构成的集合 对应的就是一大组彼此不同的图灵机，记为 。
接着，如果字符串都可以当作图灵机（及输入参数），所以如果字符串 A 是良性的，那么它自然会生成一个字符串，我们可以记 、 ，并且可以递归地定义 ，只要 是良性的。但需要注意，如果存在两个不同的自然数 i < j 使得 成立，那么我们可以认为这个递归链条到 j-1 结束，并没有新的 被生成。
特别，如果 ，则记为 ，即表示 A 可以“直接生成” B。
很显然，对任意 B，这样的 A 都只是少数。
因此，与之前定义的字符操作是对称的、完全的（即对任意两个字符串总有字符操作可以从一个变成另一个）不同，这里定义的生成关系是单向的、不完全的。
因此可以构造一个集合：
它包含了所有能生成目标字符串 s 的良性字符串。
由于字符串本身也可以作为参数输入到图灵机中，因此就存在这样的情况：
字符串 A 通过字符操作得到了良性字符串 C，C 又生成了目标字符串 B。
或者，良性字符串 A 生成了字符串 C，而后字符串 C 通过字符操作得到良性字符串 D，D 最终又生成了目标字符串 B。
又或者，字符串 A 通过字符操作得到良性字符串 C，C 生成了字符串 D，D又经过字符操作得到了良心字符串E，最终 E 生成了 B。
等等等等。
而每一步种这样的操作，本质上都可以用图灵机来表达，而每个这样的图灵机都对应一个字符串，而由于字操作可以有可数无穷种（对任意初始字符串与目标字符串），由此可见，