3 ms·
I think the intent is clear. We could just enumerate all strings in size and lexicographical order. Then the task is only to filter, which strings are programs
by maweki 2mo ago
I think the intent is clear. We could just enumerate all strings in size and lexicographical order. Then the task is only to filter, which strings are programs we desire.
It's the same sentiment as "the typing itself is not the issue, it's the order of the button presses that's difficult."
Of course, by Rice's theorem, all interesting questions are undecidable anyway...
- deleted 2mo ago[deleted]
- adrianN 2mo agoIf we restrict ourselves to programs that can be stored inside the physical universe, suddenly everything switches from undecidable to O(1) :)