程序与有穷状态机

问题 1、为什么要写程序？或者程序是用来干嘛的？
答： 程序是用来解决计算任务的。

问题 2、程序是用来解决什么样的计算任务的？
答： 程序是用来解决可解的计算任务的。

问题 3、什么样的计算任务是可解的？
答： 对计算机来说，可以在有限步骤内完成的就是可解的计算任务。

问题 4 可解的计算任务与程序又有何深层的关系？
答： 在图灵对”计算“的抽象模型中，有一个控制逻辑部件来控制读写头往前移，还是往后移动，我们可以将它想象成是状态的迁移，当然这个模型是理论上的，因此是可以有”无穷“的状态迁移，而我们所关心的是”有穷“的状态迁移，这就是我所赖以生存的”程序“的本质了。
    简言之，可解的计算任务 <=> 有穷状态机 <=> 程序

问题 5 程序优化的本质是什么？
由于程序在执行过程中的下一状态是需要依赖于上一状态的，所以，如果在上一状态中保存的信息足够多，那么程序就可以相应地迁移到一些”提高程序性能“的状态，反之，如果在上一状态中没有什么信息，那么程序就只能盲目地去尝试迁移到所有的状态直到遇到合适的状态为止。由这两方面比较，很显然，要想优化我们的程序，我们必须多存储某些信息，以使我们的程序在运行时刻不必去盲目尝试，这样，无疑可以减少时间开销！举个例子，在字符串搜索中，有一个很著名的KMP算法，KMP只所以效率高的原因，就在于每当发生不匹配的时候，目标字符串的指针只是简单地往后移，而模式字符串的指针则根据事先计算好的next数组中的值指向合适的位置，如果说没有next数组，那么目标字符串的指针就需要回溯到相应的位置。顺便阐述一下回溯的原因，由于在状态迁移过程中，上一状态没有可用的信息，因此需要回溯到上一状态的上一状态的上一状态......，这也就是”递归“程序的本质了！