理论计算机初步：算法和计算模型
下面是wikipedia上算法的定义：
算法是指完成一个任务所需要的具体步骤和方法。也就是说给定初始状态或输入数据，经过计算机程序的有限次运算，能够得出所要求或期望的终止状态或输出数据。
算法常常含有重复的步骤和一些比较或逻辑判断。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
一个简单而且耳熟能详的算法的例子是求最大公约数的辗转相除法：给出两个数，要求出他们俩的最大公约数。在小学的时候，我们就知道这样做就行了：将大数除以小数，用所得余数替换大数，继续用这两个数中大者除以小者，用所得余数替换较大者，继续下去，直到所得余数为0，此时除数即为所求的最大公约数。下面是一个实例：(15, 21) = (15, 6) = (3, 6) = (3, 0) = 3。又如，要判断某个数是否为质数，只需枚举所有比它小的数，检验是否其约数即可。
算法是理论计算机的灵魂。几乎所有问题都围绕它而来。为了讨论算法的性质，在理论计算机中，算法已不限于只是上面定义中的计算机程序。或者说，这里计算机的含义被大大扩广了。
我们平时所说和所使用的计算机，基于图灵提出的确定型图灵机模型。它是最好理解的：给出固定的程式，模型按照程式和输入完全确定性地运行。
但为了理解算法和这种确定型图灵机的能力，人们又发展了许多其它各式各样的图灵机模型。其中最为有名的是非确定型图灵机。这种计算模型，它在进行计算的时候，会自动选择最优路径进行计算。通俗地说，它有预测能力。比如说，为了说明某个数是合数，非确定型图灵机会猜测一个数，恰好是其因子，从而证明了它不是质数。
确定型和非确定型图灵机的计算性能所引起的P vs NP问题，一直是理论计算机科学的核心问题，这点下面专文论述。
另一个引起广泛关注的计算机模型是量子计算机模型。与上面的非确定型图灵机只存在于人们的想象中不同，量子计算机在物理上是可以实现的。关于量子计算理论，以后也有单独的介绍性文章。
虽然上面的各种计算模型的效率可能不同，比如非确定性图灵机判定一个数是合数便要快得多，但是它们的计算能力是完全一样的。也就是在某个计算模型上面运行的算法，可以被其余模型模拟实现。
这些计算模型的计算能力是一样的，那是不是世界上所有问题都有算法呢？看上去这似乎是一个哲学问题，但答案早就有了，有些问题是不可能能通过算法求解的，连下面这个看上去很简单的问题都不行：给出一些分数（指12/23，18/9这样的），问是否可以从中选出若干个分数数（可以重复选取），使得按一定顺序排起来，其分母连起来和分子连起来恰好一样？
先说一下，这个系列文章我要全文转载
Very good!
support！
建议：提到相关问题可以列一些参考文献、教材啥的，方便读者查阅，说不定回头总结总结直接初本书，就叫《理论计算机通俗入门》，哈哈
btw: 我也想全文转载没问题吧，呵呵。看你这边这么红火，等我回去跟你合写blog得了，好不。：）
好啊，我还正愁有时候没东西写，blog长草呢。
让我这样不懂的人也领略到计算机理论的美感,顺便问下 ,模型论,递归论,半群理论是属于理论计算机科学范畴么?
递归论，好像在wiki上看到，是computability theory的mathematics的对应……
不过，我也没怎么去深入了解，不敢说满
No. That's math tools.
辗转相除法一段的描述与所举实例似有冲突：将大数除以小数，用所得余数替换大数，继续用这两个数中大者除以小者，用所得余数替换较大者，继续下去，直到所得余数为0，此时除数即为所求的最大公约数。下面是一个实例：(15, 21) = (15, 6) = (3, 6) = (3, 0) = 3
(3, 0) 似不应出现
另外，会自动选择最优路径有点奇怪吧……
感觉非确定图灵机的选择应该是“盲目”的吧，如果从计算的过程来看。
嗯，从定义来看是“盲目”的，非确定就是这个意思，但这样难以让人理解。这篇文章的主要目的是给没机会接触到图灵机的直接定义的读者一些感觉，从验证的角度来看，也可以认为它的选择很聪明，一下子就选中了正确的路径。希望这样写能容易理解一些。
量子计算机模型应该是热点吧～
现在向往的地方哈～～～～
最后一段说的没有算法，是指没有时间复杂度是多项式的算法吧？
不是，最后一段讲问题的decidability概念，那个问题不但没有多项式算法，而且连“算法”都不可能有
哦，明白了，那题说是“可以重复选取”，所以还是真啥算法都没有
那是不是世界上所有问题都有算法呢？看上去这似乎是一个哲学问题，但答案早就有了，有些问题是不可能能通过算法求解的，连下面这个看上去很简单的问题都不行。
观点完全赞成，后面举的一个例子却让人弄不明白，没有任何条件？