1155: "Kolmogorov Directions"

This forum is for the individual discussion thread that goes with each new comic.

Moderators: Moderators General, Prelates, Magistrates

User avatar
rhomboidal
Posts: 797
Joined: Wed Jun 15, 2011 5:25 pm UTC
Contact:

1155: "Kolmogorov Directions"

Postby rhomboidal » Wed Jan 02, 2013 5:13 am UTC

Image

Title Text: People get really grumpy when they realize you're giving them directions for how to go to the store and buy a GPS.

I'm pretty sure this was also the initial algorithm for Apple Maps.

User avatar
Steve the Pocket
Posts: 705
Joined: Mon Apr 23, 2007 4:02 am UTC
Location: Going downtuuu in a Luleelurah!

Re: 1155: "Kolmogorov Directions"

Postby Steve the Pocket » Wed Jan 02, 2013 5:45 am UTC

Reminds me of that one Dilbert strip where he gives the cashier a weird amount that's higher than the total of his items because, to his engineer mind, it's simpler to make change for it. The cashier is totally stumped as to what he's supposed to do (this was, I guess, before cash registers that could tally up the change for you).
cephalopod9 wrote:Only on Xkcd can you start a topic involving Hitler and people spend the better part of half a dozen pages arguing about the quality of Operating Systems.

Baige.

User avatar
Quicksilver
Posts: 437
Joined: Wed Apr 29, 2009 6:21 am UTC

Re: 1155: "Kolmogorov Directions"

Postby Quicksilver » Wed Jan 02, 2013 5:46 am UTC

"Named for a president" and not "Named after a president?" What's that about?

User avatar
BAReFOOt
Posts: 179
Joined: Mon Jul 19, 2010 7:48 am UTC

Re: 1155: "Kolmogorov Directions"

Postby BAReFOOt » Wed Jan 02, 2013 5:54 am UTC

Why would you give them anything other than GPS coordinates via IM, e-mail, or something similar?

Or a map link. With url shorteners, that even works over the phone.

User avatar
poxic
Eloquently Prismatic
Posts: 4751
Joined: Sat Jun 07, 2008 3:28 am UTC
Location: Left coast of Canada

Re: 1155: "Kolmogorov Directions"

Postby poxic » Wed Jan 02, 2013 6:09 am UTC

Because your grandparents don't have (or want) that kind of stuff.
A man who is 'ill-adjusted' to the world is always on the verge of finding himself. One who is adjusted to the world never finds himself, but gets to be a cabinet minister.
- Hermann Hesse, novelist, poet, Nobel laureate (2 Jul 1877-1962)

User avatar
phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: 1155: "Kolmogorov Directions"

Postby phlip » Wed Jan 02, 2013 6:23 am UTC

To answer the inevitable question: this is from Kolmogorov complexity, which is the idea that a message that can be produced by a very short algorithm is simpler (and contains less information) than a message that requires a much longer algorithm to generate (ie a message that cannot be compressed well). Our protagonist in the comic has found a route for the other character to take which can be compressed very well, so it has low Kolmogorov complexity - as the description he gives is much shorter than a full list of directions. Of course, there's a difference between being well-compressed and being useful...

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

ijuin
Posts: 1110
Joined: Fri Jan 09, 2009 6:02 pm UTC

Re: 1155: "Kolmogorov Directions"

Postby ijuin » Wed Jan 02, 2013 6:40 am UTC

The problem with data compression in this sense is that decompressing it and processing the algorithm into a useful form may require far more processing time than simply transmitting the final processed output. In other words, you spend more time extracting the meaning from the instructions than you save by compressing them. This is why such forms of compression are mainly used when storage space or communication bandwidth is at a greater premium than the processor time and runtime memory required to decompress it (e.g. when sending files over a dialup modem or other very slow connection).

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: 1155: "Kolmogorov Directions"

Postby mike-l » Wed Jan 02, 2013 7:25 am UTC

Steve the Pocket wrote:Reminds me of that one Dilbert strip where he gives the cashier a weird amount that's higher than the total of his items because, to his engineer mind, it's simpler to make change for it. The cashier is totally stumped as to what he's supposed to do (this was, I guess, before cash registers that could tally up the change for you).

