1155: Kolmogorov Directions

2026-04-11T16:45:20Z

2A00:23C8:3309:F01:B6BA:C0A4:6A89:9FA4: /* Explanation */ This comic was already linked just a few lines above

{{comic
| number = 1155
| date = January 2, 2013
| title = Kolmogorov Directions
| image = kolmogorov directions.png
| titletext = People get really grumpy when they realize you're giving them directions for how to go to the store and buy a GPS.
}}

==Explanation==
{{w|Andrey Kolmogorov}} was a mathematician who worked, among other things, on defining computational complexity. Roughly speaking, the {{w|Kolmogorov complexity}} of a string (of bits, words, symbols, etc.) is the shortest description that allows an accurate reconstruction — or, in some variants, the length of the smallest program which will output the original string.

[[Cueball]]'s method of giving directions is very reminiscent of Kolmogorov's method of determining complexity. However, it is unlikely they know all the presidents, nor can calculate prime numbers in their heads, and so will have trouble with certain parts. These directions may have minimal Kolmogorov complexity, but they are non-intuitive and are likely not the shortest or quickest way to get there, considering that they consist mostly of left turns.

For most routes the shortest algorithm will very likely be based on some {{w|Maze-solving algorithm}} which is guaranteed to eventually visit every place and follow it until you reach your destination. This might take a very long time (for example, it is possible that the algorithm will have you travel through all of Canada first for a trip between two US cities).

This is [[783: I Don't Want Directions|not the first time]] Cueball has had difficulties with directions, and here we see he hates giving directions as much as he hates receiving them.

The joke in the title text is that Cueball just sent his friend to a store to buy a GPS device to give him the correct directions. (By the time this comic was published, GPS-enabled smartphones had already largely displaced dedicated GPS devices,<ref>https://www.nytimes.com/2010/11/15/technology/15iht-navigate.html</ref> but Cueball could be talking to a person who does not wish to own a smartphone.)

==Transcript==
:[Cueball on the phone.]
:Phone: How do I get to your place from Lexington?
:Cueball: Hmm...
:Cueball: Ok, starting from your driveway, take every left turn that doesn't put you on a prime-numbered highway or street named for a president.

:[Caption below the panel:]
:When people ask for step-by-step directions, I worry that there will be too many steps to remember, so I try to put them in minimal form.

{{comic discussion}}
[[Category:Comics featuring Cueball]]
[[Category:Number theory]]

explain xkcd - User contributions [en]

1155: Kolmogorov Directions