If such a system proved that the answer to some decidable question was x, when the actual answer was y, then the system would prove a contradiction. If the system doesn’t prove a contradiction, then that situation doesn’t happen, so you can trust its answers to decidable questions.

If the only questions you accept as meaningful are the decidable ones, then you can trust its answers for all the questions you accept as meaningful and for which it has answers.

Also, “provable that nothing that exists can serve as such an oracle” seems pretty presumptive about what things can exist? Shouldn’t that be more like, “nothing which can be given in such-and-such way (essentially, no computable procedure) can be such an oracle”?

Why treat it as axiomatic that nothing that isn’t Turing-computable can exist? It seems unlikely that any finite physical object can compute any deterministic non-Turing-computable function (because it seems like state spaces for bounded regions of space have bounded dimension), but that’s not something that should be a priori, I think.

I guess it wouldn’t really be verifiable if such a machine did exist, because we would have no way to confirm that it never errs? Ah, wait, no, maybe using the MIP* = RE result, maybe we could in principle use that to test it?

You're literally talking about how I should regard the hypothetical answers that might be produced by something that I think doesn't exist. There's a pretty clear case of putting the cart before the horse here.

On being presumptive about what things can exist, that's the whole point of constructivism. Things only exist when you can construct them.

We start with things that everyone accepts, like the natural numbers. We add to that all of the mathematical entities that can be constructed from those things. This provides us with a closed and countable universe of possible mathematical entities. We have a pretty clear notion of what it means for something in this universe to exist. We cannot be convinced of the existence of anything that is outside of the universe without making extra philosophical assumptions. Philosophical assumptions of exactly the kind that constructivists do not like.

This constructible universe includes a model of computation that fits Turing machines. But it does not contain the ability to describe or run any procedure that can't fit onto a Turing machine.

Therefore an oracle to decide the Halting problem does not exist within the constructible universe. And so your ability to imagine such an oracle, won't convince a constructivist to accept its existence.

You can think that something doesn't exist in the general case, while still allowing that it might exist in unspecified narrow cases where additional constraints could apply. For example, there might be algorithms that can decide the halting problem for some non-Turing complete class of programs. Being able to talk in full generality about how such special cases might work is the whole point of non-constructive reasoning. It's "non-constructive" in that it states "I'm not going to construct this just yet".

Well yes. We can certainly make a function that acts something like that oracle in some special cases. But my point was to give an example of something that cannot be constructively created. The oracle that I described cannot exist within the universe of constructable things.

> Therefore an oracle to decide the Halting problem does not exist within the constructible universe.

I might be confused here, but isn't an Oracle to decide the halting problem something that everyone agrees doesn't exist?

The whole idea is for this to be a thought experiment. "If we magically had a way to decide the halting problem, how would that affect things" seems like a normal hypothetical question.

You literally cannot doubt the existence of this oracle, without doubting what existence means in classical mathematics.

Here is why a classical mathematician would say that this oracle exists.

Let f(program, input, n) be 1 or 0 depending on whether the program program, given input input, is still running at step n. This is a perfectly well-behaved mathematical function. In fact it is a computable one - we can compute it by merely running a simulation of a computer for a fixed number of steps.

Let oracle(program, input) be the limit, as n goes to infinity, of f(program, input, n). Classically this limit always exists, and always gives us 0 or 1. The fact that we happen to be unable to compute it, doesn't change the fact that this is a perfectly well-defined function according to classical mathematics.

If you give up the existence of this oracle, you might as well give up the existence of any real numbers that do not have a finite description. Which is to say, almost all of them. Why? Because the set of finite descriptions is countable, and therefore the set of real numbers that admit a finite description is also only countable. But there are an uncountable number of real numbers, so almost all real numbers do not admit a finite description.

The real question isn't whether this oracle exists. It is what you want the word "exists" to mean.

Hmm. Interesting.

If I'm following you, then most "mathematical" CS is based on constructivist foundations? E.g. while a halting problem Oracle might "exist" in the mathematical sense, it's not considered to "exist" for most purposes of deciding complexity classes, etc.

