剛剛看到書上寫{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 我只能理解到這邊了考試的話這題已經有點偏了 所以可以跳過了媽的交大上次還哪次考那個複雜度好一點的矩陣乘法跳過都跳過

說的也是哈哈，感謝你陪我耗時間在這個東西上@@