4 ms·
Yeah you can definitely make a language that is not Turing complete but your goal of "up-to" is not possible. For any complexity class C that is not Turing com
by Kranar 4y ago
Yeah you can definitely make a language that is not Turing complete but your goal of "up-to" is not possible.
For any complexity class C that is not Turing complete, there is a complexity class C' that is a strict super-set of C and is also not Turing complete.
- convolvatron 4y agosorry, really genuinely interested in the structure here, reference?
- Kranar 4y agoSure, the insight/intuition comes from diagonalization, or perhaps more directly from Cantor's theorem. For any complexity class O(F(N)), there must exist a complexity class O(2^F(N)) that is strictly a superset of O(F(N)). If F(N) is decidable then so too is 2^F(N). https://en.wikipedia.org/wiki/Cantor%27s_theorem https://en.wikipedia.org/wiki/Cantor%27s_theorem
- deleted 4y ago[deleted]