I kept doingn it wrongn
« previous post | next post »
Martin Gardner would have like the mouseover title text on the latest xkcd:
And of course I had to redo this like three times because I kept writing 'UNTIE'; I kept doing 'doing 'doing it wrong' wrong' wrong.
Martin might have pointed out the possibility of adding one more level of recursion by changing UNITE to UNTIE in the t-shirt message (and UNTIE to UNITE in the prefixed apology):
And of course I had to redo this like three times because I kept writing 'UNITE'; I kept doing 'doing 'doing 'doing it wrong' wrong' wrong' wrong.
And then if you change the t-shirt back to UNITE, and the apology back to 'UNTIE', you can add yet another level:
And of course I had to redo this like three times because I kept writing 'UNTIE'; I kept doing 'doing 'doing 'doing 'doing it wrong' wrong' wrong' wrong' wrong.
And this, of course, shows by mathematical induction that 'UNITE' in the apology and UNTIE on the t-shirt is compatible with any even-numbered value of n, while 'UNTIE' in the apology and UNITE on the t-shirt is compatible with any odd value of n, in the formula
I kept doingn it wrongn
Homework: give an expression for generating strings with balanced parentheses? Balanced open and closed quotes, alternating single and double by level?
Henning Makholm said,
May 26, 2010 @ 9:50 am
re homework: In which formalism?
[(myl) Your choice!]
Jeff DeMarco said,
May 26, 2010 @ 9:52 am
Many years ago in my college band we had the pre-pre-banquet cocktail party cocktail party….
Yuval said,
May 26, 2010 @ 10:37 am
IIRC, this should be a context-free grammar / stack automaton:
S -> I kept C
C -> doing C wrong
C -> it
[(myl) Full credit! For extra credit, generate the quotes (and spaces) in the right places.]
John Lawler said,
May 26, 2010 @ 10:43 am
A rather different form of recursion displayed here (at least to me) was due to the fact that the exponential n in the post's title, especially in the sans-serif face used for titles, is very easy to mistake for a double quote. In the sans-serif face used here, that's
I kept doingⁿ it wrongⁿ
vs.
I kept doing" it wrong"
(but the quote marks " in the display here are slanted)
This is how I initially read it, and I kept wondering what kind of recursion the quotation marks would display as I read through the post (was it really supposed to be 'doing "it" wrong'?). Then I noticed the n (I had zoomed in on the text while reading); then I got to recurse. Nice effect, Mark.
John Lawler said,
May 26, 2010 @ 10:44 am
The quote marks " in the final display (as opposed to the temporary display) appear not to be slanted.
neff said,
May 26, 2010 @ 10:52 am
Now I find myself considering how people would use pitch emphasis to distinguish the meta-levels of quoting if they said that aloud. What are some good phonology papers about that sort of thing?
greg said,
May 26, 2010 @ 12:05 pm
re: homework – It has been several years since I took an automata class, but I do remember that regexp can't count balanced parenthesis, so creating them must involve something I don't remember or didn't learn.
google and wikipedia tells me the answer though, which is definitely beyond my understanding/remembrance, so I'll let someone else tangle with the adaptation of the alternating single and double quotes.
Michael Moore said,
May 26, 2010 @ 1:14 pm
S -> I kept doing C wrong
C -> 'doing D wrong'
D -> "doing C wrong"
C -> it
D -> it
Charles said,
May 26, 2010 @ 1:54 pm
Personally, I find this about as clever as saying "I'm not not not not not not not not not not not not not hungry," then making your reader parse out whether you're hungry or not.
MattG said,
May 26, 2010 @ 2:07 pm
DFW covers a similar example in Infinite Jest. Agents aren't "double" or "triple", they're "even-numbered" or "odd-numbered"
Aaron Toivo said,
May 26, 2010 @ 2:19 pm
Friends and I had a variation on the pattern XKCD used, years ago, in parody of some comedian we'd found online somewhere pseudo-ranting about how in his home country they "throw Jews down the well". Soon we were using "throw X down the well" for anything bad or disliked (purely in parody, I assure you); and of course the phrase itself quickly became overused. Thus "throw throwing things down the well down the well". Which in turn spawned a series of recursive replies in argument, each consisting of throwing the prior reply down the well: "I throw throwing throwing throwing throwing things down the well down the well down the well down the well!"
Eric S said,
May 26, 2010 @ 2:57 pm
> Homework: give an expression for generating strings with
> balanced parentheses? Balanced open and closed quotes,
> alternating single and double by level?
I see all these CFGs in response to this. Boring! Why not write an actual, executable program?
Here's a Tcl implementation. Apologies that whitespace didn't get preserved — 5 minutes was already way too long to spend on this. :)
You'll have to remove the extra newline created (by the form entry system) after line 2 if you really want to run it.
Now you can generate jokes automatically to your heart's content!
#!/bin/bash
# \
exec tclsh $0 "$@"
set LEVELS [lindex $argv 0]
set USAGE "usage: $argv0 num-levels ?-paren?"
set LEFT_QUOTE \"
set RIGHT_QUOTE \"
if {[llength $argv]<1 || ![string is integer -strict $LEVELS]} {
puts stderr $USAGE
exit 1
}
if {[llength $argv]==2} {
if {[lindex $argv 1]!="-paren"} {
puts stderr $USAGE
exit 1
}
set LEFT_QUOTE (
set RIGHT_QUOTE )
}
proc next_quote {leftquote rightquote} {
foreach quote [list $leftquote $rightquote] {
lappend out [string map {' \" \" '} $quote]
}
return $out
}
proc wrong_quote {n {str it} {leftquote \"} {rightquote \"}} {
if {$n<=0} {return "it"}
incr n -1
foreach {nextlquote nextrquote} [next_quote $leftquote $rightquote] break
set substr [wrong_quote $n $str $nextlquote $nextrquote]
return "${leftquote}doing $substr wrong${rightquote}"
}
puts "I kept doing [wrong_quote $LEVELS it $LEFT_QUOTE $RIGHT_QUOTE] wrong."
ambrosen said,
May 26, 2010 @ 4:25 pm
For the recursive case of the comparison of the students (Cholmondeley and Featherstonehaugh) who disagreed over each other's efforts in transcribing the following
Smith, where Jones had had "had had" had had "had". "Had had" had had the examiner's approval.
where we describe the situation with the following pair of sentences:
Cholmondely, where Featherstonehaugh had had 'had had "had had" had had "had". "Had had" had had' had had 'had had "had" had had "had had". "Had had" had had'. 'Had had "had had" had had "had". "Had had" had had' had had the better justification, in Cholmondeley's humble opinion.
am I right in thinking that we're not going to be able to make a context-free grammar that can generate an arbitrary depth of nesting of the correctly punctuated phrases, because we're always going to have to be able to quote one of the punctuated hadⁿ phrases for the start of the second sentence.
I choose not to attempt to write a sentence which can be generate to arbitrary depth by a CFG which plays on the 'had' vs. 'had had' distinction, but I presume it would be a single sentence so as to avoid long range dependencies.
D.O. said,
May 26, 2010 @ 4:32 pm
I very much recommend the following story of abortive recursion that might have happened (Littlewood A Mathematician's Miscellany)
Apparently, Mr. Littlewood was not dyslexic. By the way, it is not quite clear exactly which part of this story didn't happen.
Daevol said,
May 26, 2010 @ 5:24 pm
I know this is a bit of a taboo, but I think ya'll'll find this blog post relevant: The Hello World from Hell
Challenge: transform 'print("Hello World")' into a monster of a Python statement by embedding an additional eval() statement for every character of the phrase.
The backslashes grow exponentially — I had to create an auxiliary program just to generate the source code.
(Why did I do it? Because It Was There, and to cure myself of a backslash phobia)
Rubrick said,
May 26, 2010 @ 5:25 pm
An interesting discussion of this comic and recursion can be found here.
Spectre-7 said,
May 26, 2010 @ 6:32 pm
I'm reminded of my old plan to write a book titled Reading Reading Lolita in Tehran in Tehran, and the shocking exposé that would follow it, Writing Reading Reading Lolita in Tehran in Tehran in San Francisco.
MH said,
May 26, 2010 @ 6:48 pm
I would have found the title text funnier if I hadn't already read something quite similar here on LL about hypothetical "polemics and rejoinders" to "Leave Your Language Alone".
Ben said,
May 26, 2010 @ 8:32 pm
@Eric S, or in ruby:
def q(n); n % 2 == 1 ? '"' : "'"; end
def w(n, s); 0 == n ? s : w(n – 1, "doing #{q n}#{s}#{q n} wrong"); end
puts (0…MAX).map { |i| 'I kept ' + w(i, 'doing it wrong') }.join("\n")
Perhaps not the most elegant, but it works, alternating quotes and all, generating the first MAX sentences.
Army1987 said,
May 27, 2010 @ 3:30 pm
@MH: ‘“GOTO Considered Harmful” Considered Harmful’ Considered Harmful?
Army1987 said,
May 27, 2010 @ 3:31 pm
(The link was intended to point to http://en.wikipedia.org/wiki/Considered_harmful but I mis-copy&pasted.)
Goob said,
May 27, 2010 @ 10:29 pm
Here's an old chestnut you may have heard; my family's version involves my dad.
A long time ago, it was pointed out to my father that there was a movie once, titled "They Shoot Horses, Don't They?" It follows naturally that this makes for a useful tidbit should one ever find themselves in a conversation discussing trends in the qualities of movies. So: my father was waiting for just such a conversation, until one fateful evening sitting around some living room or another, he would be able to turn to his victim and say:
"Well, they shot 'They Shoot Horses, Don't They?' didn't they?"
A decade a ago, a friend of mine who knew this story sidled up to me at a party and asked me in low tones the make sure, at some point during the course of the evening, that I mentioned my father in passing. I had no idea why, and completely forgot to do so, and I didn't. A few weeks later, I asked my friend about it, and he looked at me and said that he had wanted to say:
"Oh! He said 'They shot "They Shoot Horses, Don't They?" didn't they?', didn't he?"
A few years after that, both I and my friend were attending another party, and I was telling this story, except right before delivering the punchline I turned to my friend and said:
"And you were going to say 'He said "They shot 'They Shoot Horses, Don't they?' didn't they?" didn't he?', weren't you?"
At some point after that (and some years ago, now) my father was finally in that magic conversation, and was finally able to turn to his victim and utter that line he'd been saving up for nearly two decades.
And the thing is: the victim didn't get it.
John Cowan said,
May 28, 2010 @ 11:16 am
To turn from recursion to ambiguity, I remember seeing many years ago a list of parodied movie titles in Mad magazine, one of which was "They Shoot Horse, Don't They?"
Sili said,
May 29, 2010 @ 2:28 pm
This is why he shoulda used endnotes instead. I could just have put:
Sili said,
May 29, 2010 @ 2:33 pm
Ah – So <sup> only works in preview. Sorry.
Duncan said,
May 31, 2010 @ 10:23 am
I suspect this is incorrect; this is just one of those instances where the limited space of possible movement limits nesting. It isn't possible to for me to be doing 'doing 'doing 'doing it wrong' wrong' wrong' wrong because there is nothing which it is like to be writing 'unite' when I intend to be writing 'untie' to impersonate someone who is writing 'untie' when they mean to be writing 'unite', emulating someone writing 'untie' when they mean to write 'unite' because this requires me to pretend I'm someone making a mistake in pretending to be someone making a mistake and for whatever reason that's just not possible: 'doing 'doing 'doing 'doing it wrong' wrong' wrong' wrong' is just doing 'doing 'doing it wrong' wrong' right.