mattnewport: This would seem to put you in the opposite corner from Silas, who thinks (if I read him correctly) that all of physical reality is computably describable, and hence far simpler than arithmetic (in the sense of being describable using only a small and relatively simple fragment of arithmetic).
Be that as it may, I’ve blogged quite a bit about the nature of the complexity of arithmetic (see an old post called “Non-Simple Arithmetic” on my blog). In brief: a) no set of axioms suffices to specify the standard model of arithmetic (i.e. to distinguish it from other models). And b) we have the subjective reports of mathematicians about the complexity of their subject matter, which I think should be given at least as much weight as the subjective reports of ecologists. (There are a c), d) and e) as well, but in this short comment, I’ll rest my case here.)
Your biggest problem here, and in your blog posts, is that you equivocate between the structure of the standard natural numbers (N) and the theory of that structure (T(N), also known as True Arithmetic). The former is recursive and (a reasonable encoding of) it has pretty low Kolmogorov complexity. The latter is wildly nonrecursive and has infinite K-complexity. (See almost any of Chaitin’s work on algorithmic information theory, especially the Omega papers, for definitions of the K-complexity of a formal system.)
The difference between these two structures comes from the process of translating between them. Once explained properly, it’s almost intuitive to a recursion theorist, or a computer scientist versed in logic, that there’s a computable reduction from any language in the Arithmetic Hierarchy to the language of true statements of True Arithmetic. This implies that going from a description of N to a truth-enumerator or decision procedure for T(N) requires a hypercomputer with an infinite tower of halting, meta-halting, … meta^n-halting … oracles.
However, it so happens that simulating the physical world (or rather, our best physical ‘theories’, which in a mathematical sense are structures, not theories) on a Turing machine does not actually require T(N), only N. We only use theories, as opposed to models, of arithmetic, when we go to actually reason from our description of physics to consequences. And any such reasoning we actually do, just like any pure mathematical reasoning we do, depends only on a finite-complexity fragment of T(N).
Now, how does this make biology more complex than arithmetic? Well, to simulate any biological creature, you need N plus a bunch of biological information, which together has more K-complexity than just N. To REASON about the biological creature, at any particular level of enlightenment, requires some finite fragment of T(N), plus that extra biological information. To enumerate all true statements about the creature (including deeply-alternating quantified statements about its counterfactual behaviour in every possible circumstance), you require the infinite information in T(N), plus, again, that extra biological information. (In the last case it’s of course rather problematic to say there’s more complexity there, but there’s certainly at least as much.)
Note that I didn’t know all this this morning until I read your blog argument with Silas and Snorri; I thank all three of you for a discussion that greatly clarified my grasp on the levels of abstraction in play here.
(This morning I would have argued strongly against your Platonism as well; tonight I’m not so sure...)
Splat: Thanks for this; it’s enlightening and useful.
The part I’m not convinced of this:
to simulate any biological creature, you need N plus a bunch of biological information
A squirrel is a finite structure; it can be specified by a sequence of A’s, C’s, G’s and T’s, plus some rules for protein synthesis and a finite number of other facts about chemistry. (Or if you think that leaves something out, it can be described by the interactions among a large but finite collection of atoms.) So I don’t see where we need all of N to simulate a squirrel.
Well, if you need to simulate a squirrel for just a little while, and not for unbounded lengths of time, a substructure of N (without closure under the operations) or a structure with a considerable amount of sharing with N (like 64-bit integers on a computer) could suffice for your simulation.
The problem you encounter here is that these substructures and near-substructures, once they reach a certain size, actually require more information to specify than N itself. (How large this size is depends on which abstract computer you used to define your instance of K-complexity, but the asymptotic trend is unavoidable.)
If this seems paradoxical, consider that after a while the shortest computer program for generating an open initial segment of N is a computer program for generating all of N plus instructions indicating when to stop.
Either way, it so happens that the biological information you’d need to simulate the squirrel dwarfs N in complexity, so even if you can find a sufficient substitute for N that’s “lightweight” you can’t possibly save enough to make your squirrel simulation less complex than N.
The problem you encounter here is that these substructures and near-substructures, once they reach a certain size, actually require more information to specify than N itself.
This depends on what you mean by “specify”. To distinguish N from other mathematical structures requires either an infinite (indeed non-recursive) amount of information or a second order specification including some phrase like “all predicates”. Are you referring to the latter? Or to something else I don’t know about?
2) I do not know Chaitin’s definition of the K-complexity of a structure. I’ll try tracking it down, though if it’s easy for you to post a quick definition, I’ll be grateful. (I do think I know how to define the K-complexity of a theory.) I presume that if I knew this, I’d know your answer to question 1).
3) Whatever the definition, the question remains whether K-complexity is the right concept here. Dawkins’s argument does not define complexity; he treats it as “we know it when we see it”. My assertion has been that Dawkins’s argument applies in a context where it leads to an incorrect conclusion, and therefore can’t be right. To make this argument, I need to use Dawkins’s intended notion of complexity, which might not be the same as Chaitin’s or Kolmogorov’s. And for this, the best I can do is to infer from context what Dawkins does and does not see as complex. (It is, clear from context that he sees complexity as a general phenomenon, not just a biological one.)
4) The natural numbers are certainly an extremely complex structure in the everyday sense of the word; after thousands of years of study, people are learning new and surprising things about them every day, and there is no expectation that we’ve even scratched the surface. This is, of course, a manifestation of the “wildly nonrecursive” nature of T(N), all of which is reflected in N itself. And this, again, seems pretty close to the way Dawkins uses the word.
5) I continue to be most grateful for your input. I see that SIlas is back to insisting that you can’t simulate a squirrel with a simple list of axioms, after having been told forty eight bajillion times (here and elsewhere) that nobody’s asserting any such thing; my claim is that you can simulate a squirrel in the structure N, not in any particular axiomatic system. Whether or not you agree, it’s a pleasure to engage with someone who’s not obsessed with pummelling straw men.
2) A quick search of Google Scholar didn’t net me a Chaitin definition of K-complexity for a structure. This doesn’t surprise me much, as his uses of AIT in logic are much more oriented toward proof theory than model theory. Over here you can see some of the basic definitions. If you read page 7-10 and then my explanation to Silas here you can figure out what the K-complexity of a structure means. There’s also a definition of algorithmic complexity of a theory in section 3 of the Chaitin.
According to these definitions, the complexity of N is about a few hundred bits for reasonable choices of machine, and the complexity of T(N) is &infty;.
1) It actually is pretty hard to characterize N extrinsically/intensionally; to characterize it with first-order statements takes infinite information (as above). The second-order characterization. by contrast, is a little hard to interpret. It takes a finite amount of information to pin down the model[*][PA2], but the second-order theory PA2 still has infinite K-complexity because of its lack of complete rules of inference.
Intrinsic/extensional characterizations, on the other hand, are simple to do, as referenced above. Really, Gödel Incompleteness wouldn’t be all that shocking in the first place if we couldn’t specify N any other way than its first-order theory! Interesting, yes, shocking, no. The real scandal of incompleteness is that you can so simply come up with a procedure for listing all the ground (quantifier-free) truths of arithmetic and yet passing either to or from the kind of generalizations that mathematicians would like to make is fraught with literally infinite peril.
3&4) Actually I don’t think that Dawkins is talking about K-complexity, exactly. If that’s all you’re talking about, after all, an equal-weight puddle of boiling water has more K-complexity than a squirrel does. I think there’s a more involved, composite notion at work that builds on K-complexity and which has so far resisted full formalization. Something like this, I’d venture.
The complexity of the natural numbers as a subject of mathematical study, while certainly well-attested, seems to be of a different sense than either K-complexity or the above. Further, it’s unclear whether we should really be placing the onus of this complexity on N, on the semantics of quantification in infinite models (which N just happens to bring out), or on the properties of computation in general. In the latter case, some would say the root of the complexity lies in physics.
Also, I very much doubt that he had in mind mathematical structures as things that “exist”. Whether it turns out that the difference in the way we experience abstractions like the natural numbers and concrete physical objects like squirrels is fundamental, as many would have it, or merely a matter of our perspective from within our singular mathematical context, as you among others suspect, it’s clear that there is some perceptible difference involved. It doesn’t seem entirely fair to press the point this much without acknowledging the unresolved difference in ontology as the main point of conflict.
Trying to quantify which thing is more complex is really kind of a sideshow, although an interesting one. If one forces both senses of complexity into the K-complexity box then Dawkins “wins”, at the expense of both of your being turned into straw men. If one goes by what you both really mean, though, I think the complexity is probably incommensurable (no common definition or scale) and the comparison is off-point.
5) Thank you. I hope the discussion here continues to grow more constructive and helpful for all involved.
Thanks again for bringing insight and sanity to this discussion. A few points:
1) Your description of the structure N presupposes some knowledge of the structure N; the program that prints out the structure needs a first statement, a second statement, etc. This is, of course, unavoidable, and it’s therefore not a complaint; I doubt that there’s any way to give a formal description of the natural numbers without presupposing some informal understanding of the natural numbers. But what it does mean, I think, is that K-complexity (in the sense that you’re using it) is surely the wrong measure of complexity here—because when you say that N has low K-complexity, what you’re really saying is that “N is easy to describe provided you already know something about N”. What we really want to know is how much complexity is imbedded in that prior knowledge.
1A) On the other hand, I’m not clear on how much of the structure of N is necessarily assumed in any formal description, so my point 1) might be weaker than I’ve made it out to be.
2) It has been my position all along that K-complexity is largely a red herring here in the sense that it need not capture Dawkins’s meaning. Your observation that a pot of boiling water is more K-complex than a squirrel speaks directly to this point, and I will probably steal it for use in future discussions.
3) When you talk about T(N), I presume you mean the language of Peano arithmetic, together with the set of all true statements in that language. (Correct me if I’m wrong.) I would hesitate to call this a theory, because it’s not recursively axiomatizable, but that’s a quibble. In any event, we do know what we mean by T(N), but we don’t know what we mean by T(squirrel) until we specify a language for talking about squirrels—a set of constant symbols corresponding to tail, head, etc., or one for each atom, or....., and various relations, etc. So T(N) is well defined, while T(squirrel) is not. But whatever language you settle on, a squirrel is still going to be a finite structure, so T(squirrel) is not going to share the “wild nonrecursiveness” of T(N) (which is closely related to the difficulty of giving an extrinsic characterization). That seems to me to capture a large part of the intuition that the natural numbers are more complex than a squirrel,
4) You are probably right that Dawkins wasn’t thinking about mathematical structures when he made his argument. But because he does claim that his argument applies to complexity in general, not just to specific instances, he’s stuck (I think) either accepting applications he hadn’t thought about or backing off the generality of his claim. It’s of course hard to know exactly what he meant by complexity, but it’s hard for me to imagine any possible meaning consistent with Dawkins’s usage that doesn’t make arithmetic (literally) infinitely more complex than a squirrel.
5) Thanks for trying to explain to Silas that he doesn’t understand the difference between a structure and an axiomatic system. I’ve tried explaining it to him in many ways, at many times, in many forums, but have failed to make any headway. Maybe you’ll have better luck.
6) If any of this seems wrong to you, I’ll be glad to be set straight.
Whatever the definition, the question remains whether K-complexity is the right concept here. Dawkins’s argument does not define complexity; he treats it as “we know it when we see it”. My assertion has been that Dawkins’s argument applies in a context where it leads to an incorrect conclusion, and therefore can’t be right. To make this argument, I need to use Dawkins’s intended notion of complexity, which might not be the same as Chaitin’s or Kolmogorov’s. And for this, the best I can do is to infer from context what Dawkins does and does not see as complex.
1) Unless they say otherwise, you should assume someone is using the standard meanings for the terms they use, which would mean Dawkins is using the intuitive definition, which closely parallels K-complexity.
2) If you’re going to write a book hundreds of pages long in which you crucially rely on the concept of complexity, you need to explicitly to define it. That’s just how it works. If you know what concept of complexity is “the” right one here, you need to spell it out yourself.
3) Most importantly, you have shown Dawkins’s argument to be in error in the context of an immaterial realm that is not observable and does not interact with this universe. Surely, you can think of some reason why Dawkins doesn’t intend to refer to such realms, can’t you? (Hint: Dawkins is an atheist, materialist, and naturalist—just like you, in other words, until it comes to the issue of math.)
ETA: If any followers of this exchange think I’m somehow not getting someting, or being unfair to SteveLandsburg, please let me know, either as a reply in the thread or a PM, whether or not you use your normal handle.
If you’re going to write a book hundreds of pages long in which you crucially rely on the concept of complexity, you need to explicitly to define it. That’s just how it works. If you know what concept of complexity is “the” right one here, you need to spell it out yourself.
Well, Silas, what I actually did was write a book 255 pages long of which this whole Dawkins/complexity thing occupies about five pages (29-34) and where complexity is touched on exactly once more, in a brief passage on pages 7-8. From the discrepancy between your description and reality, I infer that you haven’t read the book, which would help to explain why your comments are so bizarrely misdirected.
Oh, and I see that you’re still going on about axiomatic descriptions of squirrels, as if that were relevant to something I’d said. (Hint: A simulation is not an axiomatic system. That’s 48 bajillion and one.)
Well, Silas, what I actually did was write a book 255 pages long of which this whole Dawkins/complexity thing occupies about five pages (29-34) and where complexity is touched on exactly once more, in a brief passage on pages 7-8. From the discrepancy between your description and reality, I infer that you haven’t read the book, which would help to explain why your comments are so bizarrely misdirected.
I have not read the entire book. I have read many long portions of it, mostly the philosophical ones and those dealing with physics. I was drawn to on the assumption that, surely you would have defined complexity in your exposition!
It’s misleading to say that your usage of complexity only takes 8 pages, so it’s insignificant. Rather, the point you make about complexity is your grounding for broader claims about the role mathematics plays in the universe, which you come back to frequently. The explicit mention of the term “complexity” is thus a poor measure of how much you rely on it.
But even if it were just 8 pages, you should still have defined it, and you should still not expect to have achieved insights on the topic, given that you haven’t defined it.
(I certainly wouldn’t want to buy it—why should I subsidize such confused thinking? I don’t even like your defenses of libertarianism, despite being libertarian.)
Oh, and I see that you’re still going on about axiomatic descriptions of squirrels, as if that were relevant to something I’d said. (Hint: A simulation is not an axiomatic system. That’s 48 bajillion and one.)
Ah, another suddenly-crucial distinction to make, so you can wiggle out of being wrong!
I should probably use this opportunity to both show I did read many portions, and show why Landsburg doesn’t get what it means to really explain something. His explanation of the Heisenberg Uncertainty Principle (which gets widely praised as a good explanation for some reason) is this: think of an electron as moving in a circle within a square. If you measure its vertical position, its closeness to the top determines the chance of getting a “top” or “bottom” reading.
Likewise the horizontal direction: if you measure the horizontal position of the electron, your chances of getting a “left” or “right” reading depends on how far it is from that side.
And for the important part: why can’t you measure both at the same time? Landsburg’s brilliant explanation: um, because you can’t.
But that’s what the explanation was supposed to demystify in the first place! You can’t demystify by feeding that very mystery a blackbox fact unto itself. To explain it, you would need to explain enough of the dynamics of quantum systems so that, at the end, your reader doesn’t view precise measurement of both position and momentum as even being coherent! Saying, “oh, you can’t because you can’t” isn’t an explanation.
I see that SIlas is back to insisting that you can’t simulate a squirrel with a simple list of axioms, after having been told forty eight bajillion times (here and elsewhere) that nobody’s asserting any such thing;
I didn’t say that. Read it again. I said that there is some finite axiom list that can describe squirrels, but it’s not just the axioms that suffice to let you use arithmetic. It’s those, plus biological information about squirrels. But this arithmetic is not the infinitely complex arithmetic you talk about in other contexts!
my claim is that you can simulate a squirrel in the structure N, not in any particular axiomatic system.
You can’t—you need axioms beyond those that specify N. The fact that the biological model involving those axioms uses math, doesn’t mean you’ve described it once you’ve described the structure N. So whether or not you call that “simulating it in the structure N”, it’s certainly more complex than just N.
I’m responding here to your invitation in the parent, since this post provides some good examples of what you’re not getting.
I didn’t say that. Read it again. I said that there is some finite axiom list that can describe squirrels, but it’s not just the axioms that suffice to let you use arithmetic.
Simulating squirrels and using arithmetic require information, but that information is not supplied in the form of axioms. The best way to imagine this in the case of arithmetic is in terms of a structure.
Starting from the definition in that wikipedia page, you can imagine giving the graphs of the universe and functions and relations as Datalog terms. (Using terms instead of tuples keeps the graphs disjoint, which will be important later.) Like so:
Then you use some simple recursive coding of datalog terms as binary. What you’re left with is just a big (infinite) set of binary strings. The Kolmogorov complexity of the structure N, then (the thing you need to use arithmetic) is the size of the shortest program that enumerates the set, which is actually very small.
Note that this is actually the same arithmetic that Steve is talking about! It is just a different level of description, one that is much simpler but entirely sufficient to conduct simulations with. It is only in understanding the long-term behavior of simulations without running them that one requires any of the extra complexity embodied in T(N) (the theory). To actually run them you just need N (the structure).
The fact that you don’t seem to understand this point yet leads me to believe you were being a little unfair when you said:
By the way, I really hope your remark about Splat’s comment being “enlightening” was just politeness, and that you didn’t actually mean it. Because if you did, that would mean you’re just now learning the distinction between N and T(N), the equivocation between which undermines your claims about arithmetic’s relation to the universe.
Now, if you want to complete the comparison, imagine you’re creating a structure that includes a universe with squirrel-states and times, and a function from time to squirrel state. This would look something like:
The squirrel states, though, will not be described by a couple of words like that, but by incredibly detailed descriptions of the squirrel’s internal state—what shape all its cells are, where all the mRNAs are on their way to the ribosomes, etc. The structure you come up with will take a much bigger program to enumerate than N will. (And I know you already agree with the conclusion here, but making the correct parallel matters.)
Simulating squirrels and using arithmetic require information, but that information is not supplied in the form of axioms.
I wasn’t careful to distinguish axioms from other kinds of information in the model, and I think it’s a distraction to do so because it’s just an issue of labels (which as you probably saw from the discussion is a major source of confusion). My focus was on tabulating the total complexity of whatever-is-being-claimed-is-significant. For that, you only need to count up how much information goes into your “message” describing the data (in the “Minimum Message Length criterion” sense of “message”). Anything in such a message can be described without loss of generality as an axiom.
If I want to describe squirrels, I will find, like most scientists find, that the job is much easier of I can express things using arithmetic. Arithmetic is so helpful that, even after accounting for the cost of telling you how to use it (the axioms-or-whatever of math), I still save in total message length. Whether you call the squirrel info I gathered from nature, or the specification of math, the “axioms” doesn’t matter.
...which is actually very small. Note that this is actually the same arithmetic that Steve is talking about! It is just a different level of description, one that is much simpler but entirely sufficient to conduct simulations with. It is only in understanding the long-term behavior of simulations without running them that one requires any of the extra complexity embodied in T(N) (the theory). …
But it’s not the same arithmetic SteveLandsburg is talking about, if you follow through to the implications he claims fall out from it. He claims arithmetic—the infinitely complex one—runs the universe. It doesn’t. The universe only requires the short message specifying N, plus the (finite) particulars of the universe. Whatever infinitely-complex thing he’s talking about from a “different level of description” isn’t the same thing, and can’t be the same thing.
What’s more, the universe can’t contain that thing because there is no (computable) isomorphism between it and the universe. As we derive the results of longer and longer chains of reasoning, our universe starts to contain more and more complex pieces of that thing, but it still wouldn’t be somehow fundamental to the universe’s operation—not if we’re just now getting to contain pieces of it.
The fact that you don’t seem to understand this point yet leads me to believe you were being a little unfair when you said: … Now, if you want to complete the comparison, imagine you’re creating a structure that includes a universe with squirrel-states and times, and a function from time to squirrel state. This would look something like: … The squirrel states, though, will not be described by a couple of words like that,
I’m sorry, I don’t see how that contradicts what I said or shows a different parallel. Now, I certainly didn’t use the N vs. T(N) terminology you did, but I clearly explained how there have to be two separate “arithmetics” in play here, as best summarized in my comment here. Whatever infinitely complex arithmetic SteveLandsburg is talking about, isn’t the one that runs the universe. The insights on one don’t apply to the other.
Okay, pretend I’ve given you the axioms sufficient for you to +-*/. Can simulate squirrels now? Of course not. You still have to go out and collect information about squirrels and add it to your description of the axioms of arithmetic (which suffice for all of N) to have a description of squirrels.
You claim that because you can simulate squirrels with (a part of) N, then N suffices to simulate squirrels. But this is like saying that, because you know the encoding method your friend uses to send you messages, you must know the content of all future messages.
That’s wrong, because those are different parts of the compressed data: one part tells you how to decompress, another tells you what you’re decompressing. Knowing how to decompress (i.e., the axioms of N) is different from knowing the string to be decompressed by that method (i.e. the arithmetic symbols encoding squirrels).
By the way, I really hope your remark about Splat’s comment being “enlightening” was just politeness, and that you didn’t actually mean it. Because if you did, that would mean you’re just now learning the distinction between N and T(N), the equivocation between which undermines your claims about arithmetic’s relation to the universe.
And much of his comment was a restatement of my point about the difference between the complex arithmetic you refer to, and the arithmetic the universe actually runs on. (I’m not holding my breath for a retraction or a mea culpa or anything, just letting people know what they’re up against here.)
b) we have the subjective reports of mathematicians about the complexity of their subject matter, which I think should be given at least as much weight as the subjective reports of ecologists
Again, this word complexity is used in many ways. Complexity in the sense of humans find this complicatedis a different concept from complexity in the sense of Kolmogorov complexity.
Don’t worry guys, I didn’t let you down. I addressed the issue from the perspective of Kolmogorv complexity in my first blog response. Landsburg initially replied with (I’m paraphrasing), “so what if you became an expert on information theory? That’s not the only meaning of complexity.”
Only later did he try to claim that he also meets the Kolmogorov definition.
(And FWIW, I’m not an expert on information theory—it’s just a hobby. I guess my knowledge just looked impressive to someone...)
no set of axioms suffices to specify the standard model of arithmetic (i.e. to distinguish it from other models).
Then what do you mean when you say “integers”^H^H “natural numbers”, if no set of premises suffices to talk about it as opposed to something else?
Anyway, no countable set of first-order axioms works. But a finite set of second-order axioms work. So to talk about the natural numbers, it suffices merely to think that when you say “Any predicate that is true of zero, and is true of the successor of every number it is true of, is true of all natural numbers” you made sense when you said “any predicate”.
It is this sort of minor-seeming yet important technical inaccuracy that separates “The Big Questions” from “Good and Real”, I’m afraid.
Anyway, no countable set of first-order axioms works. But a finite set of second-order axioms work. So to talk about the integers, it suffices merely to think that when you say “Any predicate that is true of zero, and is true of the successor of every number it is true of, is true of all integers” you made sense when you said “any predicate”.
I think that you have to be careful about claims that second-order logic fixes a unique model. Granted, you can derive the statement “There exists a unique model of the axioms of arithmetic.”
But, for example, what in reality does your “any predicate” quantifier range over? If, under interpretation, it ranges over subsets of the domain of discourse, well, what exactly constitutes a subset? This presumes that you have a model of some set theory in hand. How do you specify which model of set theory you’re using? So far as I know, there’s no way out of this regress.
[ETA: I’m not a logician. I’m definitely open to correction here.]
[ETA2: And now that I read more carefully, you were acknowledging this point when you wrote, “it suffices merely to think that . . . you made sense when you said ‘any predicate’.”
However, you didn’t acknowledge this issue in your earlier comment. I think that it’s too significant an issue to be dismissed with an “it suffices merely...”. When an infinite regress threatens, it doesn’t suffice to push the issue back a level and say “it suffices merely to show that that’s the last level.”]
Sure, and that’s the age-old argument for why we should not take second-order logic at face value. But in this case we cannot go around blithely talking about the integers for there is no language we could use to speak of them, or any other infinite set. We would be forbidden of saying that there is something we cannot talk about, and this is not surprising—what is it you can’t refer to?
Sure, and that’s the age-old argument for why we should not take second-order logic at face value.
I’m not familiar with the literature of this argument. (It was probably clear from the tentativeness of my comment that I was thinking my own murky way through this issue.)
You seem to take it as the default that we should take second-order logic at face value. (Now that I know what you mean by “face value”, I see that you did acknowledge this issue in your earlier comment.) But I should think that the default would be to be skeptical about this. Why expect that we have a canonical model when we talk about sets or predicates if we’re entertaining skepticism that we have a canonical model for integer-talk?
Why expect that we have a canonical model when we talk about sets or predicates if we’re entertaining skepticism that we have a canonical model for integer-talk?
We don’t. Skepticism of sets, predicates, and canonical integers are all the same position in the debate.
And so is skepticism of canonical Turing machines, as far as I can tell. Specifically, skepticism that there is always a fact of the matter as to whether a given TM halts.
I think you might be able to make the skeptical position precise by constructing nonstandard variants of TMs where the time steps and tape squares are numbered with nonstandard naturals, and the number of symbols and states are also nonstandard, and you would be able to relate these back to the nonstandard models that produced them by using a recursive description of N to regenerate the nonstandard model of the natural numbers you started with. This would show that there are nonstandard variants of computability that all believe in different ‘standard’, ‘minimal’ models of arithmetic, and are unaware of the existence of smaller models, and thus presumably of the ‘weaker’ (because they halt less often) notions of Turing Machines.
Now, I’m not yet sure if this construction goes through as I described it; for me, if it does it weighs against the existence of a ‘true’ Standard Model and if it doesn’t it weighs in favor.
It is in fact provably impossible to construct a computable nonstandard model (where, say, S and +, or S and × are both computable relations) in a standard model of computation. What I was referring to was a nonstandard model that was computable according to an equally nonstandard definition of computation, one that makes explicit the definitional dependence of Turing Machines on the standard natural numbers and replaces them with nonstandard ones.
The question I’m wondering about is whether such a definition leads to a sensible theory of computation (at least on its own terms) or whether it turns out to just be nonsense. This may have been addressed in the literature but if so it’s beyond the level to which I’ve read so far.
It is in fact provably impossible to construct a computable nonstandard model (where, say, S and +, or S and × are both computable relations) in a standard model of computation.
Would you give a reference? I found it easy to find assertions such as “the completeness theorem is not constructively provable,” but this statement is a little stronger.
But in this case we cannot go around blithely talking about the integers for there is no language we could use to speak of them, or any other infinite set. We would be forbidden of saying that there is something we cannot talk about, and this is not surprising—what is it you can’t refer to?
I believe that this claim is based on a defective notion of what it takes to refer to something successfully. The issue that we’re talking about here is a manifestation of that defect. I’m trying to work out a different conception of reference, but it’s very much a work in progress.
mattnewport: This would seem to put you in the opposite corner from Silas, who thinks (if I read him correctly) that all of physical reality is computably describable
No, it wouldn’t—he’s saying basically the same thing I did. The laws of physics are computable. In describing observations, we use concepts from math. The reason we do so is that it allows simpler descriptions of the universe.
mattnewport: This would seem to put you in the opposite corner from Silas, who thinks (if I read him correctly) that all of physical reality is computably describable, and hence far simpler than arithmetic (in the sense of being describable using only a small and relatively simple fragment of arithmetic).
Be that as it may, I’ve blogged quite a bit about the nature of the complexity of arithmetic (see an old post called “Non-Simple Arithmetic” on my blog). In brief: a) no set of axioms suffices to specify the standard model of arithmetic (i.e. to distinguish it from other models). And b) we have the subjective reports of mathematicians about the complexity of their subject matter, which I think should be given at least as much weight as the subjective reports of ecologists. (There are a c), d) and e) as well, but in this short comment, I’ll rest my case here.)
Your biggest problem here, and in your blog posts, is that you equivocate between the structure of the standard natural numbers (N) and the theory of that structure (T(N), also known as True Arithmetic). The former is recursive and (a reasonable encoding of) it has pretty low Kolmogorov complexity. The latter is wildly nonrecursive and has infinite K-complexity. (See almost any of Chaitin’s work on algorithmic information theory, especially the Omega papers, for definitions of the K-complexity of a formal system.)
The difference between these two structures comes from the process of translating between them. Once explained properly, it’s almost intuitive to a recursion theorist, or a computer scientist versed in logic, that there’s a computable reduction from any language in the Arithmetic Hierarchy to the language of true statements of True Arithmetic. This implies that going from a description of N to a truth-enumerator or decision procedure for T(N) requires a hypercomputer with an infinite tower of halting, meta-halting, … meta^n-halting … oracles.
However, it so happens that simulating the physical world (or rather, our best physical ‘theories’, which in a mathematical sense are structures, not theories) on a Turing machine does not actually require T(N), only N. We only use theories, as opposed to models, of arithmetic, when we go to actually reason from our description of physics to consequences. And any such reasoning we actually do, just like any pure mathematical reasoning we do, depends only on a finite-complexity fragment of T(N).
Now, how does this make biology more complex than arithmetic? Well, to simulate any biological creature, you need N plus a bunch of biological information, which together has more K-complexity than just N. To REASON about the biological creature, at any particular level of enlightenment, requires some finite fragment of T(N), plus that extra biological information. To enumerate all true statements about the creature (including deeply-alternating quantified statements about its counterfactual behaviour in every possible circumstance), you require the infinite information in T(N), plus, again, that extra biological information. (In the last case it’s of course rather problematic to say there’s more complexity there, but there’s certainly at least as much.)
Note that I didn’t know all this this morning until I read your blog argument with Silas and Snorri; I thank all three of you for a discussion that greatly clarified my grasp on the levels of abstraction in play here.
(This morning I would have argued strongly against your Platonism as well; tonight I’m not so sure...)
Splat: Thanks for this; it’s enlightening and useful.
The part I’m not convinced of this:
A squirrel is a finite structure; it can be specified by a sequence of A’s, C’s, G’s and T’s, plus some rules for protein synthesis and a finite number of other facts about chemistry. (Or if you think that leaves something out, it can be described by the interactions among a large but finite collection of atoms.) So I don’t see where we need all of N to simulate a squirrel.
Well, if you need to simulate a squirrel for just a little while, and not for unbounded lengths of time, a substructure of N (without closure under the operations) or a structure with a considerable amount of sharing with N (like 64-bit integers on a computer) could suffice for your simulation.
The problem you encounter here is that these substructures and near-substructures, once they reach a certain size, actually require more information to specify than N itself. (How large this size is depends on which abstract computer you used to define your instance of K-complexity, but the asymptotic trend is unavoidable.)
If this seems paradoxical, consider that after a while the shortest computer program for generating an open initial segment of N is a computer program for generating all of N plus instructions indicating when to stop.
Either way, it so happens that the biological information you’d need to simulate the squirrel dwarfs N in complexity, so even if you can find a sufficient substitute for N that’s “lightweight” you can’t possibly save enough to make your squirrel simulation less complex than N.
Splat:
1)
This depends on what you mean by “specify”. To distinguish N from other mathematical structures requires either an infinite (indeed non-recursive) amount of information or a second order specification including some phrase like “all predicates”. Are you referring to the latter? Or to something else I don’t know about?
2) I do not know Chaitin’s definition of the K-complexity of a structure. I’ll try tracking it down, though if it’s easy for you to post a quick definition, I’ll be grateful. (I do think I know how to define the K-complexity of a theory.) I presume that if I knew this, I’d know your answer to question 1).
3) Whatever the definition, the question remains whether K-complexity is the right concept here. Dawkins’s argument does not define complexity; he treats it as “we know it when we see it”. My assertion has been that Dawkins’s argument applies in a context where it leads to an incorrect conclusion, and therefore can’t be right. To make this argument, I need to use Dawkins’s intended notion of complexity, which might not be the same as Chaitin’s or Kolmogorov’s. And for this, the best I can do is to infer from context what Dawkins does and does not see as complex. (It is, clear from context that he sees complexity as a general phenomenon, not just a biological one.)
4) The natural numbers are certainly an extremely complex structure in the everyday sense of the word; after thousands of years of study, people are learning new and surprising things about them every day, and there is no expectation that we’ve even scratched the surface. This is, of course, a manifestation of the “wildly nonrecursive” nature of T(N), all of which is reflected in N itself. And this, again, seems pretty close to the way Dawkins uses the word.
5) I continue to be most grateful for your input. I see that SIlas is back to insisting that you can’t simulate a squirrel with a simple list of axioms, after having been told forty eight bajillion times (here and elsewhere) that nobody’s asserting any such thing; my claim is that you can simulate a squirrel in the structure N, not in any particular axiomatic system. Whether or not you agree, it’s a pleasure to engage with someone who’s not obsessed with pummelling straw men.
Replying out of order:
2) A quick search of Google Scholar didn’t net me a Chaitin definition of K-complexity for a structure. This doesn’t surprise me much, as his uses of AIT in logic are much more oriented toward proof theory than model theory. Over here you can see some of the basic definitions. If you read page 7-10 and then my explanation to Silas here you can figure out what the K-complexity of a structure means. There’s also a definition of algorithmic complexity of a theory in section 3 of the Chaitin.
According to these definitions, the complexity of N is about a few hundred bits for reasonable choices of machine, and the complexity of T(N) is &infty;.
1) It actually is pretty hard to characterize N extrinsically/intensionally; to characterize it with first-order statements takes infinite information (as above). The second-order characterization. by contrast, is a little hard to interpret. It takes a finite amount of information to pin down the model[*][PA2], but the second-order theory PA2 still has infinite K-complexity because of its lack of complete rules of inference.
Intrinsic/extensional characterizations, on the other hand, are simple to do, as referenced above. Really, Gödel Incompleteness wouldn’t be all that shocking in the first place if we couldn’t specify N any other way than its first-order theory! Interesting, yes, shocking, no. The real scandal of incompleteness is that you can so simply come up with a procedure for listing all the ground (quantifier-free) truths of arithmetic and yet passing either to or from the kind of generalizations that mathematicians would like to make is fraught with literally infinite peril.
3&4) Actually I don’t think that Dawkins is talking about K-complexity, exactly. If that’s all you’re talking about, after all, an equal-weight puddle of boiling water has more K-complexity than a squirrel does. I think there’s a more involved, composite notion at work that builds on K-complexity and which has so far resisted full formalization. Something like this, I’d venture.
The complexity of the natural numbers as a subject of mathematical study, while certainly well-attested, seems to be of a different sense than either K-complexity or the above. Further, it’s unclear whether we should really be placing the onus of this complexity on N, on the semantics of quantification in infinite models (which N just happens to bring out), or on the properties of computation in general. In the latter case, some would say the root of the complexity lies in physics.
Also, I very much doubt that he had in mind mathematical structures as things that “exist”. Whether it turns out that the difference in the way we experience abstractions like the natural numbers and concrete physical objects like squirrels is fundamental, as many would have it, or merely a matter of our perspective from within our singular mathematical context, as you among others suspect, it’s clear that there is some perceptible difference involved. It doesn’t seem entirely fair to press the point this much without acknowledging the unresolved difference in ontology as the main point of conflict.
Trying to quantify which thing is more complex is really kind of a sideshow, although an interesting one. If one forces both senses of complexity into the K-complexity box then Dawkins “wins”, at the expense of both of your being turned into straw men. If one goes by what you both really mean, though, I think the complexity is probably incommensurable (no common definition or scale) and the comparison is off-point.
5) Thank you. I hope the discussion here continues to grow more constructive and helpful for all involved.
Relevant link: http://lesswrong.com/lw/vh/complexity_and_intelligence/
Splat:
Thanks again for bringing insight and sanity to this discussion. A few points:
1) Your description of the structure N presupposes some knowledge of the structure N; the program that prints out the structure needs a first statement, a second statement, etc. This is, of course, unavoidable, and it’s therefore not a complaint; I doubt that there’s any way to give a formal description of the natural numbers without presupposing some informal understanding of the natural numbers. But what it does mean, I think, is that K-complexity (in the sense that you’re using it) is surely the wrong measure of complexity here—because when you say that N has low K-complexity, what you’re really saying is that “N is easy to describe provided you already know something about N”. What we really want to know is how much complexity is imbedded in that prior knowledge.
1A) On the other hand, I’m not clear on how much of the structure of N is necessarily assumed in any formal description, so my point 1) might be weaker than I’ve made it out to be.
2) It has been my position all along that K-complexity is largely a red herring here in the sense that it need not capture Dawkins’s meaning. Your observation that a pot of boiling water is more K-complex than a squirrel speaks directly to this point, and I will probably steal it for use in future discussions.
3) When you talk about T(N), I presume you mean the language of Peano arithmetic, together with the set of all true statements in that language. (Correct me if I’m wrong.) I would hesitate to call this a theory, because it’s not recursively axiomatizable, but that’s a quibble. In any event, we do know what we mean by T(N), but we don’t know what we mean by T(squirrel) until we specify a language for talking about squirrels—a set of constant symbols corresponding to tail, head, etc., or one for each atom, or....., and various relations, etc. So T(N) is well defined, while T(squirrel) is not. But whatever language you settle on, a squirrel is still going to be a finite structure, so T(squirrel) is not going to share the “wild nonrecursiveness” of T(N) (which is closely related to the difficulty of giving an extrinsic characterization). That seems to me to capture a large part of the intuition that the natural numbers are more complex than a squirrel,
4) You are probably right that Dawkins wasn’t thinking about mathematical structures when he made his argument. But because he does claim that his argument applies to complexity in general, not just to specific instances, he’s stuck (I think) either accepting applications he hadn’t thought about or backing off the generality of his claim. It’s of course hard to know exactly what he meant by complexity, but it’s hard for me to imagine any possible meaning consistent with Dawkins’s usage that doesn’t make arithmetic (literally) infinitely more complex than a squirrel.
5) Thanks for trying to explain to Silas that he doesn’t understand the difference between a structure and an axiomatic system. I’ve tried explaining it to him in many ways, at many times, in many forums, but have failed to make any headway. Maybe you’ll have better luck.
6) If any of this seems wrong to you, I’ll be glad to be set straight.
1) Unless they say otherwise, you should assume someone is using the standard meanings for the terms they use, which would mean Dawkins is using the intuitive definition, which closely parallels K-complexity.
2) If you’re going to write a book hundreds of pages long in which you crucially rely on the concept of complexity, you need to explicitly to define it. That’s just how it works. If you know what concept of complexity is “the” right one here, you need to spell it out yourself.
3) Most importantly, you have shown Dawkins’s argument to be in error in the context of an immaterial realm that is not observable and does not interact with this universe. Surely, you can think of some reason why Dawkins doesn’t intend to refer to such realms, can’t you? (Hint: Dawkins is an atheist, materialist, and naturalist—just like you, in other words, until it comes to the issue of math.)
ETA: If any followers of this exchange think I’m somehow not getting someting, or being unfair to SteveLandsburg, please let me know, either as a reply in the thread or a PM, whether or not you use your normal handle.
Well, Silas, what I actually did was write a book 255 pages long of which this whole Dawkins/complexity thing occupies about five pages (29-34) and where complexity is touched on exactly once more, in a brief passage on pages 7-8. From the discrepancy between your description and reality, I infer that you haven’t read the book, which would help to explain why your comments are so bizarrely misdirected.
Oh, and I see that you’re still going on about axiomatic descriptions of squirrels, as if that were relevant to something I’d said. (Hint: A simulation is not an axiomatic system. That’s 48 bajillion and one.)
I have not read the entire book. I have read many long portions of it, mostly the philosophical ones and those dealing with physics. I was drawn to on the assumption that, surely you would have defined complexity in your exposition!
It’s misleading to say that your usage of complexity only takes 8 pages, so it’s insignificant. Rather, the point you make about complexity is your grounding for broader claims about the role mathematics plays in the universe, which you come back to frequently. The explicit mention of the term “complexity” is thus a poor measure of how much you rely on it.
But even if it were just 8 pages, you should still have defined it, and you should still not expect to have achieved insights on the topic, given that you haven’t defined it.
(I certainly wouldn’t want to buy it—why should I subsidize such confused thinking? I don’t even like your defenses of libertarianism, despite being libertarian.)
Ah, another suddenly-crucial distinction to make, so you can wiggle out of being wrong!
I should probably use this opportunity to both show I did read many portions, and show why Landsburg doesn’t get what it means to really explain something. His explanation of the Heisenberg Uncertainty Principle (which gets widely praised as a good explanation for some reason) is this: think of an electron as moving in a circle within a square. If you measure its vertical position, its closeness to the top determines the chance of getting a “top” or “bottom” reading.
Likewise the horizontal direction: if you measure the horizontal position of the electron, your chances of getting a “left” or “right” reading depends on how far it is from that side.
And for the important part: why can’t you measure both at the same time? Landsburg’s brilliant explanation: um, because you can’t.
But that’s what the explanation was supposed to demystify in the first place! You can’t demystify by feeding that very mystery a blackbox fact unto itself. To explain it, you would need to explain enough of the dynamics of quantum systems so that, at the end, your reader doesn’t view precise measurement of both position and momentum as even being coherent! Saying, “oh, you can’t because you can’t” isn’t an explanation.
I didn’t say that. Read it again. I said that there is some finite axiom list that can describe squirrels, but it’s not just the axioms that suffice to let you use arithmetic. It’s those, plus biological information about squirrels. But this arithmetic is not the infinitely complex arithmetic you talk about in other contexts!
You can’t—you need axioms beyond those that specify N. The fact that the biological model involving those axioms uses math, doesn’t mean you’ve described it once you’ve described the structure N. So whether or not you call that “simulating it in the structure N”, it’s certainly more complex than just N.
I’m responding here to your invitation in the parent, since this post provides some good examples of what you’re not getting.
Simulating squirrels and using arithmetic require information, but that information is not supplied in the form of axioms. The best way to imagine this in the case of arithmetic is in terms of a structure.
Starting from the definition in that wikipedia page, you can imagine giving the graphs of the universe and functions and relations as Datalog terms. (Using terms instead of tuples keeps the graphs disjoint, which will be important later.) Like so:
Universe:
is_number(0),is_number(1), …0:
zero(0)S:
next(0,1),next(1,2), …+:
add_up_to(0,0,0),add_up_to(0,1,1),add_up_to(1,0,1)…and so on.
Then you use some simple recursive coding of datalog terms as binary. What you’re left with is just a big (infinite) set of binary strings. The Kolmogorov complexity of the structure N, then (the thing you need to use arithmetic) is the size of the shortest program that enumerates the set, which is actually very small.
Note that this is actually the same arithmetic that Steve is talking about! It is just a different level of description, one that is much simpler but entirely sufficient to conduct simulations with. It is only in understanding the long-term behavior of simulations without running them that one requires any of the extra complexity embodied in T(N) (the theory). To actually run them you just need N (the structure).
The fact that you don’t seem to understand this point yet leads me to believe you were being a little unfair when you said:
Now, if you want to complete the comparison, imagine you’re creating a structure that includes a universe with squirrel-states and times, and a function from time to squirrel state. This would look something like:
is_time(1:00:00),is_time(1:00:01), …is_squirrel_state(<eating nut>),is_squirrel_state(<rippling tail>),is_squirrel_state(<road pizza>)squirrel_does(1:00:00, <rippling tail>), …The squirrel states, though, will not be described by a couple of words like that, but by incredibly detailed descriptions of the squirrel’s internal state—what shape all its cells are, where all the mRNAs are on their way to the ribosomes, etc. The structure you come up with will take a much bigger program to enumerate than N will. (And I know you already agree with the conclusion here, but making the correct parallel matters.)
(Edit: fixed markup.)
I wasn’t careful to distinguish axioms from other kinds of information in the model, and I think it’s a distraction to do so because it’s just an issue of labels (which as you probably saw from the discussion is a major source of confusion). My focus was on tabulating the total complexity of whatever-is-being-claimed-is-significant. For that, you only need to count up how much information goes into your “message” describing the data (in the “Minimum Message Length criterion” sense of “message”). Anything in such a message can be described without loss of generality as an axiom.
If I want to describe squirrels, I will find, like most scientists find, that the job is much easier of I can express things using arithmetic. Arithmetic is so helpful that, even after accounting for the cost of telling you how to use it (the axioms-or-whatever of math), I still save in total message length. Whether you call the squirrel info I gathered from nature, or the specification of math, the “axioms” doesn’t matter.
But it’s not the same arithmetic SteveLandsburg is talking about, if you follow through to the implications he claims fall out from it. He claims arithmetic—the infinitely complex one—runs the universe. It doesn’t. The universe only requires the short message specifying N, plus the (finite) particulars of the universe. Whatever infinitely-complex thing he’s talking about from a “different level of description” isn’t the same thing, and can’t be the same thing.
What’s more, the universe can’t contain that thing because there is no (computable) isomorphism between it and the universe. As we derive the results of longer and longer chains of reasoning, our universe starts to contain more and more complex pieces of that thing, but it still wouldn’t be somehow fundamental to the universe’s operation—not if we’re just now getting to contain pieces of it.
I’m sorry, I don’t see how that contradicts what I said or shows a different parallel. Now, I certainly didn’t use the N vs. T(N) terminology you did, but I clearly explained how there have to be two separate “arithmetics” in play here, as best summarized in my comment here. Whatever infinitely complex arithmetic SteveLandsburg is talking about, isn’t the one that runs the universe. The insights on one don’t apply to the other.
Okay, pretend I’ve given you the axioms sufficient for you to +-*/. Can simulate squirrels now? Of course not. You still have to go out and collect information about squirrels and add it to your description of the axioms of arithmetic (which suffice for all of N) to have a description of squirrels.
You claim that because you can simulate squirrels with (a part of) N, then N suffices to simulate squirrels. But this is like saying that, because you know the encoding method your friend uses to send you messages, you must know the content of all future messages.
That’s wrong, because those are different parts of the compressed data: one part tells you how to decompress, another tells you what you’re decompressing. Knowing how to decompress (i.e., the axioms of N) is different from knowing the string to be decompressed by that method (i.e. the arithmetic symbols encoding squirrels).
By the way, I really hope your remark about Splat’s comment being “enlightening” was just politeness, and that you didn’t actually mean it. Because if you did, that would mean you’re just now learning the distinction between N and T(N), the equivocation between which undermines your claims about arithmetic’s relation to the universe.
And much of his comment was a restatement of my point about the difference between the complex arithmetic you refer to, and the arithmetic the universe actually runs on. (I’m not holding my breath for a retraction or a mea culpa or anything, just letting people know what they’re up against here.)
Because remember—nothing is more important to SilasBarta than politeness!
Touche :-P
Again, this word complexity is used in many ways. Complexity in the sense of humans find this complicated is a different concept from complexity in the sense of Kolmogorov complexity.
Don’t worry guys, I didn’t let you down. I addressed the issue from the perspective of Kolmogorv complexity in my first blog response. Landsburg initially replied with (I’m paraphrasing), “so what if you became an expert on information theory? That’s not the only meaning of complexity.”
Only later did he try to claim that he also meets the Kolmogorov definition.
(And FWIW, I’m not an expert on information theory—it’s just a hobby. I guess my knowledge just looked impressive to someone...)
Then what do you mean when you say “integers”^H^H “natural numbers”, if no set of premises suffices to talk about it as opposed to something else?
Anyway, no countable set of first-order axioms works. But a finite set of second-order axioms work. So to talk about the natural numbers, it suffices merely to think that when you say “Any predicate that is true of zero, and is true of the successor of every number it is true of, is true of all natural numbers” you made sense when you said “any predicate”.
It is this sort of minor-seeming yet important technical inaccuracy that separates “The Big Questions” from “Good and Real”, I’m afraid.
Natural numbers, rather. (Minor typo.)
I think that you have to be careful about claims that second-order logic fixes a unique model. Granted, you can derive the statement “There exists a unique model of the axioms of arithmetic.”
But, for example, what in reality does your “any predicate” quantifier range over? If, under interpretation, it ranges over subsets of the domain of discourse, well, what exactly constitutes a subset? This presumes that you have a model of some set theory in hand. How do you specify which model of set theory you’re using? So far as I know, there’s no way out of this regress.
[ETA: I’m not a logician. I’m definitely open to correction here.]
[ETA2: And now that I read more carefully, you were acknowledging this point when you wrote, “it suffices merely to think that . . . you made sense when you said ‘any predicate’.”
However, you didn’t acknowledge this issue in your earlier comment. I think that it’s too significant an issue to be dismissed with an “it suffices merely...”. When an infinite regress threatens, it doesn’t suffice to push the issue back a level and say “it suffices merely to show that that’s the last level.”]
Sure, and that’s the age-old argument for why we should not take second-order logic at face value. But in this case we cannot go around blithely talking about the integers for there is no language we could use to speak of them, or any other infinite set. We would be forbidden of saying that there is something we cannot talk about, and this is not surprising—what is it you can’t refer to?
I’m not familiar with the literature of this argument. (It was probably clear from the tentativeness of my comment that I was thinking my own murky way through this issue.)
You seem to take it as the default that we should take second-order logic at face value. (Now that I know what you mean by “face value”, I see that you did acknowledge this issue in your earlier comment.) But I should think that the default would be to be skeptical about this. Why expect that we have a canonical model when we talk about sets or predicates if we’re entertaining skepticism that we have a canonical model for integer-talk?
We don’t. Skepticism of sets, predicates, and canonical integers are all the same position in the debate.
And so is skepticism of canonical Turing machines, as far as I can tell. Specifically, skepticism that there is always a fact of the matter as to whether a given TM halts.
I think you might be able to make the skeptical position precise by constructing nonstandard variants of TMs where the time steps and tape squares are numbered with nonstandard naturals, and the number of symbols and states are also nonstandard, and you would be able to relate these back to the nonstandard models that produced them by using a recursive description of N to regenerate the nonstandard model of the natural numbers you started with. This would show that there are nonstandard variants of computability that all believe in different ‘standard’, ‘minimal’ models of arithmetic, and are unaware of the existence of smaller models, and thus presumably of the ‘weaker’ (because they halt less often) notions of Turing Machines.
Now, I’m not yet sure if this construction goes through as I described it; for me, if it does it weighs against the existence of a ‘true’ Standard Model and if it doesn’t it weighs in favor.
I’m not sure, but I think it’s impossible to construct a computable nonstandard model of the integers (one where you can implement operations like +).
It is in fact provably impossible to construct a computable nonstandard model (where, say, S and +, or S and × are both computable relations) in a standard model of computation. What I was referring to was a nonstandard model that was computable according to an equally nonstandard definition of computation, one that makes explicit the definitional dependence of Turing Machines on the standard natural numbers and replaces them with nonstandard ones.
The question I’m wondering about is whether such a definition leads to a sensible theory of computation (at least on its own terms) or whether it turns out to just be nonsense. This may have been addressed in the literature but if so it’s beyond the level to which I’ve read so far.
Would you give a reference? I found it easy to find assertions such as “the completeness theorem is not constructively provable,” but this statement is a little stronger.
Tennenbaum’s Theorem
I believe that this claim is based on a defective notion of what it takes to refer to something successfully. The issue that we’re talking about here is a manifestation of that defect. I’m trying to work out a different conception of reference, but it’s very much a work in progress.
No, it wouldn’t—he’s saying basically the same thing I did. The laws of physics are computable. In describing observations, we use concepts from math. The reason we do so is that it allows simpler descriptions of the universe.