Complexity and Randomness revisited

I have posted before (post 1 and post 2) about order, complexity, and randomness. The image above shows the spectrum from organised order to random disorder, with structured complexity somewhere in between. The three textual examples below illustrate the same idea.

Regular Complex Random
AAAAAAAAAA AAAAAAAAAA AAAAAAAAAA AAAAAAAAAA AAAAAAAAAA AAAAAAAAAA AAAAAAAAAA AAAAAAAAAA AAAAAAAAAA AAAAAAAAAA AAAAAAAAAA AAAAAAAAAA AAAAAAAAAA AAAAAAAAAA AAAAAAAAAA AAAAAAAAAA AAAAAAAAAA AAAAAAAAAA AAAAAAAAAA AAAAAAAAAA AAAAAAAAAA … It was the best of times, it was the worst of times, it was the age of wisdom, it was the age of foolishness, it was the epoch of belief, it was the epoch of incredulity, it was the season of Light, it was the season of Darkness, it was the spring of hope, it was the winter of despair, … ShrfT e6IJ5 eRU5s nNcat qnI8N m-cm5 seZ6v 5GeYc w2jpg Vp5Lx V4fR7 hhoc- 81ZHi 5qntn ErQ2- uv3UE MnFpy rLD0Y DI3GW p23UF FQwl1 BgP36 RK6Gb 6lpzR nV03H W5X3z 2f1u8 OgpXy tY-6H HkwEU s0xLN 9W8H …

These three examples, and many intermediate cases, can be distinguished by the amount of information they contain. The leading way of measuring that information is with Kolmogorov complexity. The Kolmogorov complexity of a block of text is the length of the shortest program producing that text. Kolmogorov complexity is difficult to calculate in practice, but an approximation is the size of the compressed file produced by good compression software, such as 7-Zip. The chart below shows the number of bytes (a byte is 8 bits) for a compressed version of A Tale of Two Cities, a block of the letter ‘A’ repeated to the same length, and a block of random characters of the same length:

The random characters are chosen to have 64 possible options, which need 6 bits to describe, so a compression to about 75% of the original size is as expected. The novel by Dickens compresses to 31% of its original size.

But does this chart show information? Grassberger notes that Kolmogorov complexity is essentially just a measure of randomness. On this definition, random-number generators would be the best source of new information – but that’s not what most people mean by “information.”

An improvement is to introduce an equivalence relation “means the same.” We write X ≈ Y if X and Y have the same meaning. In particular, versions of A Tale of Two Cities with different capitalisation have the same meaning. Likewise, all meaningless random sequences have the same meaning. The complexity of a block of text is then the length of the shortest program producing something with the same meaning as that text (i.e. the complexity of X is the length of the shortest program producing some Y with X ≈ Y).

In particular, the complexity of a specific block of random text is the length of the shortest program producing random text (my R program for random text is 263 bytes), and we can approximate the complexity of A Tale of Two Cities by compressing an uppercase version of the novel. This definition of complexity starts to look a lot more like what we normally mean by “information.” The novel contains a large amount of information, while random sequences or “AAAAA…” contain almost none:

Those who hold that information satisfies the rule ex nihilo nihil fit can thus be reassured that random-number generators cannot create new information out of nothing. However, if we combine random-number generators with a selection procedure which filters out anything that “means the same” as meaningless sequences, we can indeed create new information, as genetic algorithms and genetic programming have demonstrated – although Stuart Kauffman and others believe that the evolution of biological complexity also requires additional principles, like self-organisation.


World Solar Challenge 2019: even more charts

Adding to my earlier list of World Solar Challenge distance/speed plots, here are 8 more (mostly circulated previously on Twitter). Night stops and notable events are marked on the bottom of each chart in a highlight colour. Control stops are in black.

Michigan traditionally comes third in the World Solar Challenge. They were third again this year. Their chart shows no drama, just fast, steady racing.

Control stop times for Michigan: Katherine: Sunday 12:29:00, Daly Waters: Sunday 16:08:02, Tennant Creek: Monday 12:13:30, Barrow Creek: Monday 15:14:24, Alice Springs: Tuesday 10:02:07, Kulgera: Tuesday 13:42:10, Coober Pedy: Wednesday 10:25:19, Glendambo: Wednesday 14:21:01, Port Augusta: Thursday 9:14:26, Adelaide: Thursday 14:56:00.

