3 ms·
Ah - but though a subset (bestsellers/halting programs) may not be computable (recursively enumerable) as you say, this does not preclude all novels/finite prog
by somewhereoutth 7y ago
Ah - but though a subset (bestsellers/halting programs) may not be computable (recursively enumerable) as you say, this does not preclude all novels/finite programs from being enumerated. Taking the alphabet as just the uppercase letters, I can list all novels as A, B, C.. AA, AB, AC... ... and hence eventually reach any novel you may supply. But this tells me nothing of whether they are bestsellers (or halting programs)!
- yters 7y agoYes, of course, enumerating all symbol strings is computable. What I mean is the novels as a whole correctly label the halting machines, an unreasonable assumption to be sure. That would prevent the novels from being computable. If real novels somehow exhibit an equivalent characteristic, then that would prevent real novels from being computable. Perhaps the logical consistency of good novels would be such a characteristic. We probably cannot depend on novels being perfectly consistent, but still consistent to a greater degree than we can achieve by randomly generating bitstrings. The objection would be that a finite set of axioms can generate consistent novels, so there is also some other criterion that is necessary to make the novels uncomputable. I would say this second criterion is novelty, defined as an increase in Kolmogorov complexity. Using a single set of axioms to enumerate an infinite set of novels will hit a novelty plateau, as per the proof of uncomputability of Kolmogorov complexity. So, based on these two criteria, one can derive a hand wavy argument that novels in general are uncomputable.