For example: does there exist an algorithm that computes the Kolmogorov complexity, K(s), of string s for arbitrary s? It is well-known that the answer is "no" — there is no Turing machine that takes as input a string of arbitrary length and computes K(s). The proof is quite brief and involves the halting problem.

But if we ask a similar question: does there exist an algorithm that computes K(s) of string s for arbitrary string s with length < n? The answer is yes! And there exists such an algorithm for any value of n.

How is that possible? Think about it for a second, because the answer is going to disappoint you: simply create a Turing machine that consists of a giant lookup table for all 2^n possible strings that prints the value of K(s) for each one.

But wait, that's cheating! Maybe so, but any specific implementation of the algorithm has a finite description. And by definition, K(s) is also finite for all s. While it's true that I haven't provided any particular method for determining the value of K(s) for all 2^n strings in order to actually create the lookup table, that doesn't matter. Such an algorithm nevertheless exists, regardless of whether you can find it or prove that it does what you want it to.

So in a sense, finite questions about a finite number of things are sort of uninteresting from the perspective of computability, because you can always write a program that just prints the answer for all of those things (how quickly it does this is another matter). But when you extend the question to an infinite number of things, computability becomes much more interesting, because you don't know whether something finite can provide answers to questions about an infinite number of things.

But what's really happening is that "infinity" is standing in for "approximate, eventual, steady state behavior for sufficiently large N, larger than any specific one-off gimmick you might think of".

In the real world, though, those gimmicks are important, and the constants and low-order terms ignored in a Big-O comparison are important to real world performance.

There is constant tension between "big enough problem that the contant factors don't matter", and "small enough problem that it conforms to the (often implicit) of what 'constant' means (example: 32bit ints masquerading as integers)"

Oh no, not at all. My point is that the concept of infinity is in a sense necessary for the mathematics involved in developing algorithms to solve problems. We are performing induction to "predict" the behavior of an infinite number of Turing machines without actually running them. We can't just iterate through all possible programs, so we have to use patterns that apply in a consistent way to all possible problem instances to narrow down the search space.

> approximate, eventual, steady state behavior for sufficiently large N, larger than any specific one-off gimmick you might think of

I know this is how computational complexity theory is considered from the perspective of many software engineers, but my point is a bit more fundamental. Computational complexity theory ultimately isn't concerned about any one particular problem and how to solve it quickly for practical applications—the goal is to understand what is and isn't possible with computation overall and with what resources (time, space). Why solve one problem when you can solve all of them?

But to do that requires really understanding the mathematical structures behind computation itself. If you're a formalist, instead of thinking of infinity as "the limit of large n", you think of it as a concept in a formal system that involves manipulating symbols according to a set of axioms and inference rules. You can use whatever intuitive human-scale analogies you prefer when thinking about large cardinal axioms or the continuum hypothesis, but at the end of the day, all that matters in terms of computability and computational complexity is how exploring the space of proofs derivable from these formal systems leads to a better understanding about the behavior of Turing machines (and thus the nature and fundamental limits of computation).

Well, only computability theory, not complexity theory, which you mention in the rest of your post.

of course - n is by definition a finite number!

and in fact at infinity, all finite numbers are quite small, actually. A mile might as well be a millimeter, from your chair at the end of the universe.

And your scenario is basically just "hilbert's infinite hotel, on a computer" - we can of course add another program simply by moving all the existing programs 1 spot over... and it remains the exact same size of table needed to compute it!

I would actually generalize this and just say that most people have poor intuition of how infinities (alephs, etc) and transfinite mathematics work in general. it's not a common subject, it's not a subject with everyday relevance, and it's deeply steeped in the emergent properties of mathematics and category/set theory. Like not only are infinities bigger than any finite number, but some infinities can nevertheless be bigger than other infinities etc - these are not things that are immediately obvious to the 3rd-grade concept of "infinity" that most people stop at.

the much more interesting question would be if there exists an n < infinity such that the algorithm can be computed, and of course the answer is no (darn, there goes my turing prize).

Everything can be textualized, but making a complete interpreter for it requires understanding what intelligence really is.

For example, we don't (yet) have a proof that there exists (constructively) a program that that prints out the answer to the P=NP problem.

I had some commentary in my thesis about this issue with regards to computable Julia sets. Mark Braverman proved that every (quadratic) Julia set is computable. But, as he notes, his proof isn't uniformly computable. Instead he develops 5 machines that attempt to draw various sets (at whatever desired resolution) given the parameter for the Julia set desired. For each Julia set, one of these 5 machines will correctly draw the set.

When doing constructive mathematics, the constructive notion of a compact set roughly corresponds to being a computable set in the sense we need for computable Julia sets. We cannot constructively prove that every (quadratic) Julia set is compact. Instead we have to divide the complex plane of possible parameters of the Julia set into multiple regions, and within each of those regions we can prove all of the corresponding Julia sets are compact.

