刚刚看到书上写{0, 1}*字串是不可数
直觉的想法是所有01字串的个数是2的指数, 所以必为不可数
但是下面这题(交大104)又说0,1字串必定可以对应到一个正整数, 所以是可数
https://imgur.com/geofuUs
https://imgur.com/RUGo06M
如果0,1字串可以对应到一个正整数的话, 是可以onto对完所有正整数没错,
但例如01和001, 都会对到1, 这样不是就不符合one-to-one?
所以到底0,1字串是可数还是不可数?

你举的两个例子都是可数喔，你可以把字串长度当作基准，从长度1开始列，然后长度2、长度3，依此类推，然后依然所有字串都能获得一个序号，所以是可数的Ex. 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ..

对应到2和4

btw, 可不可数是看能不能把元素有条不紊的排成一列绝对不是看长度是不是指数次方

{0,1}* 是可数集吧我印象中 @@这题很难我记得我之前看到直接跳过第二题 两个都是program 都是01字串的集合 皆可数集抱歉我更正 我刚刚看了一些东西 他跟证明[0,1]不可数的方法是一样的都是用那个对角线的方式证明的 所以{0,1}* 不可数呢我可以确定program是可数的我刚刚查过了不过他的解释 看起来很ok 可是我感觉我可以用她的解释方式 去说{0,1}* 是可数的让我困惑到现在XDhttps://goo.gl/HzL7Vn 你可以看看他基本上是用可数集的联集依然是可数的方式然后长度为n的program是有限集(所以可数所以把n=0到无限大都union起来 说这也是可数的这我不懂 因为program是无限集 所以他union到无限长的program才对(我的认知拉可是union到无限长度的话就跟{0,1}*是一样的东西所以应该不是这样(一片混乱应该说any长度的set联集再一起跟{0,1}*是不一样的东西看看有没有人念语言的XD 我只能理解到这边了考试的话这题已经有点偏了 所以可以跳过了妈的交大上次还哪次考那个复杂度好一点的矩阵乘法跳过都跳过

说的也是哈哈，感谢你陪我耗时间在这个东西上@@