I do this all the time and always get funny looks. Most people will pay the exact change amount if they can, and failing that will pay the pennies to avoid getting pennies back, but when I give an extra nickle to get a dime instead of a nickle (thus reducing the change in my pocket by 1) it confuses people.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

User avatar
TheGrammarBolshevik
Posts: 4878
Joined: Mon Jun 30, 2008 2:12 am UTC
Location: Going to and fro in the earth, and walking up and down in it.

Re: 1155: "Kolmogorov Directions"

Postby TheGrammarBolshevik » Wed Jan 02, 2013 7:34 am UTC

phlip wrote:To answer the inevitable question: this is from Kolmogorov complexity, which is the idea that a message that can be produced by a very short algorithm is simpler (and contains less information) than a message that requires a much longer algorithm to generate (ie a message that cannot be compressed well). Our protagonist in the comic has found a route for the other character to take which can be compressed very well, so it has low Kolmogorov complexity - as the description he gives is much shorter than a full list of directions. Of course, there's a difference between being well-compressed and being useful...

TBH, as someone who gets to most places by a combination of public transportation and walking I would find this very useful. I have a bad habit of "memorizing" parts of directions that seem too tedious to write down, only to find that I've forgotten key items when I actually need to figure out where I'm going. If I could really get my trip down to "every left except primes and presidents," it would make it a lot easier to memorize my route. And, at walking speed, it's not at all inconvenient to ask whether a street sign is prime when I see it up ahead.

Of course, it would probably be easier to just resolve to write things down properly, but if I'm not doing that anyway I could see the usefulness of a mnemonic like this.
Nothing rhymes with orange,
Not even sporange.

User avatar
Davidy
Posts: 221
Joined: Sat Dec 01, 2012 1:18 am UTC

Re: 1155: "Kolmogorov Directions"

Postby Davidy » Wed Jan 02, 2013 7:49 am UTC

An example of extreme simplicity in directions for solving a very complicated problem is in finding ones way through a maze - simply continue walking, keeping your right hand on a wall and you will eventually reach the exit.
"It's only funny until someone loses an eye, then it's still funny but they can only see it in 2-D."

User avatar
da Doctah
Posts: 985
Joined: Fri Feb 03, 2012 6:27 am UTC

Re: 1155: "Kolmogorov Directions"

Postby da Doctah » Wed Jan 02, 2013 7:55 am UTC

Quicksilver wrote:"Named for a president" and not "Named after a president?" What's that about?
You also have to trust that they know "Lincoln Avenue" was named after early local settler Jeremiah Lincoln.

Yerushalmi
Posts: 22
Joined: Wed Jan 02, 2013 8:17 am UTC

Re: 1155: "Kolmogorov Directions"

Postby Yerushalmi » Wed Jan 02, 2013 8:28 am UTC

At some point while living in my old apartment I noticed that it had a very amusing location in Jerusalem. Whenever someone would stop me outside my apartment and ask how to leave the city and get to Tel Aviv, I'd ask them, "Do you want the short way or the simple way?" The short way was rather complicated - turn left here, another left at the light, a right at the next light, etc. - but, obviously, short. The simple way was "Make a U-turn, and then keep going straight until you get to Tel Aviv." (Somehow, they invariably asked me when their car was pointing in the opposite direction from the simple way.) The simple way would take you in loops and circles around the city for a while until suddenly you found yourself on Route 1, pointing towards Tel Aviv.

Human nature being what it is, nobody was EVER able to resist asking me what both sets of directions were. Interestingly, only once in the entire four years I lived there did anybody actually choose the simple way.

leapoffaith28
Posts: 2
Joined: Wed Jan 02, 2013 8:32 am UTC

Re: 1155: "Kolmogorov Directions"

Postby leapoffaith28 » Wed Jan 02, 2013 8:33 am UTC

I have registered to ask..

Steve, where is the original post in your sig? :D

Oh, great comic too.