In classical mathematics the union of all these regions is the entire complex plane, but this result doesn't hold constructively. Analogously, in classical mathematics the union of the positive reals, and the non-positive reals is the whole real line; however, again, this result doesn't hold constructively.

The constructive mathematics approach clearly states exactly what additional information is need to actually realize the computation of a (quadratic) Julia set: that is you must state in which of these regions of the complex plane you given parameter belongs to, which in turn tells you which of these 5 machines you need to run to get actually get the image you want. This is a much more satisfying answer.

People just instinctively know that you need to know which side of the disjunction you're on, and they haven't been trained in classical logic to forget it.

We may enumerate the turing machines and call ours the M-th one. Given a boolean expression P, increment a counter N and run the first N turing machines on P for N steps, check each of the outputs of these against the certificate checker.

If M runs in time O(|P|^n) and the certificate checker is O(|C|^m) and then our hybrid machine runs in something like O((M+|P|^n)^2m).

All we're missing is a proof.

That's really interesting. Does this essentially correspond to a proof of being able to compute the correct set with probability no less than 1/5?

For the question "which of the 5 is correct?", is it presumed that there exists a proof that hasn't been found yet or that this is undecidable (e.g., within ZFC)?

You want to object “but those programs don’t know anything about Turing machines. They don’t count!” But that’s not what decidability is about. You might want to think something like “ok, but figuring out which of those programs gives the right answer is undecidable,” but again, no, that has a defined true or false answer too. The problem can only become undecidable once it’s extended to an infinite set of machine/input combinations.

> Let f:{0,1}*→{0,1} be the constant 1 function if God exists, or the constant 0 function if God does not exist. Is f computable? (Hint: The answer does not depend on your religious beliefs.)

The precise question is would f be computable (i.e. exists a Turing machine M st. f(x) = M(x) everywhere).

Would f be computable? Yes, because in either world there is a trivial TM, M = 1_M or M = 0_M. In contrast, the originally worded question "Is f computable" is a modally invalid question, analogous to the Sleeping Beauty or Red Envelope paradoxes. It's like, grammatically incorrect.

Another way to look at this is the dependency on God or some potentially real fact is more like a compiler directive or pragma whose parameters get filled in later but prior to use, so the question when asked correctly is just about unpacking the strict definitions of function and computable, both of which are explicitly defined in Sipser.

I don't think these paradoxes are relevant here. They only highlight a fact that application of the pure mathematical notion of probability to the actual reality is sometimes a non-trivial process. It's not a surprise, if you think of it the fact that the probability theory works _at all_ when applied to reality is extremely puzzling and has been a subject of various scientific and philosophical inquiries (see "probability interpretations").

Now the resolution you propose ("would" f be) doesn't seem to resolve anything. The purpose of "god" question is to force the reader to abstract away from a particular P-NP problem and understand that the whole concept of computability is useless for constant functions. So what you suggest is helpful only if you could also apply it to the original P-NP question, which I don't see so far. How the modalities approach come into play here, for a well-defined mathematical question?

A slightly longer way to write this that I think would cause fewer parse errors is

> Let f:{0,1}*→{0,1} be the constant 1 function if God exists, or let f:{0,1}*→{0,1} be the constant 0 function if God does not exist.

Whether there exists such a predicate that conforms to your conception of God or not is a separate (non-mathematical) issue.

I think it's a bit like the surprise people show when they learn that in classical logic a false statement implies everything. Mathematics has strict formal rules, and it's important to leave aside your preconceptions of the semantics of various words like "implies" and "if" when engaging in it.

Let G:t∈ℝ⁺->{0,1} be the 1 if God exists at time t and 0 otherwise.

EDIT: And of course this starts getting even more interesting when you analyze G in a non-inertial reference frame.

> Let f:{0,1}*→{0,1} be the constant 1 function if God exists, or the constant 0 function if God does not exist. Is f computable? (Hint: The answer does not depend on your religious beliefs.) [emphasis mine]

The alternative is not part of the function. The function f does not branch based on the value of "God exists". The branch is in the metalanguage. We don't know whether f = 0 or f = 1, but whichever it is, it is computable because both possible functions are computable.

