Hacker News Reader

Comment by calf | Hacker News Reader

What about this one:

  f(n) = { 0, if no Turing machine computes the halting problem
           H(n), if there exists a Turing machine, H, that computes the halting problem
          }

A function is just any proper mathematical function, a "black box", such that for each input x is given exactly one unique y. A computable function (per Sipser) has some Turing machine M such that M(x) = y everywhere.

It would seem the definitions are also fine for the above contrived example. edit: I'm not sure if n needs to encode a tuple (P, i) for some program P on input i and so forth.

View on HN

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

Hm, but the definition is not fine if we didn't already know the status of the halting problem?

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.

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

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.

> What about this one

This is not the kind of thing Aaronson is actually asking about. He's not asking about a function f that outputs 1 if God exists or 0 if God doesn't exist. He's asking about a label f that refers to the function f1 (that just outputs 1) if God exists or the function f0 (that just outputs 0) if God doesn't exist. To me the question is not about computability at all, it's about labels.

> He's not asking about a function f that outputs 1 if God exists or 0 if God doesn't exist.

Because that’s not a function in the mathematical sense. The output of a mathematical function can only depend on its inputs, and the function in question is not given any inputs, hence it’s necessarily a constant function, and constant functions are trivially computable.

> the function in question is not given any inputs

As the problem was posed, the function does take an input; it's defined as a function from {0, 1} to {0, 1}. However, as I pointed out in another comment upthread, the function makes no use of its input so it could just as well be defined with no inputs. (Indeed, even if you read the question as asking about a function f that outputs 1 if God exists or 0 if God doesn't exist, it doesn't seem like whether or not God exists is supposed to be an input.)

Reply on news.ycombinator.com