Western Sydney, in their beautiful car Unlimited 3.0, battled electrical issues, motor problems, and a wind gust that finally took them out. They still found time to help out Sonnenwagen Aachen on the road south. The photograph in the chart is mine.

Control stop times for Western Sydney: Katherine: Sunday 12:55:00, Daly Waters: Sunday 16:59:06, Tennant Creek: Tuesday 11:51:31.

There was no such drama for ETS Quebec (Éclipse), just steady consistent driving, finishing as best Canadian team, 2th North American team, and 9th in the world. That’s why they received my consistency gem.

Control stop times for Éclipse: Katherine: Sunday 13:27:04, Daly Waters: Monday 8:55:47, Tennant Creek: Monday 16:08:23, Barrow Creek: Tuesday 11:13:27, Alice Springs: Tuesday 16:10:27, Kulgera: Wednesday 11:59:00, Coober Pedy: Thursday 9:48:25, Glendambo: Thursday 13:56:55, Port Augusta: Friday 9:32:09, Adelaide: Friday 14:21:48.

Swedish team Jönköping University (JU) also had plenty of drama. They were forced to stop under cloudy skies with a flat battery and they needed an overnight repair. But they still finished tenth!

Control stop times for JU: Katherine: Sunday 12:51:56, Daly Waters: Monday 8:07:49, Tennant Creek: Monday 14:31:05, Barrow Creek: Tuesday 9:41:27, Alice Springs: Tuesday 14:13:37, Kulgera: Wednesday 12:39:00, Coober Pedy: Thursday 9:53:47, Glendambo: Thursday 13:51:40, Port Augusta: Friday 10:04:55, Adelaide: Friday 14:44:20.

Antakari had a smooth and largely uneventful race, apart from a couple of stops of a few minutes each. The GPS track shows them hunting around for a good campsite each night. They finished 7th (just ahead of NITech).

Control stop times for Antakari: Katherine: Sunday 13:15:43, Daly Waters: Monday 8:56:38, Tennant Creek: Monday 15:06:40, Barrow Creek: Tuesday 9:55:51, Alice Springs: Tuesday 14:17:59, Kulgera: Wednesday 10:34:05, Coober Pedy: Thursday 8:45:34, Glendambo: Thursday 12:58:06, Port Augusta: Friday 8:33:08, Adelaide: Friday 13:07:11.

Nagoya Institute of Technology (NITech) also had a smooth and largely uneventful race, finishing 8th (just behind Antakari).

Control stop times for NITech: Katherine: Sunday 12:56:50, Daly Waters: Monday 8:06:31, Tennant Creek: Monday 14:42:02, Barrow Creek: Tuesday 9:38:31, Alice Springs: Tuesday 14:40:56, Kulgera: Wednesday 10:22:50, Coober Pedy: Thursday 8:45:20, Glendambo: Thursday 13:01:29, Port Augusta: Friday 8:38:35, Adelaide: Friday 13:24:10.

The team from Durham University crossed Australia on solar power, in spite of minor electrical problems (they are the first UK team to do so for many years). Unfortunately they only managed around 2830 km, not quite reaching Adelaide. In the past, cars have been permitted to drive on Saturday mornings, whereas this year, cars had to cease driving on Friday evening. Judging from the graph, Durham might not have realised this for the first few days.

Control stop times for Durham: Katherine: Sunday 14:26:58, Daly Waters: Monday 10:34:22, Tennant Creek: Tuesday 9:39:42, Barrow Creek: Tuesday 13:45:32, Alice Springs: Wednesday 10:53:29, Kulgera: Wednesday 15:59:45, Coober Pedy: Thursday 14:36:36, Glendambo: Friday 10:01:30, Port Augusta: Friday 14:42:19.

Swedish newcomers Chalmers Solar Team managed two control stops, but were slowed significantly by the hilly terrain in the first part of the route. They therefore trailered at around 735 km.

Control stop times for Chalmers: Katherine: Sunday 14:56:54, Daly Waters: Monday 12:49:32.


Something is going on with the primes…

