3 ms·

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 ha

by calf 2y ago

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.

foldr 2y ago
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.
pdonis 2y ago
> 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.
- layer8 2y ago
  > 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.
  - pdonis 2y ago
    > 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.)

by calf 2y ago

foldr 2y ago

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.

pdonis 2y ago

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

layer8 2y ago
> 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.
- pdonis 2y ago
  > 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.)