> The real question isn't whether this oracle exists. It is what you want the word "exists" to mean.

I was going to say the same thing. I'm not sure what "exists" means in some of these discussions.

It would be more accurate to say that most mathematical CS fits inside of constructivist foundations. Of course it also fits inside of classical foundations. So someone with constructivist inclinations may be drawn to that field. But participation in that field doesn't make you a constructivist.

As for what exists means, here are the three basic philosophies of mathematics.

The oldest is Platonism. It is the belief that mathematics is real, and we are trying to discover the right way to do it. Ours is not to understand how it is to exist, it is to try to figure out what actually exists. Kurt Gödel is a good example of someone who argued for this. See https://journals.openedition.org/philosophiascientiae/661 for a more detailed exploration of his views, and how they changed over time. (His Platonism does seem to have softened over time.)

Historically this philosophy is rooted in Plato's theory of Forms. Where our real world reflects an ideal world created by a divine Demiurge. With the rise of Christianity, that divine being is obviously God. This fit well with the common idea during the Scientific Revolution that the study of science and mathematics was an exploration of the mind of God.

Formalism dates back to David Hilbert. In Hilbert's own description, it reduces mathematics to formal symbol manipulation according to formal rules. It's a game to figure out what the consequences are of the axioms that were chosen. As for existence, "If the arbitrarily posited axioms together with all their consequences do not contradict each other, then they are true and the things defined by these axioms exist. For me, this is the criterion of truth and existence." See page 39 of https://philsci-archive.pitt.edu/17600/1/bde.pdf for a reference.

In other words if we make up any set of axioms and they don't contradict each other, the things that those axioms define have mathematical existence. Whether or not we can individually describe those things, or learn about them.

Over on the constructivist side of the fence, there are a wide range of possible views. But they share the idea that mathematical things can only exist when there is a way to construct them. But that begs the question.

Finitism only accepts the existence of finite things. In an extreme form, even the set of natural numbers doesn't exist. Only individual natural numbers. Goodstein of the Goodstein sequence is a good example of a finitist.

Intuitionism has the view that mathematics only exists in the minds of men. Anything not accessible to the minds of men, doesn't exist. The best known adherent of this philosophy is Brouwer.

My sympathies generally lie with the Russian school, founded by Markov. (Yes, the Markov that Markov chains are named after.) It roots mathematics in computability.

Erret Bishop is an example of a more pragmatic version of constructivism. Rather than focus on the philosophical claims, he pragmatically focuses on what can be demonstrated constructively. https://www.amazon.com/Foundations-Constructive-Analysis-Err... is his best known work.

Everyone agrees that you can't write an algorithm for a Turing machine (or computational equivalent) that decides the Halting problem for Turing machines in every case. Since this is explicitly worded as "you can't write an algorithm for..." it's in fact talking about a kind of constructive existence and saying that it doesn't apply. The oracle concept is normally phrased about "If we magically had a way to decide this undecidable problem in every case" but it's real utility from a constructive POV is talking about special cases that you haven't bothered to narrow down just yet.

> Things only exist when you can construct them.

This is exactly what I’m saying is presumptive! If constructivism is to earn the merit of being less presumptive by virtue of not assuming the existence of various things, it should also not assume the non-existence of those things.

Which, I think many visions of constructivism do earn this merit, but not your description of it.

The underlying problem is that constructivism and non-constructive reasoning are using the word "exists" (and, relatedly, the logical disjunction) to mean very different things. The constructive meaning for "exists" is certainly more intuitive, so it makes sense that constructivists would want it by 'default'; but the non-constructive operator (which a constructivist would preferably understand as "is merely allowed to exist"), while somewhat more subtle, has a usefulness of its own.

So having a different philosophy from you makes me presumptive?

What makes you presume that you have any business telling someone with different beliefs from you, what is OK to believe? You may believe in the existence of whatever you like. Whether that be numbers that cannot be specified, or invisible pink unicorns.

I'll be over in the corner saying that your belief does not compel me to agree with you on the question of what exists. Not when your belief follows from formalism, which explicitly abandons any pretense of meaningfulness to its abstract symbol manipulation.