The chart below illustrates the Erdős–Kac theorem. This relates to the number of distinct prime factors of large numbers (integer sequence A001221 in the On-Line Encyclopedia):

Number No. of prime factors No. of distinct prime factors
1 0 0
2 (prime) 1 1
3 (prime) 1 1
4 = 2×2 2 1
5 (prime) 1 1
6 = 2×3 2 2
7 (prime) 1 1
8 = 2×2×2 3 1
9 = 3×3 2 1
10 = 2×5 2 2
11 (prime) 1 1
12 = 2×2×3 3 2
13 (prime) 1 1
14 = 2×7 2 2
15 = 3×5 2 2
16 = 2×2×2×2 4 1

The Erdős–Kac theorem says that, for large numbers n, the number of distinct prime factors of numbers near n approaches a normal distribution with mean and variance log(log(n)), where the logarithms are to the base e. That seems to be saying that prime numbers are (in some sense) randomly distributed, which is very odd indeed.

In the chart, the observed mean of 3.32 is close to log(log(109)) = 3.03, although the observed variance of 1.36 is smaller. The sample in the chart includes 17 numbers with 8 distinct factors, including 1,000,081,530 = 2×3×3×5×7×19×29×43×67 (9 factors, 8 of which are distinct).

The Erdős–Kac theorem led to an episode where, following the death of Paul Erdős in 1996, Carl Pomerance spoke about the theorem at a conference session in honour of Erdős in 1997. Quoting Albert Einstein (“God does not play dice with the universe”), Pomerance went on to say that he would like to think that Erdős and [Mark] Kac replied “Maybe so, but something is going on with the primes.” The quote is now widely misattributed to Erdős himself.


World Solar Challenge 2019 Revisited: some additional charts

Revisiting the World Solar Challenge, the chart below shows distance/speed plots for seven WSC teams (for other teams I was either missing some GPS data, or did not have access to explanatory social media). Distances shown are road distances (not geodesic), while speeds are estimated from distance and time information (because speeds were not included in the GPS data that was kindly supplied to me). As a result of data limitations, the compulsory 30-minute stops at Katherine etc. are shown by sharp speed dips, but not necessarily ones that drop all the way to zero.

Vattenfall (3) had a devastating battery fire; Top Dutch (6) were the best new team, finishing 4th; Agoria (8) won the Challenger class; Twente (21) tragically crashed while in the lead; Sonnenwagen Aachen (70) were one of two teams to come back from a serious crash and still finish; Blue Sky (77) were the 11th and last Challenger team to reach Adelaide on solar power; and Kogakuin (88) were the other team to recover from a major crash.

Night stops in the chart above are marked in red. Photos are from their tweet posted minutes before the fire and from a tweet posted shortly afterwards.

Control stop times for Vattenfall: Katherine: Sunday 12:19:21, Daly Waters: Sunday 15:59:21, Tennant Creek: Monday 11:45:23, Barrow Creek: Monday 14:51:01, Alice Springs: Tuesday 9:30:33, Kulgera: Tuesday 12:51:41, Coober Pedy: Wednesday 8:39:31, Glendambo: Wednesday 12:40:58, Port Augusta: Wednesday 16:44:32.

The chart shows Top Dutch’s multiple stops just out of Tennant Creek with battery problems. Top Dutch finished 4th, and won the WSC Excellence in Engineering Award.

Control stop times for Top Dutch: Katherine: Sunday 12:16:27, Daly Waters: Sunday 15:57:03, Tennant Creek: Monday 12:12:55, Barrow Creek: Monday 15:28:35, Alice Springs: Tuesday 10:39:32, Kulgera: Tuesday 14:41:40, Coober Pedy: Wednesday 12:00:43, Glendambo: Wednesday 15:48:50, Port Augusta: Thursday 10:47:39, Adelaide: Thursday 15:30:00.

Night stops in the chart above are marked in blue. Agoria had a virtually perfect race, winning the Challenger class. Visible in the chart after Coober Pedy is the 80 km/h speed limit imposed by the WSC on Wednesday morning after wind gusts caused multiple crashes.

