3 ms·

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 cle

by btilly 1y ago

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.

zozbot234 1y ago
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".
- btilly 1y ago
  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.
drdeca 1y ago
> 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.
- btilly 1y ago
  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.
  - drdeca 1y ago
    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.
    - btilly 1y ago
      > 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 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.
edanm 1y ago
> 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.
- zozbot234 1y ago
  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.
- btilly 1y ago
  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.

by btilly 1y ago

zozbot234 1y ago

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

btilly 1y ago
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.

drdeca 1y ago

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

btilly 1y ago
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.
- drdeca 1y ago
  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.
  - btilly 1y ago
    > 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 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.

edanm 1y ago

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

zozbot234 1y ago
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.
btilly 1y ago
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.