3 ms·
> 2)This indicates that there is a way to write a program in javascript which gives me f_i for i. Let's call that function gen_f(i) The whole point, actually,
by dvt 9y ago
> 2)This indicates that there is a way to write a program in javascript which gives me f_i for i. Let's call that function gen_f(i)
The whole point, actually, is that there isn't a way to write a program in JS which gives you f_i for i (pragmatically, you have no access to T). You might think of some clever way to try and augment your language (but that will be tricky; T is infinite but programs are finite, so you'll run into the Halting Problem). The Second Theorem of Incompleteness shows why you'll never be able to do that, but that's another post for another day.
- davrosthedalek 9y agoI 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.