But, I would go further: if f did include the branch, and the domain of the function is 0 (God doesn't exist) and 1 (God does exist), then we still have a computable function in the sense that we can compute a result for each value of the domain.

The confusion effectively is a matter of pushing a free variable whose value is taken to be unknown into the branch condition in f.

[big number from Wikipedia] "exists" and is "computable" in an academic sense, even though its digits cannot fit in our universe.

> Let n equal 3 if God exists, or 5 if God does not exist. Is n prime?

Sure, I'll happily quibble! You're using excluded middle to assert that n is either 3 or 5, but you haven't justified that excluded middle holds for the proposition "God exists".

If you’re going to quibble over whether LEM is justifiable in this case, then you need to justify why you’re only concerned about LEM; why not drop ex falso too (Kolmogorov had serious issues with this axiom, and initially considered it to be incompatible with a constructive logic) and work in a paraconsistent logic?

Also, depending on the precise formulation of this proposition, it doesn’t necessarily need LEM.

(I agree that there are formulations which don't require LEM, but it's important to be precise, especially when writing to dismiss a common misconception among people who haven't got the concepts crisply in their minds. "Is this quantity computable?" is very close in spirit to "can I compute the value of this quantity?", and LEM is exactly the kind of axiom which shows the difference.)

> Ex-falso has trivial computational content, and we use it all the time: it's `panic!()`.

I have major issues with the computational content of a bottom type; my interpretation of the BHK semantics would not admit ex falso as constructive.

Of course this all of this really stems from one’s notion of semantic truth: any non-trivial semantic theory of truth can be argued as the “one true logic”, and there’s not much anyone can say otherwise! As I see it, it really comes down to how useful it turns out to be in modelling the particular domain of discourse.

As it happens, I’m more than happy to accept classical logic: I believe the principle of bivalence is how the world works, and as a result I’m forced to admit LEM if I want my proof calculus to be complete.

You are right that pointing out the connection to LEM is important and worthwhile, regardless of formulation.

Why does it rely on the axiom of choice? It’s a consequence of the obvious fact that for every integer n, there exists a program that prints n. This doesn’t require choice.

Also whether n is prime is up to the will of God, if God exists.

A God is not necessarily bound to the "laws of physics" or even basic logical necessities (a God that does comes from a specific line of theological reasoning, not the general case).

He could even make 6 odd if He so wished - altering all math and logical consistency and the whole universe, or just make just 77 even and every other number odd, making so every mathematician finds the new arrangement perfectly consistent and consider it to always have been the valid one!

So the answer does kind of "depend on your religious beliefs".

If you're allowed to invoke God ironically in the question, you're allowed to take that seriously (meta-ironically?) in the rebuttal!

The idea of "new doesn't affect old" is an idea based on logical and temporal consistency. God is not bound to those.

In fact the current system of odd/even - as well as any other system and law, including the "excluded middle" - can be understood to be God's arbitrary creation. You consider it logically necessary and absolute just because God willed it so, you'd be considering a different one with any arbitrary change as just as logically necessary and absolute if/when God willed it :)

People create a lesser conception of God, with specific boundaries and limitations, and then gloat how he is limited. Well, let's instead start with the more common conception of God as limitless and with total arbitrary power.

That entirely depends on your specific god belief. Suppose someone believes that god is the eternal principle of consistency?

>Well, let's instead start with the more common conception of God as limitless and with total arbitrary power.

If god is capable of anything can god decide to make it such that there is no god? Can god decide to self-limit god's own powers? If god intrinsically encompasses all possibilities does that include the possibility of godlessness?

You quickly get to then point where the concept ceases having any meaning.

My sentiments exactly.

The whole point of the comment was that the part saying "The answer does not depend on your religious beliefs" was wrong.

>If god is capable of anything can god decide to make it such that there is no god? Can god decide to self-limit god's own powers? If god intrinsically encompasses all possibilities does that include the possibility of godlessness?

Yes. Trivially so. And He can even make it so godlessness involves the presense of God too, without there being any logical inconsistency even (since he's so powerful he shapes logic, not the other way around).

Except if they wanted to say "The answer, iff your religious beliefs are conveniently tame and constrained, so that your God has limited powers and is bound to respecting excluded middle, the laws of physics and other such constraints, doesn't depend on your religious beliefs".

Any other movie quotes to put forward in lieu of counter-arguments?

Logical consistency only cares about propositions and their relationship, it doesn't care whether an entity involved in one is fictitious or not.

Yep. Possible, and endless fun for a certain sort of person!

>Like, is there a point in asking/answering anything if anything goes?

Sure, since at any given time anything God wills goes!

In contrast laws of physics are a real world thing, and any omnipotent being can meddle with it, basically by definition.

You can't, under your logical constraints.

God has no such constraints, not just in the physical but also in the logical realm. He can make it so that assuming the law of excluded middle and not assuming it at the same time, is compatible and consistent.

It could be Author chose (due to their extensive training) their (very strict!) definition of computable, then wrote an entire article about their specific definition of a word, and lambasted the world for asking dumb questions using a different definition of the same word, and refusing to elaborate.

This honestly happens all the time at work, when talking to academics, or even talking to laypersons. It's hard to establish common nomenclature, and drawing a line in the sand at their nomenclature and asking people to catch up is exhausting.

Philosophers spend a lot of time in term definitions and it's the only way to avoid the conversation devolving into talking past each other.

Rigor might be exhausting, the same way that exercising is. No one is forcing you to do it, but you can only reap the benefits by making the effort yourself.

And people curious about P versus NP or Busy Beaver should begin by learning some basic TCS, so they can understand what people who study the problems professionally are saying.

I think some people think of “god exists” as unknowable, or undefinable, or ill-defined, etc. But the “riddle” requires P to be exactly true or false. Seems one of the pitfalls of mixing natural language with mathematics.

Your choice of P (whether the continuum hypothesis holds) is still ill-defined! This is because the answer depends on the system of axioms one subscribes to. Or, if you feel like playing God, you may pick an answer (CH holds / does not hold) and find axioms that support it. (Which can be as simple as ZF + CH holds/does not hold.)

It is very powerful to be able to advance past an uncertainty in some logic net and establish certainty on the other side. It's not a thing that comes up every day by any means, but it's a great tool to add to your belt.

And you can see even in this comment thread that it is not intuitive for people.

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

    if (God does exist)
      return isPrime(3)

    else 
      return isPrime(5)

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

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

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.

It's the difference between:

    does_program_x_halt():
      return true

    does_program_halt(x):
      if x halts:
        return true
      else:
        return false

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.

  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
          }

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.

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.

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

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

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

I thought this was not necessarily true.

For example, one beaver might halt after some integer number of steps. This would be the potentially very large integer the author is referring to. Another might go into an infinite loop, and clearly never halt.

My understanding of the where incomputability entered the discussion is the third possibility, that a beaver might have complex behavior that neither ever halts or ever loops.

The author touches on answering this, drawing the distinction that a specific answer might not be provable. But I'm not sure I understand.

How would the answer for a specific integer be computable if it's impossible to determine what the value for the function of is for that integer?

> How would the answer for a specific integer be computable if it's impossible to determine what the value for the function of is for that integer?

Can you say precisely what you mean by “computable”? I suspect you’re using an intuitive definition that’s different from the author’s formal definition.

What if a similar proof is made for a Beaver? That a specific beaver is constructed such that

1: It probably never halts 2: Proving that it never halts is a paradox

Something like that. If assignment of BB number for BB of that size depends on that proof, then the BB value doesn't exist.

And what else would it depend on? How could a smaller number be selected when larger potential numbers cannot be ruled out?

Then we will never be able to find the Nth beaver number for the corresponding N.

That doesn’t mean it is undefined or uncomputable. It actually has nothing to do with it. There is a computer program that prints out the number of hairs on my head. Doesn’t matter that you will never know how to write that program.

Again, uncomputable is being used in a technical sense here which is why I asked you what definition of “computable” you’re using.

"Is X computable?" is asking if there is a program that is capable of printing X out. For any integer, the answer to this question is trivially yes.

But when people are asking "Is BB(6) computable?", that's not really what they're intending to ask. What they're trying to ask is "is it possible for us to figure out what the value of BB(6) is?" In a more precise sense, the question is "Can we prove {BB(6) = x} is a true statement for some value of x?"

To some degree, I think Scott is being somewhat specious here. The question may be somewhat malformed as written, but it's also pretty clear to an expert what the question meant to ask, and--especially when you're targeting a more lay audience--insisting on giving the trivial answer to the clearly unintended question isn't likely to help the situation much.

It doesn't address what I am claiming though.

The busy beaver is not defined entirely by halting vs not-halting.

Looping beavers are excluded as well.

The middle ground I am claiming is that there is a middle ground between non-halting and provably non-halting.

I'm claiming there could be a non-halting Beaver that is impossible to prove, which would mean there is no answer for the BB function.

> Looping beavers are excluded as well.

Looping beavers do not halt.

> there is a middle ground between non-halting and provably non-halting

Yes, there are turing machines that encode mathematical theorems which are independent of ZFC, meaning they cannot be proven to halt or not to halt. The state-of-the-art is BB(748), which is known to be independent [0].

There are also much smaller known turing machines which encode classically difficult math problems, like the Goldbach conjecture [1]. This means that the value of BB(27) cannot be proven until the Goldbach conjecture is proven or disproven, as until that is done, we will always have something like "BB(27) is N unless the Goldbach conjecture is false".

However, our inability to prove these things does not change the fact that they have specific values. To stick with the BB(27) example, say that it seems we've narrowed it down to some huge number A, or a number dependent on the first number for which Goldbach does not hold. Call that second number B. We may be unable to find the value of B (doing so would disprove Goldbach), but it is still a specific number. There still exists a concrete value for BB(27)--it's A if Goldbach is true, and it's B is Goldbach is false.

[0] https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-unde...

[1] https://gist.github.com/anonymous/a64213f391339236c2fe31f874... This 27-state machine halts when it finds a counterexample to the Goldbach conjecture.

Is there a way to formulate or rephrase this such that we could effectively ask this question? I'm thinking like some way of formally encoding the question (does P=NP?) that could be plugged into a turing machine which then computes the answer.

I guess I was thinking something along those lines. Perhaps if there's a way to "generalize" the P vs NP question, then we can hypothetically give some mildly meaningful answer about complexity.

Similarly the traveling salesman problem is NP Hard but there are inputs that have trivial outputs.

> Could the P versus NP question itself be [mathy-difficult in a way] that makes it impossible [for humanity to know the answer]?

Which becomes a family of interesting questions when you substitute exact expressions for the bracketed natural language

Thinking of a way for smart people to formally encode questions and hand them off to dumb computers is what led to the whole field of computing in the first place!

Regardless of whether yes, the given example program is computable (it is), the general folks of the CS world probably understand it to be uncomputable because no computer could run that properly due to the impossible complexity in `if god`.

It does bother me a little bit when an academic writes an entire article about their specific definition of a word, then lambastes the world for asking dumb questions using a different definition of the same word, and refusing to elaborate.

> This is the best way I can think to formalize your question. These are some ways it's different than what you asked, but here's why I think it close enough, and this is the answer in this case.

are usually better than asserting,

> There's absolutely no way to formalize your question. It's utter nonsense and I won't answer it.

Even when, to the answerer, the proposed formalization seems much different from the informal question, the questioner is often satisfied with the answer.

Let f: {0,1}* -> {0,1} = 1 if Paris contains at least one porta potty and 0 if it does not. This one is both computatable and you can actually run it with a true input. The one about God is also computable but can only be run with a guessed input. You can't guarantee the output corresponds in any meaningful way to the universe you live in, but it is still a computable function.

Maybe it's better to just consider f: {0,1}* -> {0,1}. "God exists" and "God does not exist" are both possible bit strings on their own. Can a program exists that outputs 0 if it gets one of these inputs and 1 if it gets the other? Of course it can. It doesn't matter if the input is empirically true or not.

Saint Anselm's Ontological Theory of Computation. "First.. imagine the most perfect function that could possibly exist.."

Yes, and one of them is "a fast program that correctly answers the P vs. NP question". We don't know which.

You being a clever programmer somehow know of a very powerful oracle, lets call the oracle Pauli. You're program works as follows:

  func main():

    response = write_pauli_asking_if_p_is_np() //synchronous, waits for response 

    if response is true:
      print(“P=NP.”)
    else:
      print(“P≠NP.”)

(This is of course not relevant to the oracle you suggest as that doesn't evaluate a noncomputable function, but it's relevant to what sort of "program" Aaronson is talking about here.)

The example is genuinely confusing to me because of the igtheism problem: the idea that the question of whether God exists is a poorly posed one, because God is undefinable. It's like dividing by zero or a type error or something. This was Bertrand Russell's perspective, for example.

Maybe the intent of the example is "here is a function whose inputs are unknown" but for me it was more like "here is a function whose outputs depend on an undefinable input."

The second example didn't seem much better for the same reason. Knowing that the output is prime regardless of the input — a logical conclusion from the "meta evaluation" of the function — doesn't seem to me to be the same as asking whether the function is computable.

To me it's like having the function depend on a contingency sort of like "if the color blue tastes like cheese, then..." It doesn't make sense.

If the example was meant to incorporate an unknown state (as opposed to an undefinable one), it would have been better off with a random unseen event or something, like a person flipping a coin in a different room. Or a particle decay in a box, but then that leads to quantum issues maybe which leads to the same sort of problem possibly.

No, it isn't. The if-then part of the question is about which of two trivial functions the label "f" refers to. It has nothing to do with the functions themselves or their computability. That, from what I can gather, is supposed to be the point of the question, but I don't think the question gets that point across very well.

> if response is true:

i've always wondered how people know when to stop (which, i guess, is relevant to the subject matter).

e.g. why is your next step not

> if (response is true) is true:

Depending on language

>if response:

could mean "response" is true,1,not empty, X....

Similarly for every hash function there exists a program that outputs a hash collision in well under a second. Just hardcore any collision and print it to the screen. [2]

[1] If you want to be pedantic then there's a third option that prints some more complicated statement about the relationship between standard axioms and P?=NP.

[2] Please don't ruin my short argument by pointing out that someone can create a hash function with output size in the petabytes range :)

Those constant functions aren't proofs, the proof is in coming up with a series of computable steps to reduce a model of P=NP into that constant function. That is, the proof is the computation itself, not just the constant value.

What the author did describe is a function that we can only evaluate when we already have an answer for P = NP, not a function that computes it.

Computability is defined in terms of functions that map the input to yes/no. A function is computable if there exists a representation that computes it correctly for any input and eventually terminates. Every yes/no question where the answer does not depend on the input is by definition computable. The corresponding function is either the one that maps every input to "yes" or the one that maps every input to "no". We may not know which one, but that's irrelevant.

In some sense, computability is similar to probability. Your intuition is wrong, and following it only leads to further confusion. But if you unlearn it and rebuild it from basic principles, things become much clearer.

NP, by definition involves decision problems, but many NP-Hard problems are optimization problems.

More specifically NP is the set of decision problems solvable by a NTM in poly time with the following conditions:

1) If the answer is "yes," at least one computation path accepts. 2) If the answer is "no," all computation paths reject

