3 ms·

That definition is fine (given that we know that no Turing machine computes the halting problem). It's equivalent to f(n) = 0.

• calf 2y ago
  Hm, but the definition is not fine if we didn't already know the status of the halting problem?
  • foldr 2y ago
    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.
    • mrkeen 2y ago
      > It's just that we wouldn't know what value the function had. I think there should be a word for that...
      • foldr 2y ago
        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.
    • karatinversion 2y ago
      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.