User avatar
orthogon
Posts: 3079
Joined: Thu May 17, 2012 7:52 am UTC
Location: The Airy 1830 ellipsoid

Re: 1155: "Kolmogorov Directions"

Postby orthogon » Wed Jan 02, 2013 9:24 am UTC

Did he optimise the route, then compress the directions? Or did he jointly optimise both?
xtifr wrote:... and orthogon merely sounds undecided.

Arariel
Posts: 404
Joined: Fri Sep 17, 2010 2:32 am UTC

Re: 1155: "Kolmogorov Directions"

Postby Arariel » Wed Jan 02, 2013 9:33 am UTC

Davidy wrote:An example of extreme simplicity in directions for solving a very complicated problem is in finding ones way through a maze - simply continue walking, keeping your right hand on a wall and you will eventually reach the exit.

A maze with walls that form a square somewhere within it (or other close-ended shape). You put your right hand on it, you'll walk around in a circle.

OP Tipping
Posts: 258
Joined: Thu Dec 13, 2007 6:23 am UTC

Re: 1155: "Kolmogorov Directions"

Postby OP Tipping » Wed Jan 02, 2013 10:02 am UTC

Reminds me of that one Dilbert strip where he gives the cashier a weird amount that's higher than the total of his items because, to his engineer mind, it's simpler to make change for it. The cashier is totally stumped as to what he's supposed to do (this was, I guess, before cash registers that could tally up the change for you).


I do that all the time. The cashier is usually glad, because he gets a bunch of small change in his float.

"Named for a president" and not "Named after a president?" What's that about


It is a perfectly common expression.

Why would you give them anything other than GPS coordinates via IM, e-mail, or something similar? Or a map link. With url shorteners, that even works over the phone.


Great! Unless the person has never used a computer or a GPS.

Did he optimise the route, then compress the directions? Or did he jointly optimise both?


He didn't optimise the route ... he chose the most compressed directions that got the person to the destination.
a) Please explain the specific MEDICAL reason for ordering this MEDICATION !
b) Please state the nature of your ailment or injury.
c) One a scale of one to ten, how would you rate your pain?
d) Please state the nature of the medical emergency.

blowfishhootie
Posts: 486
Joined: Wed Sep 21, 2011 11:13 pm UTC

Re: 1155: "Kolmogorov Directions"

Postby blowfishhootie » Wed Jan 02, 2013 10:04 am UTC

Quicksilver wrote:"Named for a president" and not "Named after a president?" What's that about?


Maybe it's about your English language deficiencies? I'm not sure the sentence could be any clearer. If the phrasing is at all problematic, then how did you know it meant the same thing as "named after" anyway?

Carlomagno
Posts: 75
Joined: Fri May 20, 2011 6:23 pm UTC

Re: 1155: "Kolmogorov Directions"

Postby Carlomagno » Wed Jan 02, 2013 10:04 am UTC

I think people in this thread are missing that the route itself is probably inefficient; it just so happens that the simplified directions are highly compressed.

gazdinf
Posts: 1
Joined: Wed Jan 02, 2013 10:03 am UTC

Re: 1155: "Kolmogorov Directions"

Postby gazdinf » Wed Jan 02, 2013 10:06 am UTC

Actually you cannot buy "a GPS", unless the United States government decides to sell all the satellites, etc...
You can only by GPS based navigation systems. :)

User avatar
ElWanderer
Posts: 293
Joined: Mon Dec 12, 2011 5:05 pm UTC

Re: 1155: "Kolmogorov Directions"

Postby ElWanderer » Wed Jan 02, 2013 10:12 am UTC

Quicksilver wrote:"Named for a president" and not "Named after a president?" What's that about?

It's a difference between American English and English. In the US, the former construction is "right", though in the UK we generally never use it and it sounds wrong to our ears.
Now I am become Geoff, the destroyer of worlds

User avatar
orthogon
Posts: 3079
Joined: Thu May 17, 2012 7:52 am UTC
Location: The Airy 1830 ellipsoid

Re: 1155: "Kolmogorov Directions"

Postby orthogon » Wed Jan 02, 2013 11:02 am UTC