Equivalently is is the set of decision problems verifiable by a TM in poly time.

Modern programming tends to only care about #1, and structured programming paradigm helps with that.

People not moving past NP in complexity theory is the real problem here. I also blame using the 'trys all answers at once' NTM intuition vs the max lucky guesser which makes it less silly.

But didactic half truths do really hurt. Entscheidungsproblem is better for teaching people in my experience.

Of course it's a not a proof of "P=NP", but no one is asking for it.

> What the author did describe is a function that we can only evaluate when we already have an answer for P = NP, not a function that computes it.

Yes. This function is still computable though. The question of computability doesn't depend on humans being able to evaluate this function on a given day in history.

But I think the issue there is the assumption that it even makes sense to define a function over ‘classes of questions’.

These kind of handwaveing are quite common in math. For example, Axiom of Choice assume there exists a choice function. It does not specify how.

It's so trivially obvious when you know this that it isn't worth talking about. It is also completely unreachable for many people who don't know what these terms mean.

I have, in the past, had a misconception of this shape in a different field. In my case, it was my belief in DNA as code that is executed by things that message-pass between each other sometimes directly through the substrate and sometimes by modifying the DNA. Overall, this isn't a useless model but I needed to know when to not get addicted to it.

To biologists with mathematical backgrounds, it's obviously wrong to just take the TM execution of DNA as a model. To me, it was less so.

