证明 JS 和 TS 类型编程是图灵完备的

254次阅读  |  发布于3年以前

如何证明

图灵完备和实现偏递归函数是等价的[1]，关于偏递归函数的定义可以参照以下系列视频，我觉得这几个视频介绍偏递归函数解释得比较简单明了。

  1. Partial Recursive Functions 1: What's a function?[2]
  2. Partial Recursive Functions 2: The basic functions[3]
  3. Partial Recursive Functions 3: Composition[4]
  4. Partial Recursive Functions 4: Primitive Recursion[5]
  5. Partial Recursive Functions 5: Minimisation[6]

由于视频存放于油管，感兴趣的同学可以自行搜索哈。

因为图灵完备和实现偏递归函数是等价的[7] ，因为我们可以通过用一门语言实现偏递归函数来证明这门语言是图灵完备完备的。这种领域有一个有趣的定理是，任意偏递归函数都可以由原始递归函数经过一次极小化得来，所以写程序的时候如果发现两层以上的无限循环要格外小心，很可能逻辑是错的。

偏递归函数的定义

在偏递归函数这个领域有三个基本函数和三个基本操作，三个基本函数为零函数、后继函数和投影函数，三个基本操作为组合、原始递归和最小化。所有的可计算问题可以由这三个基本函数和基本操作组合而来，由原始递归操作得到的函数叫原始递归函数，将原始递归函数进行最小化后得到的函数称为偏递归函数。

函数

这里对函数定义是一个或者多个非负整数到单个非负整数的映射，非负整数集我们用 来表示，如果这个这个函数接受 个参数，则记作 。当函数对所有输入都有输出的时候，则称函数是完全的（total），用符号 来表示，否则称其为非完全（partial），用符号 来表示。

基本函数

零函数/zero

基本定义

个参数的零函数我们简单记作

形象化记忆

可以理解为在某个内存地址，将地址内容置空为 0。

后继函数/Successor

基本定义
形象化记忆

可以理解为在某个内存地址，将地址内容进行 +1 操作，能够实现一个加法器。

投影/Projection

基本定义

具有 个参数的投影函数返回第 个参数，我们简单地记作 。

形象化记忆

可以理解为对内存的某个地址进行取值。

基本操作

组合/Composition

基本定义

给定 个函数 和函数 ，定义 ，则称 为 和 的组合操作，记作 。

形象化记忆

可以理解为支持函数调用/复合函数。

原始递归

基本定义

给定函数 和函数 ，如果满足以下条件，定义函数 为 和 的原始递归操作，记作 ：

base case:

recursive case:

形象化记忆

可以理解为支持递归。

最小化

给定函数 ，最小化 定义为找到第一个 使得 。

原始递归函数由最小化得到的函数叫偏递归函数。

形象化记忆

可以理解为可以实现 while 循环。

偏递归函数的作用

计算机上面任何可计算的问题都可以用上面的基本函数和基本操作来组合实现，下面举几个例子：

加法

首先先说结论，加法可以用原始递归操作实现。首先我们的加法是 是一个 的函数，也就是我们需要找函数 是 的函数， 是 的函数，如果用原始递归的话：

Base Case:

，也就是 是 。

Recursive Case:

，也就是 。

总结上面得到的 和 ，也就是 ，可以看到，加法可以通过三种基本函数和三种基本操作组成。

前继函数

也可以用原始递归实现

Base Case:

，也就是 是 。

Recursive Case:

，也就是 。

总结上面得到的 和 ，也就是 。

减法

也可以用原始递归实现

Base Case:

，也就是 是 。

Recursive Case:

，也就是 。

总结上面得到的 和 ，也就是 。

是否为 0/isZero

首先先说结论，isZero 可以用原始递归实现，首先给出 的定义：

也就是 ，。所以我们可以得出

Base Case:

，也就是 是 。

Recursive Case:

，也就是 。

总结上面得到的 和 ，也就是 ，可以看到，加法可以通过三种基本函数和三种基本操作组成。

<=/小于等于/isLessEqualThan

先给出定义：

这里比较清晰了，我们只要复用一下 就可以

乘法

Base Case:

，也就是 是 。

Recursive Case:

，也就是 。

除法

首先先说结论，除法可以用最小化实现。对于两个非负整数 ，且 ，则定义：

这里先写结论，后续证明看后面的 JS 代码实现处可以比较直观地看到。

，

JS 是图灵完备的

我们先来简单的，证明 JS 是图灵完备的。

// 基本函数
//// 零函数
function zero(...args) {
  return 0;
}
//// 后继函数
function succ(n) {
  return n + 1;
}
//// 投影函数
function getProjFunc(n) {
  return (...args) => args[n];
}
const projN1 = getProjFunc(1);
//// ...
// 基本操作
//// 组合
function compose(h, ...funcs) {
  return function (...args) {
    return h(...funcs.map((f) => f(...args)));
  };
}
//// 原始递归
function primitiveRecursion(g, h) {
  return function __primitiveRecursion(n, ...args) {
    if (0 === n) {
      let resp = g(...args);
      // console.log("0 resp", resp, n, args);
      return resp;
    }
    let last = __primitiveRecursion(n - 1, ...args);
    let resp = h(n - 1, last, ...args);
    // console.log("n resp", resp, n, args);
    return resp;
  };
}
//// 最小化
function getMinimizationFunction(f) {
  return function (...args) {
    let i = 0;
    while (i < Number.POSITIVE_INFINITY) {
      if (f(i, ...args) === 0) {
        return i;
      }
      i++;
    }
    return undefined;
  };
}
// 加法
/*
      这里注意投影函数和前面公式推导不一样了，是因为我们过程中一些函数的参数位置与推导处不一样，但是本质是一样的
  */
