4 ms·
Wait, the number of programs is countable? Are we saying that programs must be of finite length? (because if not a diagonal approach would prove them to be unco
by gcanyon 2y ago
Wait, the number of programs is countable? Are we saying that programs must be of finite length? (because if not a diagonal approach would prove them to be uncountable)
- titanomachy 2y ago“Countable” as used in mathematics does not necessarily imply finite. The integers are “countably infinite”, and so is anything you can put in a 1:1 correspondence with integers.
- gcanyon 2y agoBut as I said, if programs are of infinite length, then a diagonalization argument proves the computable numbers not to be countable I think.
- titanomachy 2y agoAh yes, of course you're right. I think it does make sense to assume the programs are finite, I don't think numbers described by an infinite program should be considered computable.
- Gabriel54 2y agoYup! Programs are assumed to have finite length, in the sense that the program must have a finite description. Of course, it may use recursion or include a loop that runs forever, for example.