Thinking About Encryption, Part 2

(En/De plain text entry screen.)

I’ll start out with the easiest and most well-known one – the Caesar Cipher; AKA, the Captain Midnight Decoder Ring code.

The Caesar cipher is a simple substitution algorithm where each letter is shifted a fixed number of positions along the alphabet. It gets its name from Julius Caesar, who is said to have used it for protecting military messages. Below, the upper line is for the plain text letters, and the lower line is what we read to get the cipher text.

Say we use a shift of 5:


In other words, A=F, B=G, C=H, etc.
If our plain text message reads “THIS IS A SUBSTITUTION CIPHER”, the cipher result will be:


To reverse the process, we can either use the lower line for the cipher letters, and read the plain text off the upper line, or we can flip the lines and start from “A” for the cipher line, as follows:


This gives us:



(En/De option selection screen.)

One thing this flipping demonstrates is that the Caesar cipher has a big weakness – flipping the key and reapplying the cipher causes your plain text to come back out. “A=F” relates to “A=V”.

You can pick a shift of 3, and apply the cipher to the plain text more than once:


But this is really the same as applying a shift of 9 one time.

We can “harden” the Caesar cipher a little several different ways. First would be to “flip” the coder ring (i.e. – the lower cipher alphabet line) to go from Z to A.


The second step would be to reverse the plain text before enciphering (or reverse the cipher text afterward).


LYVNUA POUJIJUJKBIK C KU KUVJ (reversed text, flipped ring, shift of 3)

By combining the two methods, we go from 25 possible encryption outputs (not counting A=A), to 4*26-1, or 103 possible outputs (normal unflipped, normal flipped, reversed normal, and reversed flipped).

(The cipher text after applying the options to the algorithm.)

Now, as we look at the various ciphers used throughout history, there are going to be a couple obvious factors for why they were considered adequate at the time, but not any more. In the case of the Caesar cipher, most of Rome’s enemies couldn’t read Latin. Shifting the letters a bit made the resulting message look like it was in a completely different language. The Romans themselves would figure things out very quickly, and in the case of Caesar sending messages to his generals, he WANTED them to read the cipher texts. But, if there were trained spies in the Roman ranks, or if one of Caesar’s Roman enemies wanted to spoil his plans, then this cipher isn’t all that secure.

But, still, if you’re trying to crack a cipher with pencil and paper, having to go through 25 different shifts is going to take time. And, by applying reversed text and a flipped cipher alphabet, that bumps you up to a maximum of 103 trials to see which algorithm and shift value is needed to read the message again. Doing this by hand, on paper, is going to be very time consuming.

(En/De brute force approach to cracking the Caesar cipher.)

However, with modern PCs we can easily apply the cipher algorithm to the cipher text to test every possible combination one at a time and still retrieve the original plain text message in less than a second. Two additional steps can make things even easier. First is to only apply the algorithm to the first 10-30 letters of the message, then when you know which key to apply by visually checking the output, run the algorithm on the entire message with that key (i.e. – normal, flipped ring, shift 6 places).

The other step is to create an array of common 3- and 4- letter words (e.g. – “the”, “this”, “and”, “will”, “for”, “she”, “her”, “was”), and count how often they show up in each combination of letter shifts. While it is possible that a random-looking permutation of letters might include “the” or “to”, only the correctly deciphered text will have the maximum number of hits on the words in the array. Using this array can allow the program to automagically identify a “best-fit” key, or even predict whether the Caesar cipher was used at all to encrypt the plain text. En-De already allows for testing shortened strings for speed, and I’ve just added the short word array test as I write this entry.

A couple other minor points to cover: The simplest form of the algorithm consists of only upper case letters (A-Z), no spaces and no punctuation or digits. And, any attempt to make the letter substitutions look really random just means that there’s more reason to attack the cipher via letter frequencies, which I’ll get into next time, instead of using the brute-force approach.

I also want to mention ROT-13 while I’m at this. I expect that most computer users are at least aware of ROT-13 as a name, while a lot of people have actually used it to hide, or reveal, video game, TV show and movie spoilers. ROT-13 is just another name for the Caesar cipher with a shift of 13 (A=N, B=O, C=P, etc.)

