Hacker News Reader

Comment by davrosthedalek | Hacker News Reader

Hmm, not sure I fully follow. I'll number my steps to help discussion:

1) The argument assumes that I can generate all programs and name them, right?

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)

3) Isn't the function fbar(i)=1-eval(gen_f(i))(i) a valid program? It obviously fulfills the premise.

4) The only way out here that I see is that gen_f is not halting, or that eval(gen_f(i)) is not halting.

5) The first case is possible, but then we can not generate the table, and without the table, it's not clear that fbar exists.

6) The second case means that we generated a non-halting function, i.e. f_i is not a computable function, and not part of F.

So, if we write a function gen_f, it's either not sound, as it gives functions which are actually not in F, or not complete, because it can then never give fbar. That's the trick, right?

View on HN

> 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.

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?

> 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.

The list of words from that trivial alphabet is certainly generatable via a function though.

True, 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.

The point is that you cannot find an alphabet to generate all terminating programs. The infinite nature of T is really not the problem.

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.

Well, 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.

Reply on news.ycombinator.com