Control stop times for Agoria: Katherine: Sunday 12:17:04, Daly Waters: Sunday 16:05:54, Tennant Creek: Monday 11:55:56, Barrow Creek: Monday 14:56:40, Alice Springs: Tuesday 9:46:28, Kulgera: Tuesday 13:10:50, Coober Pedy: Wednesday 9:22:36, Glendambo: Wednesday 13:05:06, Port Augusta: Wednesday 16:51:59, Adelaide: Thursday 11:52:42.

Twente’s tragic crash (due to a strong wind gust) occurred at about 2165 km from Darwin, just before Coober Pedy. Photos are from a tweet posted the day before the crash and from a tweet posted shortly afterwards. I was one of the people that signed the car after the crash. Twente won the Promotional Award, for their excellent media.

Control stop times for Twente: Katherine: Sunday 12:08:43, Daly Waters: Sunday 15:32:39, Tennant Creek: Monday 11:33:01, Barrow Creek: Monday 14:31:33, Alice Springs: Tuesday 9:17:16, Kulgera: Tuesday 12:40:40.

Sonnenwagen Aachen stopped for five hours to repair their car on Wednesday, just before Coober Pedy, after the car was blown off the road (their first priority was the driver, of course). There was another stop between Glendambo and Port Augusta, due to a broken shock absorber that had been damaged in the crash (Western Sydney Solar Team kindly helped get them back on the road). Sonnenwagen Aachen finished 6th. They also won the Safety Award and and the Spirit of the Event Award (for not giving up).

Control stop times for Sonnenwagen Aachen: Katherine: Sunday 12:27:34, Daly Waters: Sunday 16:09:06, Tennant Creek: Monday 12:17:32, Barrow Creek: Monday 15:12:27, Alice Springs: Tuesday 9:52:06, Kulgera: Tuesday 13:31:00, Coober Pedy: Wednesday 15:08:20, Glendambo: Thursday 9:35:27, Port Augusta: Thursday 14:49:06, Adelaide: Friday 10:03:48.

Blue Sky (Toronto) had several brief stops of a few minutes (including for electrical issues on Monday), but no particularly dramatic events. They were also slowed somewhat by clouds on Wednesday morning. Blue Sky finished 11th (the last Challenger team to reach Adelaide on solar power).

Control stop times for Blue Sky: Katherine: Sunday 12:49:29, Daly Waters: Monday 8:03:38, Tennant Creek: Monday 14:42:34, Barrow Creek: Tuesday 9:54:44, Alice Springs: Tuesday 14:23:40, Kulgera: Wednesday 11:00:30, Coober Pedy: Thursday 10:34:55, Glendambo: Thursday 15:01:18, Port Augusta: Friday 10:53:25, Adelaide: Friday 15:47:10.

Kogakuin was forced to stop with an overheated motor just after Katherine. They also crashed twice due to strong winds. The second, more serious, crash was due to a mini-tornado or willy-willy just before Glendambo (see their report here), and required overnight repair in town on Wednesday night. Kogakuin finished 5th. They won the CSIRO Technical Innovation Award, for their hydropneumatic suspension. Their dramatic after-race video is here.

Control stop times for Kogakuin: Katherine: Sunday 12:18:43, Daly Waters: Monday 8:03:13, Tennant Creek: Monday 13:16:26, Barrow Creek: Monday 16:15:52, Alice Springs: Tuesday 11:03:53, Kulgera: Tuesday 14:32:15, Coober Pedy: Wednesday 12:04:23, Glendambo: Thursday 9:45:18, Port Aug: Thursday 14:18:47, Adelaide: Friday 9:53:00.

For comparison, here is the distance/time chart I did before. In that analysis, higher means slower, and the arrival times (in Darwin time) can be read out on the right:


Quantum supremacy – or not?

Google recently published a paper in Nature entitled “Quantum supremacy using a programmable superconducting processor.” They claim to have used 53 qubits to solve a task that would take about 10,000 years on a classical supercomputer.

Some caution seems necessary in interpreting this claim, however. First, it does not refer to any of the practical tasks that people would like quantum computers to solve. And second, IBM claims that 2.5 days is a more realistic estimate for the time required on a classical supercomputer. It does seem that “quantum supremacy” is not quite here yet (see also what Scott Aaronson has to say).


Photo: IBM 50-qubit quantum computer (credit: Ian Hughes, 2018)