As mentioned above, there are other things we can do to further harden the Caesar cipher, but I’ll get into them later.

The main points to remember now are:
Caesar is a substitution cipher.
It consists of shifting each letter a fixed amount along the alphabet.
It’s used only on upper case letters.
It can be hardened in different ways.
It’s easy to crack as-is via bruteforce.
Almost everyone knows how to use, and break, it.


Subaru Telescope Papercraft

It’s been a while since I made any papercrafts, and I started jonesing for something while I was in the middle of a short break in a contract translation clean-up project. So, I went to the Canon papercrafts site and downloaded the PDF for the Subaru telescope.  The 300:1 scale model is based on the Subaru on Mauna Kea, in Hawai’i. I had some sheets of 0.15 mm and 0.22 mm paper left over from previous projects, and I debated over which to use for the telescope. 0.15 is a little stiffer than regular printer paper, but has the benefit of being easier to fold. 0.22 is getting closer to card stock and stands up better to stress, but is more likely to leave white lines all over given the thickness of the paper compared to the sizes of some of the model details. In the end, I settled on 0.15 mm, but it might have been smarter if I’d printed the PDF twice, once on each set of sheets, and then cherry-picked the correct stiffness depending on the section of the model I was working on.

I didn’t time myself, but I think I spent at least 15 hours over the course of 3 days building this thing. The most time-consuming activities were for cutting out all the pieces, and then gluing the circular walls to the round flats. The instructions suggested gluing one tab from the walls to the disks at a time, then letting it dry before going to the next tab. This is important for keeping the walls vertically straight, and for ensuring that the end of the wall strips will meet up evenly at the end. But, that was boring, and actually it’s kind of difficult to get the paper to curve right to follow the edges of the disks that way. So, I’d glue 3-5 tabs at a time, depending on the sizes of the tabs, and that worked out ok. The toughest sections to work on were the tiny buildings, and the mounting legs for the telescope stage. My hands kept sweating, making the paper soggy, and causing it to not hold the crease lines. Even so, I think the model turned out better than it had any right to.

The finished model is about 6″ tall, and a little under 7″ at its longest. The big shutters do slide open and closed, but the paper for the guide fingers is thin enough that it can bind up, so I just want to leave the shutters open all the time. The top half of the building comes off to reveal the telescope inside, and the scope and main dome can rotate 360 degrees. The telescope can also rotate up and down, but again, the paper is thin enough that I don’t want to handle the scope so much that something tears. If I were to build this papercraft again, I’d want to go at least one grade thicker on the paper.

But, overall, I’m glad I got this out of my system. I’ll show it off to some of my students, and then decide what to do with it long-term. Recommended to astronomy buffs with a lot of patience and dry hands.

Happy Birthday Emil Berliner (May 20)

(From the Google Doodles)

Thinking About Encryption, Part 1

Sigh. I know that what I’m going to write about has been covered by many people who are better at this than I am. But, I do have a few reasons for doing this anyway. First, I’d like to put this information all in one place, rather than my having to hunt through various sources later on when I want to look this stuff up in the future. Second, it would be nice if these blog entries would serve useful for anyone just starting out with encryption as a hobby, and wanting a “one-stop shop”. Third, I am hoping to get enough interest in En/De, my Free Pascal program, to justify setting up a patreon account, and this is how I’m going to go about that. Fourth, I need more material to run on this blog. And, fifth this is how I’m going to put my thoughts together as I add new functions to En/De.

I’ll start with a little vocabulary, with the question, “what’s the difference between a code and a cipher?”

Technically, a “code” is the substitution of one word for another. One of the most famous examples of a code was with the American code talkers during WW I and II. Native Americans used their languages to communicate messages to each other, where certain words were given double meanings. As in “shark” for “destroyer,” and “silver oak leaf” for someone with the rank of lieutenant colonel. That is, a code is a list of words that have hidden meanings specific to the people using them,

Conversely, a cipher can be viewed more as an algorithm for altering the appearance of a given message. More specifically, we can say there are two ways of obscuring the content of a message.

Transposition: Changing the order of the letters in the message.

Substitution: Changing the letters themselves.

nO exemalp efoa t arsnopisitnoc pieh.r
One example of a transposition cipher is to switch the positions of pairs of letters.

