4 ms·
I don't think T being infinite is a problem, you only need a cell, which is fin(it)e. But I don't like the argument with the halting problem: If you assume the
by davrosthedalek 9y ago
I don't think T being infinite is a problem, you only need a cell, which is fin(it)e. But I don't like the argument with the halting problem: If you assume the halting problem as a given, it's trivial to show that there are uncomputable functions. Busy Beaver.
The halting problem follows from this automatically: The function gen_f cannot be correct and complete. On the other hand, if you could construct a function which solves the halting problem, you could, with that, construct gen_f to be correct and complete. So you cannot solve the halting problem.
Follow up question: Is the definition of T actually good enough? It's an infinite set, so are we sure that we can order the functions? Or do we need the axiom of choice somewhere?
- 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.