Davidy wrote:An example of extreme simplicity in directions for solving a very complicated problem is in finding ones way through a maze - simply continue walking, keeping your right hand on a wall and you will eventually reach the exit.

In the UK you have to use your left hand instead :P
xtifr wrote:... and orthogon merely sounds undecided.

User avatar
alvinhochun
Posts: 54
Joined: Wed Nov 14, 2012 3:07 pm UTC

Re: 1155: "Kolmogorov Directions"

Postby alvinhochun » Wed Jan 02, 2013 12:15 pm UTC

I'm sure he will finally realize that he is stuck in an endless loop.

blowfishhootie
Posts: 486
Joined: Wed Sep 21, 2011 11:13 pm UTC

Re: 1155: "Kolmogorov Directions"

Postby blowfishhootie » Wed Jan 02, 2013 12:18 pm UTC

alvinhochun wrote:I'm sure he will finally realize that he is stuck in an endless loop.


If you are talking about the comic, that is possible but not necessarily true. Making left turns over and over would be an infinite loop if you never stopped, but if your destination were somewhere along that route, there's nothing saying you can't stop at it.

LtPowers
Posts: 38
Joined: Fri Sep 07, 2012 4:02 pm UTC

Re: 1155: "Kolmogorov Directions"

Postby LtPowers » Wed Jan 02, 2013 1:33 pm UTC

Davidy wrote:An example of extreme simplicity in directions for solving a very complicated problem is in finding ones way through a maze - simply continue walking, keeping your right hand on a wall and you will eventually reach the exit.


Only if the maze is two-dimensional and the entrance and exit are both along the outer wall.


Powers &8^]

mfc
Posts: 14
Joined: Fri Jan 16, 2009 9:25 pm UTC

Re: 1155: "Kolmogorov Directions"

Postby mfc » Wed Jan 02, 2013 1:46 pm UTC

Grumble .. it would have been so much better if titled " Kolmogorov-Chaitin Directions" ... Greg's contribution was more relevant to the cartoon, I would suggest.

JudeMorrigan
Posts: 1266
Joined: Tue Jan 26, 2010 1:26 pm UTC

Re: 1155: "Kolmogorov Directions"

Postby JudeMorrigan » Wed Jan 02, 2013 2:09 pm UTC

OP Tipping wrote:
Reminds me of that one Dilbert strip where he gives the cashier a weird amount that's higher than the total of his items because, to his engineer mind, it's simpler to make change for it. The cashier is totally stumped as to what he's supposed to do (this was, I guess, before cash registers that could tally up the change for you).

I do that all the time. The cashier is usually glad, because he gets a bunch of small change in his float.

It depends on the values in question, in my experience. If, for example, I give the cashier $10.03 for a $5.03 order, it's all good. Alternately, if I give the cashier $10.08 for a $5.83 order, it is far more likely to require a "trust me".

User avatar
thevicente
Posts: 119
Joined: Fri Jan 29, 2010 3:19 pm UTC

Re: 1155: "Kolmogorov Directions"

Postby thevicente » Wed Jan 02, 2013 2:48 pm UTC

leapoffaith28 wrote:I have registered to ask..

Steve, where is the original post in your sig? :D

Oh, great comic too.



I belive it was http://xkcd.com/528/

User avatar
mathmannix
Posts: 1446
Joined: Fri Jul 06, 2012 2:12 pm UTC
Location: Washington, DC

Re: 1155: "Kolmogorov Directions"

Postby mathmannix » Wed Jan 02, 2013 2:49 pm UTC

leapoffaith28 wrote:I have registered to ask..

Steve, where is the original post in your sig? :D

Oh, great comic too.


Ooh, I can answer this one!

http://forums.xkcd.com/viewtopic.php?f=7&t=32997&p=1306377#p1306377

[although I did get sniped a bit...]
I hear velociraptor tastes like chicken.

User avatar
orthogon
Posts: 3079
Joined: Thu May 17, 2012 7:52 am UTC
Location: The Airy 1830 ellipsoid

Re: 1155: "Kolmogorov Directions"

Postby orthogon » Wed Jan 02, 2013 3:01 pm UTC