So it's just unfamiliarity with the basics.

Perhaps an interesting aside:

I always thought that mathematical logic, or at least the parts we typically learn to describe CS concepts, is pretty hardcore in terms of the abstract thinking we have to perform.

Until I saw what philosophers have to learn...

They are taught much richer and complex concepts that can describe how logic bleeds into written/spoken language and how you extract this logic from text. Logic is used, recognized and analyzed in pretty much _everything_ they do.

In contrast, we get by with the kindergarten version of logic for most things.

Let P be a set of programs that print all possible answers to the proposition P==NP . In this case, the possible answers are {"true", "false", "undecidable in ZFC"}. Then there trivially exists a program that can print the true answer to the proposition.

Everyone understands this. The amount of support he is getting here for the poor presentation is astonishing.

you might say, no, plenty of academics teach undergraduates, and undergraduates are super ignorant. but undergraduates generally don't care whether bb(123456789) is computable or not unless that's on the exam, and their incentives run strongly counter to arguing with the professor if they're unconvinced; the way they've learned to play the academic game is by producing the desired answers, because that's what gets good grades, not finding holes in professors' reasoning

so i think people like scott and sabine hossenfelder are doing profoundly important work, and the groundless controversies around them demonstrate not the error of their ways but the astounding degree to which the current academic system is failing to educate the public

