5 ms·

I don’t get the god thing. Why is f computable, just because we know the possible outputs? By that logic the halting problem is computable because h(f) is eithe

• alexey-salmin 2y ago
  Any given program P either terminates or not. So yes, for any fixed P the function that h_p() that returns 0 or 1 is computable. Same is true for a function h_N(P) that accepts only a finite set of possible inputs -- it's a switch case. However a generic function h(P) that can accept any program P is not computable and the switch-case approach won't work. Long story short, the question of computability only considers whether an algorithm exists or not, not whether humans know it or not -- that is irrelevant to the question. Consider the following example from wikipedia [1]: > The following examples illustrate that a function may be computable though it is not known which algorithm computes it. > The function f such that f(n) = 1 if there is a sequence of at least n consecutive fives in the decimal expansion of π, and f(n) = 0 otherwise, is computable. (The function f is either the constant 1 function, which is computable, or else there is a k such that f(n) = 1 if n < k and f(n) = 0 if n ≥ k. Every such function is computable. It is not known whether there are arbitrarily long runs of fives in the decimal expansion of π, so we don't know which of those functions is f. Nevertheless, we know that the function f must be computable.) > Each finite segment of an uncomputable sequence of natural numbers (such as the Busy Beaver function Σ) is computable. E.g., for each natural number n, there exists an algorithm that computes the finite sequence Σ(0), Σ(1), Σ(2), ..., Σ(n) — in contrast to the fact that there is no algorithm that computes the entire Σ-sequence, i.e. Σ(n) for all n. Thus, "Print 0, 1, 4, 6, 13" is a trivial algorithm to compute Σ(0), Σ(1), Σ(2), Σ(3), Σ(4); similarly, for any given value of n, such a trivial algorithm exists (even though it may never be known or produced by anyone) to compute Σ(0), Σ(1), Σ(2), ..., Σ(n). [1] https://en.wikipedia.org/wiki/Computable_function https://en.wikipedia.org/wiki/Computable_function
• empath75 2y ago
  The halting problem for any given program is either true or false, so a program that prints true or a program that prints false is a valid function that produces an answer for that function. You don't know _which_ one is the correct function, but it exists. The thing that's not computable is a function that produces an answer given any arbitrary program as input. It's the difference between: does_program_x_halt(): return true and does_program_halt(x): if x halts: return true else: return false The important distinction is that the first function is a constant that takes no input, and the second function is not a constant and takes a program as input. The first is computable(although we may not know right now if "return false" or "return true" is the correct function, one of the two is), the second is not. I think an important clarification to make is whether or not we currently know how to write a function isn't relevant to whether it's computable or not.
• School-Cotton 2y ago
  > h(f) is either 1 or 0 Depending on f. The God-existence function doesn't depend on its input. You can also say, for example, let f: R->R be defined by f(x) = 1 if I'm a man, and f(x) = 2 if I'm a woman (or non-binary or anything else). Is the derivative of f zero? You don't know what the value is, but you can answer this question with "yes".
  • wodenokoto 2y ago
    So it’s just: In universe 1, the function looks like `return True` and in universe 2, it is `return False`? And it’s computable because nothing is really computed?
    • housecarpenter 2y ago
      Yes, that's right.
• minkzilla 2y ago
  AN interesting and non rigorous way to think of it is can the compiler optimize away the non compute-able part. So this: if (God does exist) return isPrime(3) else return isPrime(5) The compiler can take this and in the first pass say, isPrime(3) is just return true, isPrime(5) is return true. Then we have an an if else with the same return for both cases, this is the same as return true!
  • wodenokoto 2y ago
    I like this explanation, but how would you apply that logic to If (god does exist) Return true Else Return False
    • minkzilla 2y ago
      I guess I misread the first part of the article while skimming. I think the key is this paragraph computability is about whether a computer program exists to map inputs to outputs in a specified way; it says nothing about how hard it might be to choose or find or write that program. Writing the program could even require settling God’s existence, for all the definition of computability cares. I guess in this case God's existence needs to be a compile time constant. I saw it elsewhere in the comments but I think computability as defined in Computer Science and used by the author is more strict a definition than you or I are/were thinking, and that is really the main point of the article. People confuse computability with "can it be computed". Missing values (such as knowledge of God's existence or null values) mean you can not computer something but that is a different thing.
    • deleted 2y ago
      [deleted]
    • deleted 2y ago
      [deleted]
    • ludwik 2y ago
      It would be something like this: if (God does exist) return isComputable(() => true) else return isComputable(() => false) (where `() => true` / `() => false` are functions, returning true / false) You do know that the code above will always return "true", without having to know whether god exists.
• pdonis 2y ago
  > Why is f computable Because f is either the constant 1 function or the constant 0 function, and both are computable. The fact that we don't know for sure which of those two functions the label "f" refers to doesn't matter if all we are asking is whether the function the label "f" refers to is computable. We know it is because both of the possible referents are computable.
  • bhewes 2y ago
    Double Entendre one of my favorite poetic devices.