const add = primitiveRecursion(getProjFunc(0), compose(succ, getProjFunc(1)));
const pred = primitiveRecursion(zero, getProjFunc(0));
const sub = primitiveRecursion(getProjFunc(0), compose(pred, getProjFunc(1)));
const isZero = primitiveRecursion(
  zero,
  compose(succ, compose(zero, getProjFunc(0)))
);
const isLessThan = compose(isZero, sub);
const mul = primitiveRecursion(
  zero,
  compose(add, getProjFunc(1), getProjFunc(2))
);
// div 的推导过程
// const f = (i, a, b) => {
//   if ((i + 1) * b <= a) {
//     return 1;
//   }
//   return 0;
// }
// 第二步
// const f = compose(isLessThan, (i, a, b) => {
//   return (i + 1) * b;
// }, getProjFunc(1));
// const div = getMinimizationFunction(f);
const div = getMinimizationFunction(
  compose(
    isLessThan,
    compose(mul, compose(succ, getProjFunc(0)), getProjFunc(2)),
    getProjFunc(1)
  )
);
console.log(add(3, 4)); // 7
console.log(pred(1), pred(2), pred(0)); // 0, 1, 0
// 这里其实是 3 - 1, 3 - 2, 3 - 3, 3 - 4
console.log(sub(1, 3), sub(2, 3), sub(3, 3), sub(4, 3)); // 2, 1, 0, 0
console.log(isZero(0), isZero(3)); // 0, 1
// 4 <= 3, 3 <= 4, 2 <= 4
console.log(isLessThan(3, 4), isLessThan(4, 3), isLessThan(4, 2)); // 1, 0, 0
// 3 * 4
console.log(mul(3, 4)); // 12
// 6 / 4
console.log(div(6, 4)); // 1

TS 类型编程是图灵完备的

这个估计稍稍有点复杂，我试一下 。

// 基本函数
//// 零函数
/*
    type Zero<A, B, C, D, E, F, G, ...> = 0;
*/
type Zero<A, B, C, D, E, F, G> = 0;
//// 后继函数
/*
    这个有点难，要通过一些 Trick
*/
type IntSeq<N, S extends any[] = []> = S["length"] extends N
  ? S
  : IntSeq<N, [...S, S["length"]]>;
type Succ<N> = [...IntSeq<N>, 1]["length"];
//// 投影函数
/*
    我们可以直接写特定的投影函数
*/
type Proj31<A, B, C> = A;
//// ...
// 基本操作
//// 组合
/*
    这个比较简单，我们可以直接写出组合
*/
type H<A, B, C> = 0;
type G<A, B, C> = 0;
type ComposedType<A, B, C> = H<G<A, B, C>, G<A, B, C>, G<A, B, C>>;
//// 原始递归
/*
    递归的话我们先实现一下减一函数会比较方便
*/
type Pop<T extends any[]> = T extends [...(infer I), infer _] ? I : never;
type Pred<N> = Pop<[...IntSeq<N>]>["length"];
type PG<A, B, C> = 0;
type HG<N, Y, A, B, C> = 0;
type PremitiveFunc<N, A, B, C> = N extends 0
  ? PG<A, B, C>
  : HG<N, PremitiveFunc<Pred<N>, A, B, C>, A, B, C>;
//// 最小化
/*
    有递归比较好办，我们直接用递归来实现
*/
type MF<A, B, C, I> = 0;
type Miminize<A, B, C, I> = MF<A, B, C, I> extends 0 ? I : Miminize<A, B, C, Succ<I>>;
type Miminized<A, B, C> = Miminize<A, B, C, 0>;
// 加法
/*
    这里注意投影函数和前面公式推导不一样了，是因为我们过程中一些函数的参数位置与推导处不一样，但是本质是一样的
*/
type Proj11<A> = A;
type Proj32<A, B, C> = B;
type SuccComposedProj<A, B, C> = Succ<Proj32<A, B, C>>;
type Add<X, Y> = Y extends 0 ? Proj11<X> : SuccComposedProj<X, Add<X, Pred<Y>>, Y>;
type R = Add<3, 4>; // 7
// 剩下的写起来比较繁琐，基本思路请按照 JS 的证明

参考资料

[1]等价的: https://ncatlab.org/nlab/show/partial+recursive+function#:~:text=A%20partial%20recursive%20function%20(often,may%20run%20forever,%20but%20otherwise)

[2]Partial Recursive Functions 1: What's a function?: https://www.youtube.com/watch?v=yaDQrOUK-KY

[3]Partial Recursive Functions 2: The basic functions: https://www.youtube.com/watch?v=_cswfIQg0Ss

[4]Partial Recursive Functions 3: Composition: https://www.youtube.com/watch?v=twHp7IrPJEs

[5]Partial Recursive Functions 4: Primitive Recursion: https://www.youtube.com/watch?v=cjq0X-vfvYY

[6]Partial Recursive Functions 5: Minimisation: https://www.youtube.com/watch?v=bFkU-qV2Ioo

[7]等价的: https://ncatlab.org/nlab/show/partial+recursive+function#:~:text=A%20partial%20recursive%20function%20(often,may%20run%20forever,%20but%20otherwise)

Copyright© 2013-2020

All Rights Reserved 京ICP备2023019179号-8