Bo fybnqmf pg b tvctujuvujpo djqifs.
An example of a substitution cipher, where every letter is shifted one position right in the alphabet, such that A=B, B=C, C=D, etc.

There aren’t as many transposition ciphers as there are substitution ciphers, and in general transposition ciphers are easier to identify and crack. But, there are ways of “hardening” a cipher, and of course, transposition and substitution ciphers can be combined in various ways to make them even tougher.

For my purposes, I’m only going to talk about ciphers, but some people do use “code” and “cipher” interchangeably. Especially when talking about the Captain Midnight secret decoder ring (i.e. – the Caesar cipher).

A few more phrases to add to the vocabulary:
Plain text: The original, human-readable message.
Cipher text: The (hopefully) unreadable message we get after applying our cipher to the plain text.

Encipher/encrypt: The process of applying a cipher to the plain text to create the cipher text.
Decipher/decrypt: The reverse process to go from the cipher text back to the original plain text.

Cryptanalysis: The study of information systems, which I’m going to use to mean creating and cracking ciphers.

Key: The word, phrase, number string, or look-up table the cipher uses to encipher the plain text, and then is used for the reverse process for deciphering the cipher text.

My goal is to write a program that implements the various public domain ciphers, to both encipher and decipher messages for hobbyists. At the same time, I want En/De capable of cracking these same ciphers for those hobbyists that like cryptography in the way that some people like crossword puzzles and Sudoku. And, if I do get enough interest to justify a patreon account, I’d like to provide cipher texts that you can try to crack yourself.

Ende, Part 2

I’ve long had kind of a love-hate relationship with software forums on the net. When I start a new project (my Java synthesizer) or language (Prolog), I do look for tutorials and online documentation that can help me get started, but most of what does exist is horribly simplified and doesn’t cover much beyond the basic concepts that everyone else teaches in their own tutorials and program examples. I guess one reason for this is that there’s an expectation that more serious programmers will take university courses to learn about the material in much greater depth. Something I don’t have much option for here in Japan. Which is where the forums come in.

Possibly close to 60% of the results of my web searches for answers tend to be identical questions that other people asked in various forums. Unfortunately, the answers those people received are often along the lines of “you’re stupid, don’t be so stupid.” Occasionally, someone will come forward and provide a useful answer to the original poster’s question, which will then guide me to what I want to know.

The problem is that a lot of what people do in code now revolves around large databases, internet interfacing and similar hot topics. I, however, have gravitated towards sound synthesis, logic problems and other oddball stuff. Meaning that I’m not doing what the majority of programmers are. And when I do ask a question in one of the forums, instead of answering my questions, the majority of the respondents (if there are any at all) tend to attack me on a completely unrelated issue. Eventually, I end up giving up, and find the answers myself through pure trial and error.

The latest example of this was with Ende (Encipher/Decipher). I’m working on a module for solving CryptoQuip-type puzzles. These are simple random letter substitution ciphers (A=C, B=Q, C=Z, etc.), and the way to crack them is to look at letter frequency counts. All written languages have “signatures”, i.e. – individual letters, letter combinations, and short 2-letter and 3-letter words that occur more often than others do. For English, the letters occurring most frequently, in descending order are : ETAOIN SHRDLCU. So, what’s necessary for a solver program is to have routines that do frequency counts.

I needed dynamic multidimensional arrays, in order to store a variable number of data points (a short message may only contain ten unique letters and only three 3-letter words, while a short story could have all 26 letters, and a whole slew of 2- and 3-letter words). For this, I found online examples using an array of an array.

TArr2D = array of array of Integer;
TArr1D = array of String;

This is just temporary. I’m leaning more towards using records, or maybe classes. Arrays apparently can only be of one type, so having “T-23” (“t” occurs 23 times in this text) means having a string array variable and an integer array variable. For the moment, I’m using the TArr2D to include the frequency count, and an index value pointing to TArr1D, which stores the “T” and “THE” strings. As I say, I’ll change this later when I get that far. (Ultimately, I’d like at least one more string variable, for holding user-entered text assignments; i.e. – “T=A”, “L=B”, plus the integer for letter counts.)

