4 ms·
f_i was defined as the ith program in lexicographical order that is guaranteed to terminate and to only return 0 or 1 (from the article: "we can just throw out
by wdrw 9y ago
f_i was defined as the ith program in lexicographical order that is guaranteed to terminate and to only return 0 or 1 (from the article: "we can just throw out programs that loop infinitely or don’t return a 1 or a 0")
This means that to write your "gen_f(i)" function, you'd have to solve the halting problem, which is impossible. So there is no mechanical (and hence no Javascript-based) way to create the gen_f(i) function.
Note that f_i is still a well-defined mathematical object, and so table T is a well-defined mathematical object (and then so is fbar). But they are not computable objects.
- davrosthedalek 9y agoWell, f_i is certainly computable, because it's in A. I guess you mean f_bar? T is not computable, but T is also not a function out of F.