为什么图灵机的个数是可数的

Question

由所有图灵机构成的集合是可数的，原因是：每个图灵机有一个编码，它是一个串。只要去掉那些不是图灵机合法编码的串，就得到了所有图灵机的序列。
这是《计算理论导引》中对问题的解释，没看懂，谁能给解释一下啊？这是证明存在非递归可枚举的语言中很重要的一步啊

Answer 1

如果你看過：http://zh.wikipedia.org/wiki/%E5%8F%AF%E6%95%B8%E9%9B%86，就不會問這個問題了

Answer 2

最近也在看计算理论导引，bumfod提到的可数集的概念在书中也可以找到：

由定义，如果存在从S到自然数集合N = {0, 1, 2, 3, ...}存在单射函数f : S → N，则S称为可数集。

可以证明偶数集合、正有理数集合是和N一一对应，康托证明了实数集R是不可数的。我个人认为不严格的说，可以把离散元素的集合看作是不一定可数的，R中元素可以看作连续的，比如0到1之间的元素是无限的，没办法和N一一对应。

---

shit，原来编辑器中插入直线的Ctrl+r快捷键和chrome的刷新冲突了，@segmentfault官方，这个问题需要解决啊 @Integ

书上解释比较清晰，好吧，接下来开始抄书：
首先证明对于任意的字母表a，其上所有的串的集合aa是可数的，因为对于每个自然数n，长度为n的串的个数是有限多个，那相当于N的每个元素对应一个有限集合，这就证明了a是可数的。
注意集合aa是大于所有图灵机识别的串的集合的，所以去掉aa中图灵不可识别的串，aa的子集当然是可数的。

Answer 3

图灵机可以编码成为TM，编码之后的string其实是一个finite alphabet上的finite string。

而一个finite alphabet上的fintie string的集合是 $$\sum^* $$. 该集合是可数的，你可以按照长度为i的string的顺序将所有元素枚举出来(i从0依次递增)。

故TM作为该集合的子集是可数的