One of the participants in this dialogue seems too concerned with pinning down models uniquely and also seems too convinced he knows what model he’s in. Suppose we live in a simulation which is being run by superbeings who have access to oracles that can tell them when Turing machines are attempting to find contradictions in PA. Whenever they detect that something in the simulation is attempting to find contradictions in PA, that part of the simulation mysteriously stops working after the billionth or trillionth step or something. Then running such Turing machines can’t tell us whether we live in a universe where PA is consistent or not.
I also wish both participants in the dialogue would take ultrafinitism more seriously. It is not as wacky as it sounds, and it seems like a good idea to be conservative about such things when designing AI.
Edit: Here is an ultrafinitist fable that might be useful or at least amusing, from the link.
I have seen some ultrafinitists go so far as to challenge the existence of 2^100 as a natural number, in the sense of there being a series of ‘points’ of that length. There is the obvious ‘draw the line’ objection, asking where in 2^1, 2^2, 2^3, … , 2^100 do we stop having ‘Platonistic reality’? Here this … is totally innocent, in that it can be easily be replaced by 100 items (names) separated by commas. I raised just this objection with the (extreme) ultrafinitist Yesenin-Volpin during a lecture of his.
He asked me to be more specific. I then proceeded to start with 2^1 and asked him whether this is ‘real’ or something to that effect. He virtually immediately said yes. Then I asked about 2^2, and he again said yes, but with a perceptible delay. Then 2^3, and yes, but with more delay. This continued for a couple of more times, till it was obvious how he was handling this objection. Sure, he was prepared to always answer yes, but he was going to take 2^100 times as long to answer yes to 2^100 then he would to answering 2^1. There is no way that I could get very far with this.
… but since Qiaochu asked that we take ultrafinitism seriously, I’ll give a serious answer: something else will probably replace ultrafinitism as my preferred (maximum a posteriori) view of math and the world within 20 years or so. That is, I expect to determine that the question of whether ultrafinitism is true is not quite the right question to be asking, and have a better question by then, with a different best guess at the answer… just because similar changes of perspective have happened to me several times already in my life.
What precisely do the Overflowers (and the mathematician reporting that anecdote) mean by the “existence” of a number?
For instance, I see that the anecdote-reporter refers to there being a series of points of a particular length, but I assume they don’t mean that in an intuitive, literal sense: there are certainly at least 2^100 Planck lengths between me and the other end of the room.
I am not sure. If I tabooed “exist,” then my best guess is that ultrafinitists would argue that statements involving really big numbers are not meaningful. For example, they might argue that such statements are not verifiable in the real world. (Edit: as another example, as I mentioned in another comment, ultrafinitists might argue that you cannot count to really big numbers.)
For instance, I see that the anecdote-reporter refers to there being a series of points of a particular length, but I assume they don’t mean that in an intuitive, literal sense: there are certainly at least 2^100 Planck lengths between me and the other end of the room.
Yes, but just barely: 2^100 Planck lengths is something like 2 x 10^{-5} meters, so substitute 2^1000 Planck lengths, which is substantially larger than the diameter of the universe.
Seems weird to think that some of the possible configurations of bits on my 1.5TB hard drive don’t exist. Which ones? I hope none of the really good collections of pr0n are logically unreachable.
If that number does exist, then what about really big busy beaver numbers, like bb(2^10^13 )? They’re just a series of computations on hard drive contents. And that number is so close to infinity that we might as well just step from ultrafinitism to plain old finitism.
While I am not an ultrafinitist, I believe the idea is meant to be this: It is not valid to talk about those numbers, because there is no meaningful thing you can do with those numbers that can affect the real world. Therefore, the ultrafinitists say that it is not really logical to treat these numbers as “existing” as they can not affect the real world at all, and why say that something exists if it cannot affect anything at all?
Seems weird to think that some of the possible configurations of bits on my 1.5TB hard drive don’t exist.
Would you like to go through all of them just to be sure? How long do you think that will take you?
what about really big busy beaver numbers, like bb(2^10^13 )? They’re just a series of computations on hard drive contents.
Trying to actually compute a sufficiently large busy beaver number, you’ll run into the problem that there won’t be enough material in the observable universe to construct the corresponding Turing machines and/or that there won’t be enough usable energy to power them for the required lengths of time and/or that the heat death of the universe will occur before the required lengths of time. If there’s no physical way to go through the relevant computations, there’s no physical sense in which the relevant computations output a result.
It may not be possible to check all of them, but it certainly is possible to check one of them...any one of them. And whichever one you choose to check, you’ll find that it exists. So if you claim that some of the possible configurations don’t exist, you’re claiming they’d have to be among the ones you don’t choose to check. But wait, this implies that your choice of which one(s) to check somehow affects which ones exist. It sure would be spooky if that somehow turns out to be the case, which I doubt.
Exactly. And I could make my choice of which pr0n library to check—or which 1.5TB turing machine to run—dependent on 10^13 quantum coinflips; which, while it would take a while, seems physically realizable.
One of the participants in this dialogue … seems too convinced he knows what model he’s in.
I can imagine living a simulation… I just don’t understand yet what you mean by living in a model in the sense of logic and model theory, because a model is a static thing. I heard someone once before talk about “what are we in?”, as though the physical universe were a model, in the sense of model theory. He wasn’t able to operationalize what he meant by it, though. So, what do you mean when you say this? Are you considering the physical universe a first-order structure) somehow? If so, how? And concerning its role as a model, what formal system are you considering it a model of?
That was imprecise, but I was trying to comment on this part of the dialogue using the language that it had established:
Argh! No, damn it, I live in the set theory that really does have all the subsets, with no mysteriously missing subsets or mysterious extra numbers, or denumerable collections of all possible reals that could like totally map onto the integers if the mapping that did it hadn’t gone missing in the Australian outback -
I was also commenting on this part:
Screw set theory. I live in the physical universe where when you run a Turing machine, and keep watching forever in the physical universe, you never experience a time where that Turing machine outputs a proof of the inconsistency of Peano Arithmetic.
The point I was trying to make, and maybe I did not use sensible words to make it, is that This Guy (I don’t know what his name is—who writes a dialogue with unnamed participants, by the way?) doesn’t actually know that, for two reasons: first, Peano arithmetic might actually be inconsistent, and second, even if it were consistent, there might be some mysterious force preventing us from discovering this fact.
I just don’t understand yet what you mean by living in a model in the sense of logic and model theory, because a model is a static thing.
Models being static is a matter of interpretation. It is easy to write down a first-order theory of discrete dynamical systems (sets equipped with an endomap, interpreted as a successor map which describes the state of a dynamical system at time t + 1 given its state at time t). If time is discretized, our own universe could be such a thing, and even if it isn’t, cellular automata are such things. Are these “static” or “dynamic”?
Argh! No, damn it, I live in the set theory that really does have all the subsets, with no mysteriously missing subsets or mysterious extra numbers,
Indeed, I think it’s somewhat unclear what is meant here. The speaker attempts to relate it to physics, referring to the idea that we appear to live in continuous space… but how does the speaker propose to rule out infinitesimals and other nonstandard entities? (The speaker only seems to indicate horror about devils living in the cracks.) Or, for that matter, countable models of the reals, as someone already mentioned. This isn’t directly related to the question of what set theory is true, what set theory we live in, etc… (Perhaps the speaker’s intention in this line was to assume that we live in a Tegmark multiverse, so that we literally do live in some set theory?)
Instead, I think the speaker should have argued that we can refer to this state of affairs, not that it must be the true state of affairs. To give another example, I’m not at all convinced that time must correspond to the standard model of the natural numbers (I’m not even sure it doesn’t loop back upon itself eventually, when it comes down to it, though I agree that causal models disallow this and I find it improbable for that reason). Yet, I’m (relatively) happy to say that we can at least refer to this as a possible state of affairs. (Perhaps with a qualifier: “Unless peano arithmetic turns out to be inconsistent...”)
That was imprecise, but I was trying to comment on this part of the dialogue using the language that it had established
Ah, I was asking you because I thought using that language meant you’d made sense of it ;) The language of us “living in a (model of) set theory” is something I’ve heard before (not just from you and Eliezer), which made me think I was missing something. Us living in a dynamical system makes sense, and a dynamical system can contain a model of set theory, so at least we can “live with” models of set theory… we interact with (parts of) models of set theory when we play with collections of physical objects.
Models being static is a matter of interpretation.
Of course, time has been a fourth dimension for ages ;) My point is that set theory doesn’t seem to have a reasonable dynamical interpretation that we could live in, and I think I’ve concluded it’s confusing to talk like that. I can only make sense of “living with” or “believing in” models.
Set theory doesn’t have a dynamical interpretation because it’s not causal, but finite causal systems have first-order descriptions and infinite causal systems have second-order descriptions. Not everything logical is causal; everything causal is logical.
As a side note, I personally consider a theory “safe” if it fits with my intuitions and can be proved consistent using primitive recursive arithmetic and transfinite induction up to an ordinal I can picture. So I think of Peano arithmetic as safe, since I can picture epsilon-zero.
I think it’s more that an ultrafinitist claims not to know that successor is a total function—you could still induct for as long as succession lasts. Though this is me guessing, not something I’ve read.
Either that, or they claim that certain numbers, such as 3^^^3, cannot be reached by any number of iterations of the successor function starting from 0. It’s disprovable, but without induction or cut it’s too long a proof for any computer in the universe to do in a finite human lifespan, or even the earth’s lifespan.
Alternatively, one could start by asking whether 2^50 is a real number or not, if yes go up to 2^75, if no go to 2^25, and in up to 7 steps find a real number that, when doubled, ceases to be a real number. There may be impractical or even noncomputable numbers, but continuity holds that doubling a real number always yields a real number.
I think the point of the fable is that Yesenin-Volpin was counting to each number in his head before declaring whether it was ‘real’ or not, so if you asked him whether 2^50 was ‘real’ he’d just be quiet for a really really long time.
But wouldn’t that disprove ultrafinitism? All finite numbers, even 3^^^3, can be counted to (in the absence of any time limit, such as a lifespan), there’s just no human who really wants to.
If that’s true, then Yesenin-Volpin was just playin the role of a Turing machine trying to determine if a certain program halts (the program that counts from 0 to the input). If 3^^^3 (say) for a finitist doesn’t exists, then s/he really has a different concept of number than you have (for example, they are not axiomatized by the Peano Arithmetic). It’s fun to observe that ultrafinitism is axiomatic: if it’s a coherent point of view, it cannot prove that a certain number doesn’t exists, only assume it. I also suspect (but finite model theory is not my field at all) that they have an ‘inner’ model that mimics standard natural numbers...
Well, that’s what the anti-ultrafinitists say. It is precisely the contention of the ultrafinitists that you couldn’t “count to 3^^^3”, whatever that might mean.
So, it’s not sufficient to define a set of steps that determine a number… it must be possible to execute them? That’s a rather pragmatic approach. Albeit it one you’d have to keep updating if our power to compute and comprehend lengthier series of steps grows faster than you predict.
No, ultrafinitism is not a doctrine about our practical counting capacities. Ultrafinitism holds that you may not have actually denoted a number by ‘3^^^3’, because there is no such number.
I would have done the following if I had been asked that: calculate which numbers I would have time to count up to before I was thrown out/got bored/died/earth ended/universe ran out of negentropy. I would probably have to answer I don’t know, or I think X is a number for some of them, but it’s still an answer, and until recently people could not say wether “the smallest n>2 such that there are integers a,b,c satisfying a^n + b^n = c^n” was a number or not.
I’m not advocating any kind of finitism, but I agree that the position should be taken seriously.
One of the participants in this dialogue seems too concerned with pinning down models uniquely and also seems too convinced he knows what model he’s in. Suppose we live in a simulation which is being run by superbeings who have access to oracles that can tell them when Turing machines are attempting to find contradictions in PA. Whenever they detect that something in the simulation is attempting to find contradictions in PA, that part of the simulation mysteriously stops working after the billionth or trillionth step or something. Then running such Turing machines can’t tell us whether we live in a universe where PA is consistent or not.
I also wish both participants in the dialogue would take ultrafinitism more seriously. It is not as wacky as it sounds, and it seems like a good idea to be conservative about such things when designing AI.
Edit: Here is an ultrafinitist fable that might be useful or at least amusing, from the link.
For what it’s worth, I’m an ultrafinitist. Since 2005, at least as far as I’ve been able to tell.
How long do you expect to stay an ultrafinitist?
Until I’m destroyed, of course!
… but since Qiaochu asked that we take ultrafinitism seriously, I’ll give a serious answer: something else will probably replace ultrafinitism as my preferred (maximum a posteriori) view of math and the world within 20 years or so. That is, I expect to determine that the question of whether ultrafinitism is true is not quite the right question to be asking, and have a better question by then, with a different best guess at the answer… just because similar changes of perspective have happened to me several times already in my life.
Is that because 2005 is as far from the present time as you dare to go?
What precisely do the Overflowers (and the mathematician reporting that anecdote) mean by the “existence” of a number?
For instance, I see that the anecdote-reporter refers to there being a series of points of a particular length, but I assume they don’t mean that in an intuitive, literal sense: there are certainly at least 2^100 Planck lengths between me and the other end of the room.
I am not sure. If I tabooed “exist,” then my best guess is that ultrafinitists would argue that statements involving really big numbers are not meaningful. For example, they might argue that such statements are not verifiable in the real world. (Edit: as another example, as I mentioned in another comment, ultrafinitists might argue that you cannot count to really big numbers.)
Yes, but just barely: 2^100 Planck lengths is something like 2 x 10^{-5} meters, so substitute 2^1000 Planck lengths, which is substantially larger than the diameter of the universe.
Seems weird to think that some of the possible configurations of bits on my 1.5TB hard drive don’t exist. Which ones? I hope none of the really good collections of pr0n are logically unreachable.
If that number does exist, then what about really big busy beaver numbers, like bb(2^10^13 )? They’re just a series of computations on hard drive contents. And that number is so close to infinity that we might as well just step from ultrafinitism to plain old finitism.
While I am not an ultrafinitist, I believe the idea is meant to be this: It is not valid to talk about those numbers, because there is no meaningful thing you can do with those numbers that can affect the real world. Therefore, the ultrafinitists say that it is not really logical to treat these numbers as “existing” as they can not affect the real world at all, and why say that something exists if it cannot affect anything at all?
This seems incredibly likely, doesn’t it? (As long as we are happy to bound ‘logically reachable’ to within the observable universe.)
Would you like to go through all of them just to be sure? How long do you think that will take you?
Trying to actually compute a sufficiently large busy beaver number, you’ll run into the problem that there won’t be enough material in the observable universe to construct the corresponding Turing machines and/or that there won’t be enough usable energy to power them for the required lengths of time and/or that the heat death of the universe will occur before the required lengths of time. If there’s no physical way to go through the relevant computations, there’s no physical sense in which the relevant computations output a result.
It may not be possible to check all of them, but it certainly is possible to check one of them...any one of them. And whichever one you choose to check, you’ll find that it exists. So if you claim that some of the possible configurations don’t exist, you’re claiming they’d have to be among the ones you don’t choose to check. But wait, this implies that your choice of which one(s) to check somehow affects which ones exist. It sure would be spooky if that somehow turns out to be the case, which I doubt.
Exactly. And I could make my choice of which pr0n library to check—or which 1.5TB turing machine to run—dependent on 10^13 quantum coinflips; which, while it would take a while, seems physically realizable.
Help me out here…
I can imagine living a simulation… I just don’t understand yet what you mean by living in a model in the sense of logic and model theory, because a model is a static thing. I heard someone once before talk about “what are we in?”, as though the physical universe were a model, in the sense of model theory. He wasn’t able to operationalize what he meant by it, though. So, what do you mean when you say this? Are you considering the physical universe a first-order structure) somehow? If so, how? And concerning its role as a model, what formal system are you considering it a model of?
That was imprecise, but I was trying to comment on this part of the dialogue using the language that it had established:
I was also commenting on this part:
The point I was trying to make, and maybe I did not use sensible words to make it, is that This Guy (I don’t know what his name is—who writes a dialogue with unnamed participants, by the way?) doesn’t actually know that, for two reasons: first, Peano arithmetic might actually be inconsistent, and second, even if it were consistent, there might be some mysterious force preventing us from discovering this fact.
Models being static is a matter of interpretation. It is easy to write down a first-order theory of discrete dynamical systems (sets equipped with an endomap, interpreted as a successor map which describes the state of a dynamical system at time t + 1 given its state at time t). If time is discretized, our own universe could be such a thing, and even if it isn’t, cellular automata are such things. Are these “static” or “dynamic”?
Indeed, I think it’s somewhat unclear what is meant here. The speaker attempts to relate it to physics, referring to the idea that we appear to live in continuous space… but how does the speaker propose to rule out infinitesimals and other nonstandard entities? (The speaker only seems to indicate horror about devils living in the cracks.) Or, for that matter, countable models of the reals, as someone already mentioned. This isn’t directly related to the question of what set theory is true, what set theory we live in, etc… (Perhaps the speaker’s intention in this line was to assume that we live in a Tegmark multiverse, so that we literally do live in some set theory?)
Instead, I think the speaker should have argued that we can refer to this state of affairs, not that it must be the true state of affairs. To give another example, I’m not at all convinced that time must correspond to the standard model of the natural numbers (I’m not even sure it doesn’t loop back upon itself eventually, when it comes down to it, though I agree that causal models disallow this and I find it improbable for that reason). Yet, I’m (relatively) happy to say that we can at least refer to this as a possible state of affairs. (Perhaps with a qualifier: “Unless peano arithmetic turns out to be inconsistent...”)
Ah, I was asking you because I thought using that language meant you’d made sense of it ;) The language of us “living in a (model of) set theory” is something I’ve heard before (not just from you and Eliezer), which made me think I was missing something. Us living in a dynamical system makes sense, and a dynamical system can contain a model of set theory, so at least we can “live with” models of set theory… we interact with (parts of) models of set theory when we play with collections of physical objects.
Of course, time has been a fourth dimension for ages ;) My point is that set theory doesn’t seem to have a reasonable dynamical interpretation that we could live in, and I think I’ve concluded it’s confusing to talk like that. I can only make sense of “living with” or “believing in” models.
Set theory doesn’t have a dynamical interpretation because it’s not causal, but finite causal systems have first-order descriptions and infinite causal systems have second-order descriptions. Not everything logical is causal; everything causal is logical.
I like your proposal, but why not just standard finitism? What is your objection to primitive recursive arithmetic?
As a side note, I personally consider a theory “safe” if it fits with my intuitions and can be proved consistent using primitive recursive arithmetic and transfinite induction up to an ordinal I can picture. So I think of Peano arithmetic as safe, since I can picture epsilon-zero.
This isn’t my objection personally, but a sufficiently ultra finitist rejects the principle of induction.
I think it’s more that an ultrafinitist claims not to know that successor is a total function—you could still induct for as long as succession lasts. Though this is me guessing, not something I’ve read.
Either that, or they claim that certain numbers, such as 3^^^3, cannot be reached by any number of iterations of the successor function starting from 0. It’s disprovable, but without induction or cut it’s too long a proof for any computer in the universe to do in a finite human lifespan, or even the earth’s lifespan.
Alternatively, one could start by asking whether 2^50 is a real number or not, if yes go up to 2^75, if no go to 2^25, and in up to 7 steps find a real number that, when doubled, ceases to be a real number. There may be impractical or even noncomputable numbers, but continuity holds that doubling a real number always yields a real number.
I think the point of the fable is that Yesenin-Volpin was counting to each number in his head before declaring whether it was ‘real’ or not, so if you asked him whether 2^50 was ‘real’ he’d just be quiet for a really really long time.
But wouldn’t that disprove ultrafinitism? All finite numbers, even 3^^^3, can be counted to (in the absence of any time limit, such as a lifespan), there’s just no human who really wants to.
As I understand it, this is precisely the kind of statement that ultrafinitists do not believe.
If that’s true, then Yesenin-Volpin was just playin the role of a Turing machine trying to determine if a certain program halts (the program that counts from 0 to the input). If 3^^^3 (say) for a finitist doesn’t exists, then s/he really has a different concept of number than you have (for example, they are not axiomatized by the Peano Arithmetic). It’s fun to observe that ultrafinitism is axiomatic: if it’s a coherent point of view, it cannot prove that a certain number doesn’t exists, only assume it. I also suspect (but finite model theory is not my field at all) that they have an ‘inner’ model that mimics standard natural numbers...
Well, that’s what the anti-ultrafinitists say. It is precisely the contention of the ultrafinitists that you couldn’t “count to 3^^^3”, whatever that might mean.
Hmm.
So, it’s not sufficient to define a set of steps that determine a number… it must be possible to execute them? That’s a rather pragmatic approach. Albeit it one you’d have to keep updating if our power to compute and comprehend lengthier series of steps grows faster than you predict.
No, ultrafinitism is not a doctrine about our practical counting capacities. Ultrafinitism holds that you may not have actually denoted a number by ‘3^^^3’, because there is no such number.
Utlrafrinitists tend no to specfify the highest number, to prevent people adding one to it.
Hence “may not”
I would have done the following if I had been asked that: calculate which numbers I would have time to count up to before I was thrown out/got bored/died/earth ended/universe ran out of negentropy. I would probably have to answer I don’t know, or I think X is a number for some of them, but it’s still an answer, and until recently people could not say wether “the smallest n>2 such that there are integers a,b,c satisfying a^n + b^n = c^n” was a number or not.
I’m not advocating any kind of finitism, but I agree that the position should be taken seriously.