JudeMorrigan wrote:... If, for example, I give the cashier $10.03 for a $5.03 order, it's all good. Alternately, if I give the cashier $10.08 for a $5.83 order, it is far more likely to require a "trust me".

Woah, until you nerd-sniped me with that example I hadn't thought about how much more interesting this type of activity is made by the existence of the quarter. In currencies with a 1,2,5 system you can deal with the units first then work up to the tens. But the quarter couples the tens into the units in a nontrivial way.
xtifr wrote:... and orthogon merely sounds undecided.

User avatar
cellocgw
Posts: 2055
Joined: Sat Jun 21, 2008 7:40 pm UTC

Re: 1155: "Kolmogorov Directions"

Postby cellocgw » Wed Jan 02, 2013 3:17 pm UTC

Steve the Pocket wrote:Reminds me of that one Dilbert strip where he gives the cashier a weird amount that's higher than the total of his items because, to his engineer mind, it's simpler to make change for it. The cashier is totally stumped as to what he's supposed to do (this was, I guess, before cash registers that could tally up the change for you).


Hey, I've been doing this for ages, before and after cash registers started "helping" the cashiers. Some of them do manage to figure it out.
https://app.box.com/witthoftresume
Former OTTer
Vote cellocgw for President 2020. #ScienceintheWhiteHouse http://cellocgw.wordpress.com
"The Planck length is 3.81779e-33 picas." -- keithl
" Earth weighs almost exactly π milliJupiters" -- what-if #146, note 7

User avatar
cellocgw
Posts: 2055
Joined: Sat Jun 21, 2008 7:40 pm UTC

Re: 1155: "Kolmogorov Directions"

Postby cellocgw » Wed Jan 02, 2013 3:21 pm UTC

Seeing as many years ago (ish), there was an XKCD strip about GPS directions sending him to a ferry port, but since it was midnite the ferry was closed, so he had to drive googol miles around the lake, I would be very suspicious if Randall sent me to a store to get a GPS.
https://app.box.com/witthoftresume
Former OTTer
Vote cellocgw for President 2020. #ScienceintheWhiteHouse http://cellocgw.wordpress.com
"The Planck length is 3.81779e-33 picas." -- keithl
" Earth weighs almost exactly π milliJupiters" -- what-if #146, note 7

User avatar
enumerated powers
Posts: 49
Joined: Fri Dec 17, 2010 10:22 pm UTC
Location: Dayton Ohio USA
Contact:

Re: 1155: "Kolmogorov Directions"

Postby enumerated powers » Wed Jan 02, 2013 3:23 pm UTC

And the probability he will reach the desired destination is either zero or one.
Last edited by enumerated powers on Wed Jan 02, 2013 3:25 pm UTC, edited 1 time in total.

OtherRob
Posts: 17
Joined: Mon Dec 20, 2010 2:52 pm UTC

Re: 1155: "Kolmogorov Directions"

Postby OtherRob » Wed Jan 02, 2013 3:25 pm UTC

phlip wrote:To answer the inevitable question...


Thanks, phlip. That's exactly why I came to the forum today. :D

User avatar
selene
Posts: 14
Joined: Fri Jun 06, 2008 4:27 am UTC

Re: 1155: "Kolmogorov Directions"

Postby selene » Wed Jan 02, 2013 3:33 pm UTC

JudeMorrigan wrote:
OP Tipping wrote:
Reminds me of that one Dilbert strip where he gives the cashier a weird amount that's higher than the total of his items because, to his engineer mind, it's simpler to make change for it. The cashier is totally stumped as to what he's supposed to do (this was, I guess, before cash registers that could tally up the change for you).

I do that all the time. The cashier is usually glad, because he gets a bunch of small change in his float.

It depends on the values in question, in my experience. If, for example, I give the cashier $10.03 for a $5.03 order, it's all good. Alternately, if I give the cashier $10.08 for a $5.83 order, it is far more likely to require a "trust me".


This is why I like the self checkout machines. I can put in $21.08 for a $5.83 order without confusing the cashier and wasting both our time.