Ok, so far, so good. I write my code for getting different kinds of character counts, and I have one form, and one unit (a unit is a collection, or a file, of functions and procedures, and the form is the layout definition for a given screen or window) set up for interactively cracking the CryptoQuip. The user types two letters in an “A=B” pattern, and I use an onkeypress event handler to capture the key presses and insert the correct letters into the memo as needed. Takes a while, and there’s still a bug I need to fix, but otherwise, fine.

(En/De quip solver screen.)

The problem was, I calculated the frequency counts all the way up to 5-letter combinations, stored in TArr2D and TArr1D element pairs, and in the main unit I wanted to preload the counts for single letters in the list box before launching the cracker_generic form. But, the cracker_generic form is where the buttons are for switching between unigram, bigram, trigram, quadgram and quintgram frequency counts, and it’s also where the main display function was located. Meaning, I needed to learn how to create global functions and procedures, i.e. – a procedure located in one unit that can be called from a second unit.

Which brings me to units. Pascal treats each file worth of code as a “unit”. And Lazarus forces the “unit” to have a specific format.

unit generic_cracker;

{$mode objfpc}{$H+}




{ Tcracker_generic }

Tcracker_generic = class(TForm)
buttonQuads: TButton;




cracker_generic: Tcracker_generic;


{$R *.lfm}