I don't see how the second part of the sentence implies the first. The primary role of academics is generating new knowledge. Educating the ignorant is a public service that few are willing or able to do. Scott Aaronson deserves a lot of credit for dedicating so much energy to his blog, it does not mean that 99.99% of his peers are wrong in focusing on advancing the frontier of knowledge.

If I ask you to write a program that returns false if 4 is an odd number and true if it's an even number, you would say that's trivially computable:

def is_four_even(): return 4 % 2 == 0

Of course there's an even _simpler_ function:

def is_four_even(): return true

The two are both valid ways of computing that function. Four is even, it has always been even, you don't need to check if it's even, you can just return true.

For all these complicated questions about that people are all getting wrapped up about the only difference is that we currently don't know how to write the first version of the function, and we don't know which of "return true" or "return false" is the correct version of the second form of the function, but _the second form surely exists_, which means that it is computable. Either P=NP or P!=NP, and that has been true or not true since the beginning of time, and _one_ of those two functions would have been correct to use from the beginning of time. It's computable, we just don't know which one to use right now.

As soon as someone proves the status of P?=NP, you can just pick one of the two ('return false' or 'return true') if someone asks you write the function. It also doesn't really matter if a statement is provable in theory or not. Whether or not it's possible to prove that P?=NP, it is either true or it's false and it has always been either true or false, and one of those two programs is correct.

This is a pretty philosophically extremist statement (relying on a hardcore version of Platonism) and with my handle I can’t just let it stand unchallenged. :)

I’m actually somewhat more sympathetic to excluded middle for P?=NP than for some other statements, so let’s start elsewhere. I don’t think it’s at all obvious that the continuum hypothesis is, and always has been, either true or false. We know it’s independent of ZFC, of course, and there are sensible “extra” axioms that would resolve it in opposite directions (e.g. V=L vs. MM). In order to believe that there’s a fact of the matter you need to posit a very well-populated Platonic realm, despite not needing that kind of philosophical commitment to do mathematics.

Well, maybe P?=NP is just simpler than CH. It probably is! But you can imagine a case where it isn’t; e.g. if there exists an algorithm for 3-SAT (call it Algorithm A) which can be proved to be asymptotically optimal, and which runs in O(n^10^100) time if !CH, and exponential time if CH. Then the P?=NP question would be equivalent to CH, and you should have the same beliefs about its truth value. If you’re like me, that means you’re skeptical that it has a well-defined truth value “for all time” at all.