However, in my experience those machines are stingy about quarters; they usually give back two dimes and a nickel.

User avatar
Klear
Posts: 1965
Joined: Sun Jun 13, 2010 8:43 am UTC
Location: Prague

Re: 1155: "Kolmogorov Directions"

Postby Klear » Wed Jan 02, 2013 3:42 pm UTC

blowfishhootie wrote:
alvinhochun wrote:I'm sure he will finally realize that he is stuck in an endless loop.


If you are talking about the comic, that is possible but not necessarily true. Making left turns over and over would be an infinite loop if you never stopped, but if your destination were somewhere along that route, there's nothing saying you can't stop at it.


Or it can lead you to a cul-de-sac.

User avatar
cellocgw
Posts: 2055
Joined: Sat Jun 21, 2008 7:40 pm UTC

Re: 1155: "Kolmogorov Directions"

Postby cellocgw » Wed Jan 02, 2013 4:31 pm UTC

blowfishhootie wrote:
alvinhochun wrote:I'm sure he will finally realize that he is stuck in an endless loop.


If you are talking about the comic, that is possible but not necessarily true. Making left turns over and over would be an infinite loop if you never stopped, but if your destination were somewhere along that route, there's nothing saying you can't stop at it.


You've never driven in Boston and Cambridge, I bet. You can take two lefts and find yourself going in the same direction as you started out. Or five rights and lost in Brookline.
https://app.box.com/witthoftresume
Former OTTer
Vote cellocgw for President 2020. #ScienceintheWhiteHouse http://cellocgw.wordpress.com
"The Planck length is 3.81779e-33 picas." -- keithl
" Earth weighs almost exactly π milliJupiters" -- what-if #146, note 7

blowfishhootie
Posts: 486
Joined: Wed Sep 21, 2011 11:13 pm UTC

Re: 1155: "Kolmogorov Directions"

Postby blowfishhootie » Wed Jan 02, 2013 4:47 pm UTC

cellocgw wrote:
blowfishhootie wrote:
alvinhochun wrote:I'm sure he will finally realize that he is stuck in an endless loop.


If you are talking about the comic, that is possible but not necessarily true. Making left turns over and over would be an infinite loop if you never stopped, but if your destination were somewhere along that route, there's nothing saying you can't stop at it.


You've never driven in Boston and Cambridge, I bet. You can take two lefts and find yourself going in the same direction as you started out. Or five rights and lost in Brookline.


What?

The poster I quoted said the person in the comic was providing directions to an infinite loop. Just because there is some example somewhere of where this might be true doesn't mean it is automatically the case. I don't care about left turns in Boston or Cambridge.

User avatar
San Fran Sam
Posts: 228
Joined: Tue Nov 15, 2011 5:54 pm UTC

Re: 1155: "Kolmogorov Directions"

Postby San Fran Sam » Wed Jan 02, 2013 5:21 pm UTC

LtPowers wrote:
Davidy wrote:An example of extreme simplicity in directions for solving a very complicated problem is in finding ones way through a maze - simply continue walking, keeping your right hand on a wall and you will eventually reach the exit.


Only if the maze is two-dimensional and the entrance and exit are both along the outer wall.


Powers &8^]



But it's much less fun. On the other hand, you could end up like Jack Nicolson.

TeddyB
Posts: 5
Joined: Wed Jan 02, 2013 5:51 pm UTC

Re: 1155: "Kolmogorov Directions"

Postby TeddyB » Wed Jan 02, 2013 5:57 pm UTC

Has anyone actually tried to work out where these directions end you up (assuming it's in NYC)?

MakingProgress
Posts: 17
Joined: Wed Jan 02, 2013 7:41 pm UTC

Re: 1155: "Kolmogorov Directions"

Postby MakingProgress » Wed Jan 02, 2013 7:49 pm UTC

LtPowers wrote:Only if the maze is two-dimensional and the entrance and exit are both along the outer wall.


Anyone have an example of a two-dimensional maze with the entrance or exit not along the outer wall ?


Return to “Individual XKCD Comic Threads”

Who is online

Users browsing this forum: No registered users and 41 guests