The first line, “unit generic_cracker;” specifies the start of the file, and gives the unit a unique name (this name has to be different from the actual *.pas file name used to store the file.

“{$mode objfpc}{$H+}” are compiler directives automatically generated by Lazarus when you create a new unit.

“interface” specifies the beginning of the interface block. In all of the online examples I’ve seen, where people do their compiling from the command prompt, “interface” is closed by the “implements” statement. Lazarus, though, closes “interface” with “end;” In essence, “interface” contains the stuff needed by the code in the “implements” section.

“type” is where you put the type declarations for the program (i.e. – my TArr2D and TArr1D).

The next part, with
{ Tcracker_generic }

Tcracker_generic = class(TForm)
buttonQuads: TButton;

is the definition of the form I’m using to display letter frequencies and get user input to crack the cipher. This a class definition derived from the TForm class, and includes all the screen elements (buttons, menu, memo, list) and event handlers for the “generic_cracker” unit and the “Tcracker_generic” form. Note that the part in curly braces ({}) is a comment.

“private” and “public” are where you declare your private and public variables for the new class you’re creating.

“end;” marks the end of the “interface” block.

“var cracker_generic: Tcracker_generic;” creates an object of the new “Tcracker_generic” class.

And then “implementation/end.” is where all the event handlers (onClick, onClose) go, as well as any programmer-specific functions and procedures.

All of the examples I found for specifying global procedures were of the following form:

unit unit1


uses unit2


code that calls global_function(arg list);


unit generic_cracker;


function global_function(arg list): return_type; {make public}


function global_function(arg list): return_type; {Actual code}


Note that I couldn’t find anything in the online examples for unit2 for specifying “type”, “private” or “public”. And I didn’t see anything showing the “interface” block ending with “end;”. So, when I tried to follow those examples, the Lazarus IDE would give me syntax errors. Naturally, I tried asking in the Lazarus forums, and all I got was grief from people telling me that I’m doing it wrong, I don’t understand Pascal, and to go read the manual. The thing is, I did finally get the code to work by doing the following:

unit unit2


TArr2D = array of array of Integer;
TArr1D = array of String;


procedure dispCnts(a1 : TArr2D; a2 : TArr1D);

cracker_generic: Tcracker_generic;


procedure dispCnts(a1 : TArr2D; a2 : TArr1D);


Putting the definition of the global procedure in the same place where cracker_generic is specified works. And this is where I get called names by some of the Free-Pascal forum people.

But, everyone that responded to me gave me examples that compile from the command line. They didn’t seem to have used the Lazarus IDE for program development or compilation, and I’m guessing that Lazarus imposes certain programming restrictions that the command line compiler ignores.

Anyway, I’ve been too busy the last few weeks to return to the forums to argue about this. It’s easier to just vent here in the blog right now. Later, I’ll go back through all the replies and see if my guess is right.

Rhymes With Orange – Escher

This is a nice twist on the theme, from Rhymes With Orange.


Colossal Gardner, ch. 50

And now we reach the last chapter in the book – Six Sensational Discoveries. This is another April Fool’s article that ran in the April 1975 issue of Scientific American, ostensibly as a recap of the top scientific discoveries that “escaped” the attention of the scientific community and the public at large. Martin comments in the addendum that although he’d thought he’d made it pretty obvious that these are all jokes, the editors received over 1,000 letters from people that took them seriously.

(All rights belong to their owners. Images used here for review purposes only. Exploding the four-color-map theorem.)

The first “discovery” by William McGregor is of a map that cannot be colored with fewer than 5 colors. (Some of Gardner’s readers succeeded in coloring the above map with 4 colors.)

The second discovery was in number theory, where e raised to the power of pi times sqrt(163) is an integer. Ramanujan had speculated that it would be, but most calculations by hand were too tedious and no one made it past twelve 9’s after the decimal. John Brillo supposedly applied Euler’s constant to prove the number is exactly 262,537,412,640,768,744. Actually, Ramanujan knew that this number is transcendental, and the next digit after 262,537,412,640,768,743.999999999999 is 2. The name Brillo is a play on John Brillhart.

In the computer sciences, Richard Pinkleaf designed a computer with the help of ex-world-chess champion Mikhail Botvinnik, designated MacHic because it plays like it’s intoxicated. MacHic is a learning machine, and is able to play 1 game against itself every 1.5 seconds. After 7 months of self-play, MacHic declared that pawn to king’s rook 4 is a win for White. Kissinger and Brezhnev were to meet to discuss the impact on world chess, and Bobby Fischer offered to play MacHic as long as it is silent during the game, and he’s guaranteed $25 million, win-or-lose. Gardner writes in the addendum that MacHic is a play on Richard Greenblatt’s MacHack.

(Special relativity – busted!)

For the physical sciences, Humbert Pringle discovered a fatal logical flaw in the special theory of relativity. In his thought experiment, a meter stick is flying through space at a speed so that it is Lorentz-contracted by a factor of 10. Simultaneously, we have a plate with a one-meter diameter hole, and the plate is traveling perpendicular to the stick, so that the two will intersect when the stick is centered in the hole. Both the stick and plate are idealized to have 0 thickness. If the plate is the inertial frame, the stick will be contracted to 10 centimeters and will easily pass through the hole. But, from the stick’s inertial reference frame, the plate’s hole will have a width of 10 cm, and the stick won’t be able to pass through. “The two situations aren’t equivalent, and thus a fundamental assumption in special relativity is violated.” For this one, Pringle is a play on relativity denier Herbert Dingle, and the solution is included in George Gamow’s Mr. Tompkins in Wonderland.

(da Vinci taking a break.)

Discovery five is of two of Leonardo da Vinci’s “lost” notebooks, which include a series of ball bearings surrounding a conical pivot similar to the Sperry Gyroscope invented in the 1920’s; a worm screw; a bicycle with a chain drive, and the first valve flush toilet. (The English patent for the valve flush toilet was granted to Alexander Cummings in 1775, but da Vinci had the idea first.) Really, the artwork here was produced by graphic artist Anthony Ravielli (Ravielli died in 1997 at age 86).

(Making a psi motor.)

Last but best is the psi energy motor constructed in 1973 by Robert Ripoff (if that isn’t a dead-giveaway, nothing is). To construct the motor, cut a rectangle as shown at the top of the figure out of heavy bond paper, 3″x7″. Make two slits as shown, and roll the rectangle into a cylinder and glue the ends together. Using a file card or pasteboard, cut a strip 3/8″x 3″. Insert a needle through the center of the strip, and push the ends of the strip through the slots in the cylinder. Place the assembly on top of a bottle 4″ tall. The bottle must have a glass or hard plastic top.

(Testing the psi motor.)

Set the psi motor on a copy of the Bible or the I Ching, aligning the book’s spine due north-south. Cup your left hand (right if you’re in the southern hemisphere) as close to the motor as possible without touching it. “Make your mind blanker than usual” and concentrate your psi energy on the motor. It can take upwards of one minute for the motor to start turning. If you’re having trouble getting the motor to spin, it helps to lean in closer and breathe shallowly.

(McCullogh and the motor.)

Gardner says that the ripoff motor is a variation of a psychic motor detailed in Hugo Gernsback’s Science and Invention magazine (Nov. 1923). Pictured above is Warren McCulloch as he demonstrates the motor. Interestingly, Gernsback himself had been described as a crook and ripoff artist who often refused to pay his writers, while collecting a $100,000/year salary, so maybe we could have called the above invention the Gernsback motor.


And there we have it. Personally, I’m loving The Colossal Book of Mathematics. There’s a lot of things in here that I hadn’t known before, and when I went through the book several more times for writing up these blog entries, I kept finding new things that had escaped me the first time. Additionally, I ended up reading quite a few wiki articles, and math and science web articles on these topics to see which ones had updates above and beyond what Martin wrote, or as part of the process of adding support links to my blog entries. But, I do have to put this book away now and move on to the next one (I got 6 new books for my birthday (I’m writing this in August, 2 days after my birthday) and I need to finish those before I get any more new books for Christmas. Plus, there’s a very good chance that I’m going to start up writing apps in three different languages (two of the books are for programming in Prolog and for the Android tablet, plus I want to make a decryption program in Free Pascal). I have too many things I want to do…

Final challenge of the week: Following Ripoff’s procedure, construct two psi motors, and turn them into a reciprocating motor for harnessing the free energy that surrounds all of us.

Ok, you now have 50 entries for a Gardner-a-week calendar. Please use them for good; and I definitely recommend buying your own copy of the book – you’ll be glad you did.

Ende, Part 1

I’ve spent two weeks working with Free Pascal so far now, at maybe 2-3 hours a night. And I’ve made some fairly amazing progress in what I consider to be a pretty short period of time. I’ve got the menuing system working ok, which is largely just canned routines built into the GUI code inherent in FP, and auto-generated by Lazarus. Lazarus makes GUI development more-or-less easy. There are so many options for any given screen element that it can get difficult to know if something you want to do is possible or not, and if it is possible, where to find it.

(Lazarus environment, plus the layout for the main En/De screen.)

One example was with memo text. As I mentioned in my previous post, my first practice program is tentatively called Ende (for Encipher/Decipher). It’s going to consist of a series of interrelated windows (called “forms” in this environment) that are all launched from the main form. The main form, in turn, has a menu bar and a memo field. The memo is a simplified text editing element that I’m going to use for entering the plaintext or cipher text data the program is going to act on.

(Memo Lines dialog.)

When you click on an element, the related properties for that element show up in the Object Inspector (right hand panel). The Inspector lets you set the properties and the events that can get triggered via that element (e.g. – onclick, onmouseover, etc.) Most elements have two key properties – Name and Caption. Name assigns the name to be used within the Pascal program. For a button, the default names are Button1, Button2, etc. But that gets confusing fast, so I’ve taken to renaming everything (forms, buttons, menu items) the second I create them (i.e. – buttonAccept, memoMainField, menuFileOpen).

(En/De compiled program main screen.)

The second property, Caption, sets the text that appears somewhere around the element. For buttons, it’s the word (Accept, Cancel, Ok) on the button. For lists, it’s the title that appears at the top left corner of the panel. Usually, the caption defaults to the element name. Now, this was an irritation for me because I wanted to use a memo element, and every time I compiled and ran the program, “Memo1” would show up in the data entry portion of the memo. I could delete or overwrite it, but I couldn’t find out how to remove “Memo1” as the default text for that element. Memos don’t have a Caption property, and changing the name changed the Pascal code, but not the default text. I knew there had to be a way to fix this, and searching Google wasn’t getting me anything useful, so I started walking through the Properties column of the Object Inspector, expanding every single compressed option. This didn’t help me, but I was finally attracted to the Lines property. It didn’t seem to have any specific controls other than just the entry field populated with (TStrings), but I clicked that field anyway, and that gave me the ellipses (…), and clicking those popped-up the Strings Editor Dialog. And THAT showed me the “Memo1” text. Cleaning out the Strings Editor Dialog gave me an empty memo box on program start-up, which is what I wanted.

As an IDE, Lazarus is very powerful. But, some stuff does require a certain amount of hunting to figure out.

GEB answers

GEB answers:
Puzzle 1: What’s the smallest positive integer that can be expressed as the sum of two different squares in two different ways?
Answer: 50
5^2 + 5^2 or 1^2 + 7^2

Puzzle 2: Is “MU” a theorem of the MIU system?
Answer: No

The problem is that the only way to introduce “U” to the existing theorem is to either add it to the end of a string ending in “I,” or to reduce “III” to “U”. Because you can only introduce new characters by appending them to the end of the string, doing something like MI -> MIU -> MIUIU means that you can’t reduce the “I”s in the middle of the string. And doubling “I” with the “Mx -> “Mxx” rule means that “I” is going to be a factor of 2. Reducing “III” to “U” will always leave one or two “I”s at the end of the string.

MII (can’t reduce)

Colossal Gardner, ch. 49

Godel, Escher, Bach.
I’ve been looking forward to this chapter. I read GEB, by Douglas Hofstadter, shortly after it got listed as a bestseller, and I absolutely loved it, both for all the information on the three top title people, and the insights into the state of AI development at the time. I’ve reread parts of the book when I’ve gotten the chance, and I still consider it a good read. The majority of Martin’s comments can be taken as a book review, and just reiterate the content of GEB as a whole. I do want to repeat his insights a little bit regarding the wood block on the GEB cover. Hofstadter made the block himself from a piece of redwood, and dubbed it a trip-let, for “triple letters.” He also reprints Scott Kim’s (creator of Inversions) “Figure” as an example of the background of a set containing the complementary information of its foreground.

The subtitle for Godel, Escher, Bach is “The Eternal Golden Braid,” in part for how the works and thoughts of the three main characters intertwine with each other, and in part because the initials can be derived from the GEB (EGB) trip-let.

(All rights belong to their owners. Images used here for review purposes only. Scott Kim’s “Figure“.)

Going through this chapter, I am finally able to appreciate Douglas’ pun character, the Indian mathematician Najunamar (Ramanujan), who proved three theorems. “He can color a map of India with no fewer than 1,729 colors; he knows that every even prime is a sum of two odd numbers, and he has established that there is no solution to a^n + b^n = c^n when n is zero.” (1729 was the number of the taxi G. H. Hardy rode in when he visited Ramanujan in the hospital, and is the smallest positive integer that is the sum of two different pairs of cubes. Note that color mapping also shows up in the next chapter.) Puzzle 1: What’s the smallest positive integer that can be expressed as the sum of two different squares in two different ways?

For the second puzzle, I have to lay down the logic first. Hofstadter has a “formal system,” which is made up of the letters M, I and U. They can be arranged in strings that he calls theorems, but only by following 4 very specific rules (taken from the site):

Rule 1: xI -> xIU (only if I is at the end)
Rule 2: Mx -> Mxx (only if M is at the beginning)
Rule 3: xIIIy -> xUy (any III anywhere)
Rule 4: xUUy -> xy (any UU anywhere)

In other words, if the string ends in “I”, we can append “U” to it.
We can copy-paste the string after “M” only if “M” is at the beginning.
If the string contains “III,” we can reduce the “III” to “U”.
If the string contains “UU,” we can eliminate the “UU”.

The only “axiom” is that we have to start with the theorem “MI”. Any string that we can make by applying the above rules to “MI” is a theorem of the system.

MI (start)
MII (rule 2)
MIIII (rule 2)
MIIIIIIII (rule 2)
MUIIU (rule 3)

Puzzle 2: Is “MU” a theorem of this system?

(The Two Mysteries, by Magritte (1966))

Gardner describes one section of GEB where Turing and Babbage are engaged in a form of Turing game, each accusing the other of not being real, when Douglas enters the scene and tells them that both of them are products of his imagination, as is fictional Hofstadter himself. Martin is reminded of Magritte’s “The Two Mysteries,” and the statement “this is not a pipe.” Martin asks, “And how real was Magritte? How real are Hofstadter, you, and I?” “We are back to a Godelian Platonism in which reality is infinitely layered. Who can say what reality really is?”

Indeed, who can say? And if they do, why do you believe them?