It's the same essentially as a function that returns true if any two lines will eventually intersect. The correct answer depends on whether you're in curved space or not. That the correct answer depends on the domain or axioms doesn't make it non computable.

There's just no case where a constant function isn't computable in the technical sense.

Is this true for the BB function though?

What if there is a beaver that never halts or loops, and has behavior sufficiently complex, such that it's impossible to prove it will never halt.

Then for rules of that length, the second form doesn't exist.

A Turing machine with finite states must eventually either halt or loop. Those are the only options, because there are only finitely many configurations it can be in, and each configuration completely determines the next.

A "beaver" is defined to not loop. All "beavers" must halt, because otherwise they're just not considered for BB(n). All the challenge is in proving whether a given Turing machine does (or does not) halt, and therefore must not (or must) loop. Proving "halt" or "loop" proves the other one.

Yes, the function `busy_beaver_6() = 576125642131574254..." must exist.

There are infinitely many configurations if you consider the tape.

It is still true, of course, that every Turing machine either halts on a given input, or doesn't.

If you are including the tape, it's not true that there are finitely many states. If you're not, then "looping" as you've defined it is not excluded from the definition of the busy beaver problem, and does not imply that the machine never halts.

An infinite Turing tape can be in an identical state, however. The number of states don't have to be finite. If a Turing machine returns to an identical state, it will not halt. That's what we call looping.

An example of an identical state is 1 at indexes 3 and 5 of the tape, and 0 everywhere else.

Another example is the Brainfuck program `++[]`. This trivially returns repeatedly to a given finite state.

Here's an example of a bf program that never returns to an identical configuration, and also never halts. The corresponding TM would be excluded from consideration for the busy beaver number, despite never "looping" according to your definition.

    +[+]

The Turing machine writes and reads from an infinite tape, and as such, the number of configurations (the machine's state + tape) is countably infinite.

Specifically, ZFC is consistent iff ZFC+“Y&A’s machine does halt” is consistent iff ZFC+“Y&A’s machine never halts” is consistent (a theorem in a fairly weak ambient metalogic). So you can take a stronger set theory that does prove the answer, it’s just that thus far we have no reason to prefer theories that answer yes to theories that answer no.

(You don’t have to accept excluded middle, and it can on occasion be useful not to[2], but pragmatically you’re going to have a lot of difficulties even with first-year calculus unless you do.)

[1] https://scottaaronson.blog/?p=2725

[2] https://www.ams.org/journals/bull/2017-54-03/S0273-0979-2016...

How can we justify not steelmanning a ternary approach to halting? Can someone show me one proof which doesn’t rely on “muh do the opposite” (how do we know the halts program can’t detect this and crash with Err(ParadoxError)?) or the circular logic appeal to Rice’s theorem which itself depends on halts being undecidable? I’ve yet to find one. Collatz Conjecture? Only with unbounded memory and time, which is un-physical. That’s something we learned from Ray Solomonoff: the difference between doable and impossible is often a time limit.

According to the concept of equivalence, aren’t p and np both equivalent and not, in infinite ways (a “filibuster proof,” just make the argument for and against their equivalence based on their mutual relationship to each counting number), and fundamentally designed to be not equal by virtue of us naming them differently?

Finally, what the heck was Gödel thinking to assume we can assign different numbers to zero and the logical not? If the Gödel numbers are off, or even if not, how can an incompleteness theorem be complete? And if the incompleteness theorem is itself incomplete, why should we take it super seriously?

Just seems like we take the validity of these fundamentals for granted, and “most computer scientists believe X” is not exactly a strong argument for anyone to believe X, because it’s an appeal to mass belief.

Lest anyone think I’m a snooty smarty pants, I’d like to say i think I’m an idiot. Every day i beat myself up for being an idiot. Go ahead and feel free to downvote for this, or call me a crackpot, but a bunch of bedrock ideas of theoretical cs really are weird and suspect

- decision problems with Boolean outputs are inherently nerfed compared to ternary ones with options to refuse to answer or to stop programs from outside - p vs np suffers the same problem, since “equals” or “not equals” ignores the infinitely huge elephant of “equivalence” (not equal how?) - Gödel numbering zero (an integer) and logical not (a function) separately is a false difference because zero IS not (to the universe itself) —

to say we can’t form complete systems out of items we ourselves falsely separated in the first place is what the universal substrate, if it could speak, might call a “skill issue”

> How can we justify not steelmanning a ternary approach to halting?

I'm not certain I understand what you mean here. In actual practice, the usual approach to undecidable problems--which come up all the time in compilers and formal methods, mind you--is to build a trichotomy of "yes", "no", and "don't know" (sometimes expressed "timeout"). What undecidability says is we can't squeeze the "don't know" category down to nothing, but in many circumstances, that's just fine.

> Can someone show me one proof which doesn’t rely on “muh do the opposite” (how do we know the halts program can’t detect this and crash with Err(ParadoxError)?) or the circular logic appeal to Rice’s theorem which itself depends on halts being undecidable?

Depending on how you define "muh do the opposite", this may be impossible. The essential crux of the theorem is that once your system reaches a certain level of power, it admits the possibilities of quines, which enables a level of self-reference that leads to paradoxes.

The best attempt I can give, that only indirectly reaches into self-reference is this:

Let f(x) be a program that returns the size of the smallest size program needed to output x (this is called Kolmogrov complexity). Let h(p) be a program that returns whether or not the input program p will halt. If h(p) exists, then f(x) necessarily exists:

  for p = 1 to infinity:
    if h(p) is true:
      if p computes x: return sizeof(p)

  for x = 1 to infinity:
    if f(x) > y:
      return x

I should also note that this is required by our conventional definition of program (specifically, a Turing machine). There's definitely models of computation more powerful than Turing machines, but these are not believed to be physically realizable (the Church-Turing Thesis); in any case, the diagonalization form of the proof of the halting problem's uncomputability indicates that these more powerful methods are also susceptible to their own variant of the halting problem.

I don’t even understand what you are getting at. But humbling ourselves and learning new things, especially such influential thoughts that mathematical giants such as Gödel and Turing gifted us with (and were since refined by hundreds of very smart people) should be the first step. All these thoughts were refined over a century, or half. It’s not some proposition that sounds cool and might later be proven wrong.

A Turing machine is fantastically simple and the halting problem is well-defined over it — it has n states, and one of them is labeled as HALT. Does it ever get to this state? There is no ternary option here.

(Note: Turing didn’t even consider them halting, but used an equivalent problem)

[Not yet finished the article]

Author says the answer is True. I say the question is malformed, and cannot be answered.

Let P be an arbitrary program and let n be equal to 3 if P terminates, or 5 if not.

Is it still malformed? Is so, then how about

Let n be equal to 3 Goldbach's conjecture is true, or 5 if not.

To answer a question, you first have to be able to parse the question.

   fn is_n_prime_whether_or_not_God_exists()
       if (is_prime(3) && is_prime(5)) { // early return 
            return true;
       } else { 
            return three_if_God_exists_five_otherwise(); 
       }
   }

> vague existence claim of a program that cannot be concretely written

It can be concretely written. It's either "return True" or "return False". As of today we don't know which one of the two is this. However our lack of knowledge is not relevant to the question if it's computable or not. Definition of computability doesn't rely on it.

> unless it takes "P==NP" and "P!=NP" as inputs, which would be a tautology.

It doesn't take any inputs at all since none are necessary. It's a constant function. The question of computability isn't relevant for constant functions or for functions with a finite set of possible inputs -- they are computable as switch-case on all possible inputs.

The problem only appears with functions that have an infinite set of possible inputs where the switch-case approach won't work. You need an _algorithm_ to convert inputs to outputs and sometimes this algorithm just can't exists, regardless of how far we've got in proving truthfulness of various mathematical statements.

That clearly implies solving. Aaronson is pretty sloppy with his own definitions and yet criticizes his students.

An unambiguous presentation would be:

1) Contrary to usual language use, we define "answer P?=NP" as "print 'yes' or 'no' or 'undecidable'".

2) By "program" we do not mean a single program, but three separate programs that print "yes", "no", or "undecidable".

3) We claim the existence of the program, not that it will ever be possible to know which of the three programs is correct.

You can think of it not as he is describing three separate programs, but giving three separate possible descriptions of one program and asserting that one of them is indeed the correct description.

Consider this rephrasing of the question: “Let X be an NP-complete problem. Can X be solved in polynomial time?” This is a problem with an infinite number of instances, all of which reduce to “P?=NP”, so we know that this problem can be decided in constant time.

The answer is trying to show the absurdity of the question. It's like asking for the time complexity of factoring 120. If there is no input to the algorithm, the answer is always trivial.

> The deeper lesson Sipser was trying to impart is that the concept of computability applies to functions or infinite sequences, not to individual yes-or-no questions or individual integers. Relatedly, and even more to the point: 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.

Yes, it is, but you can have functions that output other functions, and the question of computability applies to those functions as well. Sure, the constant functions are trivially computable; but one can also ask about a function that outputs one or the other of those constant functions depending on whether God exists, or whether the halting problem is solvable, or whether the Riemann hypothesis is true, etc., etc., etc. And in a post that is supposed to be about computability, saying "Gotcha! Misconception!" when people start talking about those kinds of functions instead of the trivially computable constant functions explicitly mentioned in the question does not seem to me to be a good strategy. As I posted in response to Aaronson in the comments there, before concluding from someone's answer that they have a misconception about computability, you should first make sure they don't just have a simpler misconception about what question you were asking.

The question revolves around computability: can the input be mapped to an output; does the calculation terminate and the output emerge.