tag:blogger.com,1999:blog-3722233.post8332168540710996095..comments2024-08-03T11:58:59.111-05:00Comments on Computational Complexity: Lincoln's Dog-Tail question (in honor of Presidents Day)Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger24125tag:blogger.com,1999:blog-3722233.post-30635850170642239602014-08-13T09:36:24.839-05:002014-08-13T09:36:24.839-05:00think a lot of people are missing the point of thi...think a lot of people are missing the point of this...the point of all this is there is only 1 truth and only one fact..RIGHT OR WRONG IN LIFE.. DOGs ONLY have 4 LEGS..not because you call a tail a LEG...that dont mean its a LEG..its still 4<br /><br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48579048094636906462013-01-26T18:28:18.679-06:002013-01-26T18:28:18.679-06:00Depends whether the dog is an amputee.Depends whether the dog is an amputee.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35190921178165715652012-12-19T02:48:04.001-06:002012-12-19T02:48:04.001-06:00I am firmly in the "four" camp. I unders...I am firmly in the "four" camp. I understand the point of view of the fivers, and agree that it has value. Hell, I'll celebrate it on Interesting Point Day. But the preamble is just that, and when the dog runs, it will use four legs and not five. Define what you want, but to the dog, that definition is a matter of indifference, unlike the number of legs it has.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42725026521032943192011-03-05T15:52:05.846-06:002011-03-05T15:52:05.846-06:00I think the answer is 5. It is true that calling t...I think the answer is 5. It is true that calling the tail "leg" does not change the leg, but you are the one asking the question and formally your answer is 5. Other one asks me in middle of this "How many legs does a dog have?" I would say a 4 to him, a 5 to you. The puzzle you're posing is not about the dog!Salnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63127719447469607222011-02-26T09:51:30.396-06:002011-02-26T09:51:30.396-06:00Here are some amusing informal connections:
Life ...Here are some amusing informal connections:<br /><br />Life imitates Art:<br /><br />Watson the computer is named after Thomas Watson, the first president of IBM. Go back to Stanley Kubrick's classic sci-fi film "2001: A Space Odyssey". The computer name HAL was code for IBM.<br /><br />Another connection:<br /><br />Think Watson the man (James) who helped discover the structure of DNA, wrote the book "Double Helix", and was instrumental in carrying out the Human Genome Project, the amino acid code.<br /><br />If memory serves me well, Watson and Crick tested various mathematical models on a computer before they got the right one. Computer as lab rat, so to speak.james blairhttp://firedude7@aol.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91169085013070961992011-02-24T23:38:55.783-06:002011-02-24T23:38:55.783-06:00John,
Sounds like a plan.
I look forward to see...John, <br /><br />Sounds like a plan.<br /><br />I look forward to seeing how it unfolds.Jim Blairhttp://firedude7@aol.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11412012100722851092011-02-24T10:26:17.395-06:002011-02-24T10:26:17.395-06:00Jim, with regard to formalizing the notion of &quo...Jim, with regard to formalizing the notion of "narrative" in complexity theory, I am working toward posting a question in this regard on TCS StackExchange with the intent that it be sufficiently well-posed as to be objectively answerable (with current complexity-theoretic knowledge) ... this is the hope, anyway.<br /><br />A key step in this construction is associated to the question "Are runtime bounds in P decidable? (answer: no)" for which <a href="http://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no/5006#5006" rel="nofollow">Emanuele Viola's proof</a> provides a beautiful and ingenious answer.<br /><br />When it comes to formalizing ideas, a really nice aspect of the various StackExchanges is the discipline and objectivity that they enforce equally upon askers and answerers.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70897414752163043612011-02-24T06:38:20.158-06:002011-02-24T06:38:20.158-06:00Back to John's question:
Is there a way to fo...Back to John's question:<br /><br />Is there a way to formalize the quality of narrative in mathematics, just as the concepts of consistency, completeness, and complexity have been formalized?<br /><br />You ask a very good question (thought provoking)in a very good way (concise and to the point).<br /><br />Keep it up. Maybe the rest of us can find some useful pointers to help you find an interesting answer.<br /><br />Hopefully, the cybernetic feedback will not be too noisy or too quiet.Jim Blairhttp://firedude7@aol.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2174478533497707772011-02-23T08:03:14.510-06:002011-02-23T08:03:14.510-06:00I was happy with the first three numeric answers: ...I was happy with the first three numeric answers: the Douglas Dog, the Lincoln Dog, and the Prince Dog ... the "one" with the leg formerly known as tail.<br /><br />If you superimposed the Lincoln Dog and the Prince Dog, you could get back to just two dogs.<br /><br />But they just keep permutating ....Jim Blairhttp://firedude7@aol.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7660080731648320332011-02-22T18:18:15.359-06:002011-02-22T18:18:15.359-06:00I think the confusion here is that "leg"...I think the confusion here is that "leg" or "5" are symbols which, by common consent, have a certain meaning. They are not platonic ideals -- eternally unchangeable and perfect.<br /><br />If we redefine then word "leg" to mean something different, then, yes, a dog can have 5 legs. <br /><br />If we change the association of the symbol "5" to mean the successor of "3" which is itself the successor of "2" which is the successor of "1", which is the successor of "0", the arithmetic identity, then "2"+"2" does equal "5" and "4" is either undefined or has some other value.Unknownhttps://www.blogger.com/profile/01005537995315440769noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36351670864443698002011-02-22T11:08:28.683-06:002011-02-22T11:08:28.683-06:00This Lincoln story, to me, brings to mind the way ...This Lincoln story, to me, brings to mind the way his comments on race and slavery so often slice right through cant.Shelleyhttp://dustbowlpoetry.wordpress.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60835228270476728572011-02-22T10:53:19.496-06:002011-02-22T10:53:19.496-06:00Oh, we all of us would like to live on the floatin...Oh, we all of us would like to live on <a href="http://en.wikipedia.org/wiki/Laputa" rel="nofollow">the floating island of Laputa</a> ...<br /><br />Hmmm ... except for field ecologists ... trauma surgeons ... novelists ... and comedians!<br /><br />Yes, there are pleasures—and even mathematical inspirations—to be found at ground-level too.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46743716175166455952011-02-22T10:31:06.255-06:002011-02-22T10:31:06.255-06:00The answer to the last anonymous question is "...The answer to the last anonymous question is "yes".<br /><br />Simple book keeping creates huge problems. Think: "credit default swaps".<br /><br />The answer to John's question about creating a mathematical narrative is: How far down the mathemical food chain do you want to go?Jim Blairhttp://firedude7@aol.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28991554197941863262011-02-22T08:44:26.254-06:002011-02-22T08:44:26.254-06:00MTV has non-musician reality programming
AMC showe...MTV has non-musician reality programming<br />AMC showed a British First-run Television series<br />Cartoon Network airs live action shows<br />History Channel aired Hunt for Red October<br /><br />all of these are far more troubling to me than this blog having fun little posts like this oneAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90215137343801903042011-02-22T06:32:33.529-06:002011-02-22T06:32:33.529-06:00Nobody answered the question posed by Ricky Martin...Nobody answered the question posed by Ricky Martino. Is this still a complexity theory blog?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77019970675786756462011-02-22T05:46:39.262-06:002011-02-22T05:46:39.262-06:00To answer Ed Darrell's question in a literal (...To answer Ed Darrell's question in a literal (possibly boring) way, it is natural to read-out the point of this GASARCH weblog essay in very much the same way as Tim Gowers's present weblog essay <i>A new way of proving sumset estimates</i> ... indeed, I borrowed the phrase "read out" from Tim's discussion!<br /><br />Tim's essay talks about proofs that consist of a long string of elementary manipulations ... so many, that one loses the ability to "read out" a story from the proof. The essay remarks:<br /><br />-------------<br />"Of course, if one feels this way about a proof, it is a good sign that one probably hasn’t fully understood the proof, as there is usually some story to tell about how the sequence of elementary observations was discovered. I freely admit to not fully understanding the proof of the sumset estimates in this deep way ... But now, I am glad to say, all that is a thing of the past. A research student of mine [named] George Petridis, has come up with a ridiculously simple proof."<br />-------------<br /><br />There are many, many essays by renowned mathematicians that make the same point about the central role of narrative ideas in high-level mathematics. <br /><br />Indeed, the utter absence of narrative capacity is what is so conspicuously alien about the "Watson" style of artificial intelligence. The absence of narrative is a signifier that Watson does not really understand the questions it is answering, and thus, is unlikely ever to really do high-quality mathematics.<br /><br />Lincoln was skillfully making the same point ... that politicians like Douglas, in offering pro-slavery arguments of correct logical form, but devoid of moral narrative, were proving themselves incapable of human-quality statesmanship.<br /><br />Is there a way to formalize the quality of narrative in mathematics, just as the concepts of consistency, completeness, and complexity have been formalized? If not, why not? If so, what might a formalized definition of mathematical narrative look like? And what kind of dogs are we telling stories about? Do the class P have too many dogs in it ... or too few?<br /><br />These are very interesting questions, that Lincoln's story suggests to us very compactly.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91448598697044798862011-02-21T22:47:06.285-06:002011-02-21T22:47:06.285-06:00How long will we tell a silly story if we can attr...How long will we tell a silly story if we can attribute it to Lincoln?<br /><br />Does this apply to any story, or only that that can actually be connected to Lincoln?<br /><br />What about Einstein, Twain, Jefferson, and Teddy Roosevelt?<br /><br />Why don't we attribute stories to Washington the same way we attribute stories to Einstein, Twain, Jefferson, T. Roosevelt and Lincoln, even though we lack proof that they actually said the stuff alleged?<br /><br />The answer, obviously, is "42."Ed Darrellhttps://www.blogger.com/profile/10056539160596825210noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43568938211995186412011-02-21T21:49:17.735-06:002011-02-21T21:49:17.735-06:00ok this is a complexity blog rite ?ok this is a complexity blog rite ?ricky martinonoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91646403234908275692011-02-21T21:12:18.109-06:002011-02-21T21:12:18.109-06:00The answer to "what would 2+2 equal to if we ...<i>The answer to "what would 2+2 equal to if we defined 2+2=5" is 5. Yes, you can attack the premise, but that is not an answer to the question itself.</i><br /><br />Another equally correct answer to "What would 2+2 equal if 2+2=5" is "Her Lunar Majesty, the Empress of the Moon". Given a false premise, one can logically conclude <em>anything</em>.JeffEhttps://www.blogger.com/profile/17633745186684887140noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23175027770798941262011-02-21T20:45:01.305-06:002011-02-21T20:45:01.305-06:00Why call paradox a theorem? It goes against intuit...Why call paradox a theorem? It goes against intuition, not against logic or its own premises.Janomahttps://www.blogger.com/profile/08125807104571129259noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62800766076999937692011-02-21T16:15:21.361-06:002011-02-21T16:15:21.361-06:00Lincoln's anecdote is fide Henry M. Smith in &...Lincoln's anecdote is <i>fide</i> Henry M. Smith in "Western Reminiscences", <i>Proceedings of the Worcester Society of Antiquity</i> Volume 2, Page 42 (1879) ... although there is evidence that Lincoln told this anecdote on numerous occasions! <br /><br />`Cuz heck, it's a wonderful story that so deftly makes a hard-to-grasp point, that we are still telling it 132 years later.<br /><br />Here is one natural pullback of Lincoln's anecdote that makes a hard-to-grasp practical point relating to complexity theory:<br /><br />-----------<br />"If a complexity theorist specifies an algorithm in P, can an engineer verify (or falsify) that its runtime is O(n^2)?"<br />-----------<br /><br />The surprising (at first sight) answer has been <a href="http://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no/5006#5006" rel="nofollow">neatly proved by Emanuele Viola</a>: the engineer's verification question is ... undecidable.<br /><br />Thus I came to appreciate that complexity theory is, in effect, that branch of mathematics in which dogs have a finite-but-undecidable number of legs! :)<br /><br />The narrow point of this story is that that for <i>many</i> breeds of dogs (that is, algorithms in P) the number of legs (that is, the runtime exponent) is perfectly feasible to count. However, complexity theory teaches us that there exist <i>some</i> breeds of dogs (that is, <i>some</i> algorithms in P) for which verifying the leg-count is not just exponentially difficult ... but utterly undecidable.<br /><br />The broad point of this story (the intended broad point, anyway) is that modern complexity theory has much to teach engineers, provided that engineers and complexity theorists respect each other's normative usages, and draw practical conclusions from the theorems of complexity theory with due respect for their surprising subtlety ... even for so seemingly straightforward a task as counting legs. :)John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10851038476099056792011-02-21T15:51:42.670-06:002011-02-21T15:51:42.670-06:00The answer to "what would 2+2 equal to if we ...The answer to "what would 2+2 equal to if we defined 2+2=5" is 5. Yes, you can attack the premise, but that is not an answer to the question itself.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17956943815349410512011-02-21T15:23:45.174-06:002011-02-21T15:23:45.174-06:00If I was asked
"How many legs would a dog ha...If I was asked <br />"How many legs would a dog have if we called the dog's tail a leg?" <br />I would say 4, but if I was asked <br />"Define a leg to be (what we usually call) a leg or a tail. How many legs does a dog have" <br />I would say 5. The first question and answer shows that changing the definition doesn't change the number of legs, but the second shows that I accept that we can change that definitions. What would other people who say 4 to the first question say to the second?Unknownhttps://www.blogger.com/profile/16545393909591610628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57816811445477109562011-02-21T14:22:09.941-06:002011-02-21T14:22:09.941-06:00One.
If the dog's tail is called a 'leg&#...One.<br /><br />If the dog's tail is called a 'leg', then the legs are still called legs?Anonymousnoreply@blogger.com