图灵完备（Turing completeness）

在可计算性理论中，如果一个数据操作规则系统（如计算机的指令集、编程语言或细胞自动机）可以用来模拟任何图灵机器（由英国数学家和计算机科学家阿兰·图灵（Alan Turing）设计），则称其为图灵完备（Turing-complete）或计算通用的。

图灵等价（Turing equivalence）

若P可以模拟Q，Q可以模拟P，那个么这两个数据操作规则系统P和Q就是图灵等价的。

图灵机（Turing machine）

图灵机（Turing Machine）是图灵在1936年发表的 《论可计算数及其在判定性问题上的应用》（《On Computable Numbers, with an Application to the Entscheidungsproblem》）中提出的数学模型。

图灵机的结构包括以下几个部分：

• 一条无限长的纸带（tape），纸带被分成一个个相邻的格子（square），每个格子都可以写上至多一个字符（symbol）。
• 一个字符表（alphabet），即字符的集合，它包含纸带上可能出现的所有字符。其中包含一个特殊的空白字符（blank），意思是此格子没有任何字符。
• 一个读写头（head），可理解为指向其中一个格子的指针。它可以读取/擦除/写入当前格子的内容，此外也可以每次向左/右移动一个格子。
• 一个状态寄存器（state register），它追踪着每一步运算过程中，整个机器所处的状态（运行/终止）。当这个状态从运行变为终止，则运算结束，机器停机并交回控制权。如果你了解有限状态机，它便对应着有限状态机里的状态。
• 一个有限的指令集（instructions table），它记录着读写头在特定情况下应该执行的行为。可以想象读写头随身有一本操作指南，里面记录着很多条类似于“当你身处编号53的格子并看到其内容为0时，擦除，改写为1，并向右移一格。此外，令下一状态为运行。”这样的命令。其实某种意义上，这个指令集就对应着程序员所写下的程序了。

在计算开始前，纸带可以是完全空白，也可以在某些格子里预先就有写上部分字符作为输入。运算开始时，读写头从某一位置开始，严格按照此刻的配置（configuration），即：

• 当前所处位置
• 当前格子内容

来一步步的对照着指令集去进行操作，直到状态变为停止，运算结束。而后纸带上留下的信息，即字符的序列（比如类似“…011001…”）便作为输出，由人来解码为自然语言。

停机问题（Halting Problem）

在可计算性理论中，停机问题是根据对任意计算机程序和输入的描述，确定程序是否将完成运行，还是将永远继续运行的问题。阿兰·图灵在1936年证明，解决所有可能的程序输入对的停机问题的通用算法不存在。

自动机（Automation）

自动机是有限状态自动机（Finite State Machine，FSM）的数学模型。有限状态自动机是给定符号输入，依据（可表达为一个表格的）转移函数“跳转”过一系列状态的一种机器。

1. 有限状态自动机（Finite Automata，FA）
   1. 确定有限自动机（Deterministic Finite Automata，DFA）
      自动机的每个状态都有对字母表中所有符号的转移。
   2. 非确定有限自动机（Non-deterministic Finite Automata，NFA）
      自动机的状态对字母表中的每个符号可以有也可以没有转移，对一个符号甚至可以有多个转移。
      上述自动机接受的语言家族被称为正规表达式(Regular Expression)
2. 下推自动机（Pushdown Automation，PDA）
   下推自动机额外的装备了栈形式的内存。下推自动机是一种实现上下文无关语法的方式。
3. 线性有界自动机（Linear Bounded Automation，LBA）
   线性有界自动机是有限制的 图灵机；不使用无限磁带，它的磁带有同输入字元串成正比的空间。线性有界自动机接受上下文有关语言。
4. 图灵机（Turing Machine）
   图灵机是最强力的自动机。图灵机拥有磁带形式的无限内存，和可以读取和变更磁带的磁头，它可在磁带上向任何方向移动。图灵机等价于演算法，可以用来判定递归语言并识别递归可枚举语言。

Brainfuck 语言

在1993年，Urban Müller 发明了 Brainfuck 语言。这门语言可以说是编程语言界的 helloworld 了——它一共只含有 8 个有效字符，每个有效字符就是一条指令。语言虽然极致轻量，它却是一门图灵完备的编程语言。

语言里的 8 个有效字符分别是：

• >
  指针向右移动一格
• <
  指针向左移动一格
• +
  使指针当前格数值加一
• -
  使指针当前格数值减一
• .
  把当前格数值按 ASCII 表输出到终端
• ,
  从终端接受 1 byte 的数据，存储其 ASCII 数值到当前格
• [
  当指针当前值为 0 时，程序跳转至与之对应的 ] 之后；否则程序正常执行
• ]
  程序跳转回与之对应的 [ 处

brainfuck-visualizer 提供了 Brainfuck 的可视化解析过程。

Brainfuck 的 8 个指令可以等价的转换为 C/C++ 语言语法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

string translate(char c) {
    switch(c) {
        case '>':
            return "p++";
        case '<':
            return "p--";
        case '+':
            return "*p = *p + 1";
        case '-':
            return "*p = *p - 1";
        case '.':
            return "cout << char(*p)";
        case ',':
            return "*p = getchar()";
        case '[':
            return "while(*p) {";
        case ']':
            return "}";
        default:
            return "";
    }
}
void run() {
    char arr[1000] = { 0 };
    char* p = arr + 500;
}
int main() {
    run();
    freopen("D:/out.text", "w", stdout);
    char c;
    while(cin >> c) {
        cout << translate(c);
        if (c != '[')
            cout << ";\n";
    }
    return 0;
}

阶乘

在数学上, 自然数n的阶乘写作n!。一个正整数 n 的阶乘, 就是所有小于等于 n 的正整数的乘积，0的阶乘为1。比如:

5！ = 5 4 3 2 1 = 120

问题： 求自然数n的阶乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/**
 * @param {number} number
 * @return {number}
 */
export default function factorial(number) {
  let result = 1;
  // 0 或 1 返回 1
  if (number === 0 || number === 1) {
    return 1;
  }
  // 大于等于2时循环相乘
  for (let i = 2; i <= number; i++) {
    result *= i;
  }

  return result;
}

使用尾递归的方法

1
2
3
4
5
6
7
8

/**
 * @param {number} n
 * @param {number} total
 * @return {number}
 */
export default function factorial(n, total = 1) {
  return n === 1 ? total : factorial(n - 1, n * total);
}

阅读更多

函数式编程

函数式编程（Functional programming）或称函数程序设计，又称泛函编程，是一种编程范型，它将电脑运算视为数学上的函数计算，并且避免使用程序状态以及易变对象。函数编程语言最重要的基础是λ演算（lambda calculus）。而且λ演算的函数可以接受函数当作输入（引数）和输出（传出值）。

函数式编程优点：

1. 没有并发编程的问题，是多线程安全的
2. 函数式编程的表达方式更加符合人类日常生活中的语法，代码可读性更强，实现同样的功能函数式编程所需要的代码比面向对象编程要少很多，代码更加简洁明晰

函数式编程缺点：

1. 所有的变量在程序运行期间都是一直存在的，资源利用率低
2. 大型项目中工程化不足，使得代码易读性降低

阅读更多

时间空间复杂度

排序是算法中最经典的问题，以下表格对插入排序、冒泡排序、选择排序、希尔排序、快速排序、归并排序这几种排序进行了比较。

阅读更多

该文章用来记录一些常见的前端简单面试题，这些题目部分是因为比较细碎，部分是比较偏门（对某个不常用功能的深入知识），部分是因为还没来得及，所以没有单独列出文章来讲述。

阅读更多