No, that’s not what I said. Thinking you can determine a-priori that something that is logically self-consistent, cannot exist, if there is no reason that such a thing being physically instantiated would imply a logical contradiction, is the thing I think is presumptive.

Merely believing that such a thing (a halting oracle) doesn’t exist, isn’t something I meant to call presumptive, only believing that you can know a-priori (with certainty) that such things cannot exist.

I don’t claim that you are obligated to agree with me that they do exist. Someone who believes they don’t, but doesn’t believe they can know this as certain a-priori knowledge, would be no more presumptive than I am, and someone who is agnostic on the question of whether they exist would be less presumptive than I am.

Also, I disagree with your notion of “meaningfulness”. At a minimum, all statements in the arithmetic hierarchy are meaningful. The continuum hypothesis might in a certain sense not be meaningful.

> Merely believing that such a thing (a halting oracle) doesn’t exist, isn’t something I meant to call presumptive, only believing that you can know a-priori (with certainty) that such things cannot exist.

If you think that I was making that case, then you have misunderstood something important.

Constructivism is a statement about what kinds of arguments will convince me that things exist.

Could things exist that I don't believe in? Absolutely! There could well be a bank account with my name on it that I don't know about. Its existence is possible, and my lack of belief in it is no skin off of its back. But I still don't believe that it exists.

Similarly, the Platonists could be correct. There could be an omniscient God whose perfect mind gives existence to a perfect system of mathematics, beyond human comprehension. I have no way to prove that there isn't such a God, and therefore that there isn't such a perfect mathematics.

However the potential for such things to exist is a point of theology. I do not believe in their existence. Just as I do not believe in the existence of Santa. In neither case can I prove that they don't exist. And if you choose to believe in them, that's your business. Not mine.

There is nothing presumptive in my laying out the rules of reason that I will accept as convincing to me. There is a lot of presumption if anyone else comes along and tells me that I should think differently about unprovable propositions.

Now it happens to be the case that from the rules of reason that I use, I provably can't be convinced of the existence of certain things. That's a mathematical theorem. But the fact that I can't be convinced, doesn't prove that you shouldn't be convinced. You are free to be convinced of all of the unprovable assertions that you wish. And it is also true that on something like this, I have no way to convince you that it doesn't exist.

On meaningfulness, meaning is in the eye of the beholder. For example there are people who are willing to pay a million dollars for a century old stamp which was misprinted with the airplane upside-down. (See https://en.wikipedia.org/wiki/Inverted_Jenny to verify that.) They clearly find great meaning in that stamp. But I don't.

So again, you're free to find meaning in whatever you want. But you're in the wrong to object that I don't find meaning in what you consider important.

Ah, that I wouldn't call presumptuous. I just interpreted a previous statement you made as saying that one can prove that certain such things can't exist. So, I guess there was just a miscommunication (I guess I misunderstood.)

> emphatically DOES NOT demonstrate the constructive existence of such an oracle

Of course, but it shows that you can assume that such an oracle exists whenever you are working under additional conditions where the existence of such a "special case" oracle makes sense to you, even though you can't show its existence in the general case. This outlook generalizes to all non-constructive existence statements (and disjunctive statements, as appropriate). It's emphatically not the same as constructive existence, but it can nonetheless be useful.

That's like asserting the existence of a bank account in my name with a billion dollars in it that I know nothing about.

I won't ever be able to find a contradiction from that claim, because I have no way to find that bank account if it exists.

But that argument also won't convince me that the bank account exists.

That argument ought to convince you that there's a mere "possible world" where that bank account turns out to exist. Sometimes we are implicitly interested in these special-cased "possible worlds", even though they'll involve conditions that we aren't quite sure about. Non-constructive existence is nothing more than a handy way of talking about such things, compared to the constructively correct "it's not the case that the existence of X is always falsified".

It would be weird for a constructivist to be interested in a possible world that they don't believe exists.

Theoretically possible? Sure. But the kinds of questions that lead you there are generally in opposition to the kinds of principles that lead someone to prefer constructivism.