3 ms·
> It's an infinite set, so are we sure that we can order the functions? It's ordered lexicographically. Consider a trivial alphabet {a, b}. So, we have: a
by dvt 9y ago
> It's an infinite set, so are we sure that we can order the functions?
It's ordered lexicographically. Consider a trivial alphabet {a, b}. So, we have:
a
b
aa
ab
ba
bb
aaa
aab
...
And so on, ad infinitum. No AoC needed.
- davrosthedalek 9y agoThe list of words from that trivial alphabet is certainly generatable via a function though.
- dvt 9y agoTrue, but the generation will never terminate (as the list is countably infinite). Your next argument might be "oh I just need to generate T until I hit f_i" -- which is true, but then I can introduce another function f_i_i which will bungle up your system again :) But this gets into the Second Incompleteness Theorem.
- davrosthedalek 9y agoThe point is that you cannot find an alphabet to generate all terminating programs. The infinite nature of T is really not the problem.