gardner@shl.com (Gardner Buchanan) (04/19/91)
>So, what is the least positive integer not expressable in less than 13 >English words? I think it's 121,121,121; assuming you don't use "and": One hundred twenty one million one hundred twenty one thousand 1 2 3 4 5 6 7 8 9 10 one hundred twenty one 11 12 13 14 :-) -- Gardner Buchanan gardner@shl.com Systemhouse, Ottawa (613) 236-6604 x375
tgl@g.gp.cs.cmu.edu (Tom Lane) (04/19/91)
In article <1991Apr18.210832.9918@shl.com>, gardner@shl.com (Gardner Buchanan) writes: > >So, what is the least positive integer not expressable in less than 13 > >English words? > > I think it's 121,121,121; assuming you don't use "and": Try: one hundred twenty one times one million one thousand and one The question is of no interest if you are restrictive about *how* the integer is described. I believe the original poster meant to include phrases like "the ten millionth prime" and other indirect specifications. In that case it's obviously an unsolvable problem. (Try "ten if Fermat's last conjecture is true, else eleven".) -- tom lane Internet: tgl@cs.cmu.edu BITNET: tgl%cs.cmu.edu@cmuccvma
weverka@spot.Colorado.EDU (Robert T. Weverka) (04/19/91)
In article <1991Apr18.210832.9918@shl.com> gardner@shl.com (Gardner Buchanan) writes: >>So, what is the least positive integer not expressable in less than 13 >>English words? > >I think it's 121,121,121; assuming you don't use "and": > >One hundred twenty one million one hundred twenty one thousand > 1 2 3 4 5 6 7 8 9 10 > >one hundred twenty one >11 12 13 14 > >:-) I can express 121,121,121 in only 8 words. eleven squared times one million one thousand one 1 2 3 4 5 6 7 8
weverka@spot.Colorado.EDU (Robert T. Weverka) (04/19/91)
>In article <1991Apr18.210832.9918@shl.com> gardner@shl.com (Gardner Buchanan) writes: >>>So, what is the least positive integer not expressable in less than 13 >>>English words? >> >>I think it's 121,121,121; assuming you don't use "and": >> >>One hundred twenty one million one hundred twenty one thousand >> 1 2 3 4 5 6 7 8 9 10 >> >>one hundred twenty one >>11 12 13 14 >> >>:-) Try 121121129 One hundred twenty one million one hundred twenty one thousand 1 2 3 4 5 6 7 8 9 10 one hundred twenty nine 11 12 13 14 this is of course the smallest prime number greater than 121,121,121 :-)
brad@looking.on.ca (Brad Templeton) (04/19/91)
In article <1991Apr18.210832.9918@shl.com> gardner@shl.com (Gardner Buchanan) writes: >>So, what is the least positive integer not expressable in less than 13 >>English words? > >I think it's 121,121,121; assuming you don't use "and": > >One hundred twenty one million one hundred twenty one thousand > 1 2 3 4 5 6 7 8 9 10 > >one hundred twenty one >11 12 13 14 > Maybe I missed the start of this, but isn't this an old paradox? After all, "least positive integer not expressable in less than 13 English words" has 11 words, so in fact there is no such animal. -- Brad Templeton, ClariNet Communications Corp. -- Waterloo, Ontario 519/884-7473
dfs@doe.carleton.ca (David F. Skoll) (04/19/91)
In <12719@pt.cs.cmu.edu> tgl@g.gp.cs.cmu.edu (Tom Lane) writes: [Someone wrote:] >> >So, what is the least positive integer not expressable in less than 13 >> >English words? >The question is of no interest if you are restrictive about *how* the >integer is described. I believe the original poster meant to include >phrases like "the ten millionth prime" and other indirect specifications. >In that case it's obviously an unsolvable problem. I think you've got it! "The least positive integer not expressable in less than 13 English words" is a 12-word English sentence. Hmm... -- David F. Skoll
dfs@doe.carleton.ca (David F. Skoll) (04/19/91)
In <1991Apr19.153858.19089@colorado.edu> weverka@spot.Colorado.EDU (Robert T. Weverka) writes: >Try 121121129 >this is of course the smallest prime number greater than 121,121,121 >:-) One Two One One Two One One Two Nine (Base Ten) 1 2 3 4 5 6 7 8 9 10 11 Next... :-) -- David F. Skoll
davidc@montagar.lonestar.org (David L. Cathey, SYSOP) (04/20/91)
In article <1991Apr18.210832.9918@shl.com>, gardner@shl.com (Gardner Buchanan) writes: >>So, what is the least positive integer not expressable in less than 13 >>English words? > > I think it's 121,121,121; assuming you don't use "and": > > One hundred twenty one million one hundred twenty one thousand > 1 2 3 4 5 6 7 8 9 10 > > one hundred twenty one > 11 12 13 14 > But if you change to a different base, which is mathematically valid, you can represent the same number in less words! 121,121,121 = 0x7382961 = seven three eight two nine six one hex :-) 1 2 3 4 5 6 7 8 Just kidding, I think you are correct based on the intended premise of the question. > Gardner Buchanan gardner@shl.com > Systemhouse, Ottawa > (613) 236-6604 x375 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - David L. Cathey |INET: davidc@montagar.lonestar.org Don't blame me! I voted for Bill and |UUCP: ...!texsun!montagar!davidc Opus for President! Ack! Thhrrptt! |Fone: (214)-618-2117
tomh.bbs@shark.cs.fau.edu (Tom Holroyd) (04/20/91)
> >>So, what is the least positive integer not expressable in less than 13 > >>English words? Hmm. Compressing English phrases into shorter ones. Keep it up and pretty soon we'll all be speaking zipspeak, or maybe arctalk. Might improve the signal to noise ratio a bit.. :-) :-) tomh@bambi.ccs.fau.edu
gwyn@smoke.brl.mil (Doug Gwyn) (04/21/91)
In article <1991Apr18.210832.9918@shl.com> gardner@shl.com (Gardner Buchanan) writes: >>So, what is the least positive integer not expressable in less than 13 >>English words? >I think it's 121,121,121; assuming you don't use "and": No, if that really were it then you could express it as: "the least positive integer not expressable in less than 13 English words" which expresses it in only 12 English words.
gwyn@smoke.brl.mil (Doug Gwyn) (04/21/91)
In article <1991Apr19.155442.4840@looking.on.ca> brad@looking.on.ca (Brad Templeton) writes: >After all, "least positive integer not expressable in less than 13 >English words" has 11 words, so in fact there is no such animal. But then what about the following argument: There are a finite (although large) number of English words. The number of combinations of fewer than 13 words from the finite set of words is also finite (although very large). The combinations of fewer than 13 English words that express positive integers form a subset of the set of all possible combinations of fewer than 13 English words, and thus that subset is finite. Every finite set of positive integers has a least member. Therefore the (finite) set of positive integers expressed by that subset of English word combinations has a least member. It would seem that the phrase does describe some integer. Yes, it's a paradox. But it could be relevant when considering compression schemes that encode numeric values in terms of formulas.
jms@tardis.Tymnet.COM (Joe Smith) (04/21/91)
In article <1991Apr19.153858.19089@colorado.edu> weverka@spot.Colorado.EDU (Robert T. Weverka) writes: >Try 121121129; it needs more than 13 words. >this is of course the smallest prime number greater than 121,121,121. :-) weverka@spot.Colorado.EDU (Robert T. Weverka) writes: >eleven squared times one million one thousand one Combining these two, I come up with: "smallest prime above eleven squared times one million one thousand one" 1 2 3 4 5 6 7 8 9 10 11 Want to try again? -- Joe Smith (408)922-6220 | SMTP: jms@tardis.tymnet.com or jms@gemini.tymnet.com BT Tymnet Tech Services | UUCP: ...!{ames,pyramid}!oliveb!tymix!tardis!jms PO Box 49019, MS-C51 | BIX: smithjoe | CA license plate: "POPJ P," (PDP-10) San Jose, CA 95161-9019 | humorous dislaimer: "My Amiga 3000 speaks for me."
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (04/23/91)
In article <15901@smoke.brl.mil> gwyn@smoke.brl.mil (Doug Gwyn) writes: > There are a finite (although large) number of English words. > The number of combinations of fewer than 13 words from > the finite set of words is also finite (although very large). > The combinations of fewer than 13 English words that express > positive integers form a subset of the set of all possible > combinations of fewer than 13 English words, and thus that > subset is finite. As with all set-theoretic ``paradoxes,'' the flaw is in defining your sets. There exist propositions which do not define sets---in fact, the set of integers not expressible in fewer than 13 words is not defined. If you restrict attention to those propositions which do define sets, the ``paradox'' goes away. This becomes obvious in any formalization of the argument. There is no reason to believe that you can convert any given English proposition into the set satisfying that proposition, just as there is no reason to believe that you can define the set of all sets which do not contain themselves. ---Dan
ch@dce.ie (Charles Bryant) (04/23/91)
In article <15901@smoke.brl.mil> gwyn@smoke.brl.mil (Doug Gwyn) writes: > The combinations of fewer than 13 English words that express > positive integers form a subset of the set of all possible > combinations of fewer than 13 English words, and thus that > subset is finite. > Every finite set of positive integers has a least member. Hang on there! There is a gap there. A `combination of English words that expresses an integer' is not `an integer'. For example `a random integer' or `my age' both express an integer, but cannot be said to be less than or greater than `forty two'. Also I have doubts that every finite set of integers has a least member if sets are allowed where it is impossible to determine whether a given integer is in the set or not. -- Charles Bryant (ch@dce.ie) -- If you like the opinions expressed in this message, they may be available for rent - contact your local sales office. Low interest deals available.
ttobler@unislc.uucp (Trent Tobler) (04/26/91)
From article <15901@smoke.brl.mil>, by gwyn@smoke.brl.mil (Doug Gwyn): > In article <1991Apr19.155442.4840@looking.on.ca> brad@looking.on.ca (Brad Templeton) writes: >>After all, "least positive integer not expressable in less than 13 >>English words" has 11 words, so in fact there is no such animal. > > But then what about the following argument: > There are a finite (although large) number of English words. > The number of combinations of fewer than 13 words from > the finite set of words is also finite (although very large). > The combinations of fewer than 13 English words that express > positive integers form a subset of the set of all possible > combinations of fewer than 13 English words, and thus that > subset is finite. > Every finite set of positive integers has a least member. > Therefore the (finite) set of positive integers expressed by > that subset of English word combinations has a least member. > It would seem that the phrase does describe some integer. No, it is self referencial. If 'The least positive integer not expressable in less than thirteen english words' is allowed to represent the least positive integer not expressable in less than thirteen english words, then that number does not exist. You try to make some correlation between this and the labeling of english sentences. The problem with this is that it is not 'The least positive integer not expressable in less than eighteen english words which specify a unique integer.' > Yes, it's a paradox. No, no paradox. The number simply does not exist. > But it could be relevant when considering compression schemes > that encode numeric values in terms of formulas. Yes, it is relevent, and has been considered. See Godel's theorem and the turing halting problem. -- Trent Tobler - ttobler@csulx.weber.edu
herrickd@iccgcc.decnet.ab.com (04/27/91)
In article <kgio16w163w@shark.cs.fau.edu>, tomh.bbs@shark.cs.fau.edu (Tom Holroyd) writes: > Hmm. Compressing English phrases into shorter ones. Keep it up > and pretty soon we'll all be speaking zipspeak, or maybe arctalk. > Might improve the signal to noise ratio a bit.. :-) :-) > Nah, net noise will zip no better than signal. It'll just free bandwidth for more of it. dan herrick herrickd@iccgcc.decnet.ab.com
gwyn@smoke.brl.mil (Doug Gwyn) (04/27/91)
In article <1991Apr25.234539.24276@unislc.uucp> ttobler@unislc.uucp (Trent Tobler) writes: >No, no paradox. The number simply does not exist. Oh, good -- then we can conclude that all positive integers are expressable in fewer than 13 English words. That has ramifications for data compression.. In case you didn't detect the sarcasm, I'm well aware of Godel's work etc. but I don't think it helps answer the question "What is wrong with this argument?". Self-reference is not automatically invalid; consider "This is a sentence." There's nothing wrong with that. Even "This is not a sentence." is meaningful, albeit false. "The set of all sets that do not include themselves" is not meaningful, but you can't lay the entire blame on self-reference.
doug@eris.berkeley.edu (Doug Merritt) (04/29/91)
In article <15989@smoke.brl.mil> gwyn@smoke.brl.mil (Doug Gwyn) writes: > >Oh, good -- then we can conclude that all positive integers are >expressable in fewer than 13 English words. [...] >In case you didn't detect the sarcasm, I'm well aware of Godel's >work etc. but I don't think it helps answer the question "What is >wrong with this argument?". Self-reference is not automatically >invalid; consider "This is a sentence." [...] > Even "This is not a sentence." is meaningful, albeit >false. "The set of all sets that do not include themselves" is >not meaningful, but you can't lay the entire blame on self-reference. Some good points, good enough to reply to. (A great deal of the stuff in this thread has sounded as if people had never heard the subject discussed before, hard though that is to believe.) You go too far with that last point, though. Self reference can be very useful, but the "entire blame" for self-contradiction *does* lay on self-reference. Saying that such self-contradiction is "not meaningful" can work for simple cases, where you can pin down the problem to a very small set of symbols which contradict each other. It does not work in general, however, because one can have very complex systems of logic/math in which one finds contradictions, without any *single* statement being the culprit. This is the general class of inconsistent statements, and Godel's theorem does apply. The big problem is that, Godel notwithstanding, systems with the power of self-reference are just too handy to toss out. Try to get by on propositional logic rather than predicate logic, for instance. This was the reef on which Principia Mathematica foundered. The "Theory of Types" was introduced to try to get around it, and most mathematicians (e.g. all of the ones who hang out in sci.math) consider this to be workable for the things they care about, but it turns out not to be equivalent in power, and so no really ultimate solution has been found yet. That is, people will sometimes claim the crisis is over, but they're the ones who don't find a need for self referential systems. The people who do find self reference handy (extremely frequent in CS) try to avoid inconsistency by what amounts to exhaustive test. I have yet to see the two camps agree on anything fundamental. Doug -- -- Doug Merritt doug@eris.berkeley.edu (ucbvax!eris!doug) or uunet.uu.net!crossck!dougm
rpw3@rigden.wpd.sgi.com (Rob Warnock) (05/05/91)
In article <15989@smoke.brl.mil> gwyn@smoke.brl.mil (Doug Gwyn) writes: +--------------- | ttobler@unislc.uucp (Trent Tobler) writes: | >No, no paradox. The number simply does not exist. | | Oh, good -- then we can conclude that all positive integers are | expressable in fewer than 13 English words. That has ramifications | for data compression.. | | In case you didn't detect the sarcasm, I'm well aware of Godel's | work etc. but I don't think it helps answer the question "What is | wrong with this argument?". Self-reference is not automatically | invalid; consider "This is a sentence." There's nothing wrong | with that. Even "This is not a sentence." is meaningful, albeit | false. "The set of all sets that do not include themselves" is | not meaningful, but you can't lay the entire blame on self-reference. +--------------- Doug, the problem *is* self-reference, but the sticking point is simply that this discussion thread hasn't quoted the "right" authority yet... ;-} We need not refer to Godel (yet), but to Russell. Using Russell's Theory of Types, if there is a thing pointed to by the phrase "the smallest positive integer not expressable in 13 English words", whatever that thing is, it's not itself a "positive integer" -- it's of a higher type, since it talks *about* "integers expressable by words". Thus there is no immediate paradox (though there may be one later in the investigation). If I remember it correctly, in the Theory of Types, one would oddly enough say that "This is not a sentence" is *true*, since it is *not* a "sentence" but a "sentence-about-sentences" (a higher-order type). -Rob ----- Rob Warnock, MS-1L/515 rpw3@sgi.com rpw3@pei.com Silicon Graphics, Inc. (415)335-1673 Protocol Engines, Inc. 2011 N. Shoreline Blvd. Mountain View, CA 94039-7311