Hacker News Reader

Comment by foldr | Hacker News Reader

In that scenario I think the definition itself is still fine, technically. It's just that we wouldn't know what value the function had. It would be a bit like defining f(n) = n + the number of hairs Julius Caesar had when he died. There's nothing inherently wrong with the definition. You just can't do much with it.

View on HN

To tie this back to TFA, even before we knew that the Halting problem was uncomputable, we could have defined

  f(n) = { 1 if there is a Turing machine with at most n states that solves the Halting problem;
           0 otherwise }

and we can easily show that f(n) is computable without proving that the Halting problem is undecideable. Viz., f is either constant 0; or equal to a function of the form

  g_k(n) = { 1 if n >= k;
             0 if n < k },

and both the constant 0 function, and all the g_k functions, are computable; thus f is computable.

> It's just that we wouldn't know what value the function had.

I think there should be a word for that...

I don't think so. It's a pretty uninteresting property of a function whether or not a particular person happens to know its value for a given input. It does not entail that the function is not computable, if that's what you're suggesting.

Reply on news.ycombinator.com