A brief digression

Before we continue our exploration of truthiness in C#, a brief digression. I mentioned last time the "knights and knaves" puzzles of logician Raymond Smullyan. Though I do enjoy those puzzles, my favourite of his puzzles are his chess puzzles, and my second favourite are his combinatory logic puzzles. Here's an example of the latter, adapted from the puzzle on page 134 of Satan, Cantor and Infinity.

We have an alphabet consisting of the letters S, E, R, M, K and V. You can make strings out of these letters; a "string" is defined as a ordered sequence of letters drawn from the given alphabet; the sequence can be of any finite length. Some strings are said to "name" other strings.

I'll use "x" and "y" as variables that stand in for strings, and furthermore we can assume that x and y never stand for empty strings. (And that moreover, in the fourth rule, y is a string with at least two characters.) The rules of naming are:

• SxE names x
• if x names y then Rx names yy
• if x names y then Mx names SyE
• if x names y then Kx names the string formed by removing the leftmost character from y
• if x names y then Vx names the string formed by reversing the letters of y

So, for example, SRME names RM, by the first rule. Because SRME names RM, we know that RSRME names RMRM by the second rule. And thus KRSRME names MRM.

There has been a small amount of confusion in the comments; note that I am not saying that some strings are "legal" and some are "illegal" in any way; rather, I am saying that some strings just happen to "name" other strings. A string that does not name any other string is still a perfectly "good" string; no string is more or less valid than any other. "RM" for example does not name any string.

The challenge -- which probably will not be too hard for computer programmers, but will be a bit tricky for non-programmers who haven't read the fifteen pages of easier puzzles leading up to this one -- is to find a string that names itself. Smullyan's solution is 18 letters long and he challenges the reader to find a shorter one. I have found a 12 letter solution. I conjecture that 12 letters is the smallest such string, but I have not proven it. I'll put both Smullyan's solution and my solution in the comments. Good luck!

UPDATE: There is a nine-letter solution, and it is minimal. Nice work!

Comments

• Anonymous
  April 14, 2012
  Smullyan's 18 letter solution is KMKRVKVMSKMKRVKVME. My 12 letter solution is RKMKSERKMKSE, which you will note does not even have V in it! Rule V is unnecessary to solve this particular puzzle, though it is needed to solve some of the even harder puzzles that Smullyan poses about this set of rules.

• Anonymous
  April 17, 2012
  Woah, great! I only found the two 18 letter solutions, KMKRVKVMSKMKRVKVME and KKMRVKVMSKKMRVKVME. I totally missed the idea of using S and E between themselves.

• Anonymous
  April 17, 2012
  It's essentially the same challenge as trying to write a quine, isn't it? The "rules" in this puzzle essentially describe a simple language for manipulating strings; the challenge is to write a quine in that language. That is correct. -- Eric

• Anonymous
  April 17, 2012
  Are you sure that Es are allowed within a SxE string? "Allowed?" Allowed by who? I don't understand what you're talking about. Can you explain? I said that SxE names x for any nonempty string x, so SEE names E; what else would it name? -- Eric

• Anonymous
  April 17, 2012
  My question (inspired by Anonymous's question, but slightly different) is: If x and y never stand for empty strings, how can you have "SE"? Again, I don't understand the question. "SE" is just a string; no one is stopping you from "having" it. I haven't said anything whatsoever about some strings being "legal" or "illegal". I've just said that there is a relation "names" on strings drawn from this alphabet. A relation is neither more nor less than a set of ordered pairs of strings; given the rules I've drawn up it just so happens that there is no pair in that set where the first item in the pair is "SE". -- Eric

• Anonymous
  April 17, 2012
  You can have SE, it simply doesn't name anything. As an extension of this, RSE doesn't name anything either. However SSEE names SE.

• Anonymous
  April 17, 2012
  KMRSKMRSE? Nice! -- Eric

• Anonymous
  April 17, 2012
  It's pretty easy to search for solutions in increasing order of length, which quickly dispatches your conjecture with this 9-letter counterexample: KMRSKMRSE. All other solutions have at least 12 letters (although your 12 letter solution is not unique). Nice. I considered writing such a program, but I figured someone would on my behalf. :-) Incidentally, I believe Smullyan gives a 14 letter solution when he gives a similar problem in a different book. -- Eric

• Anonymous
  April 17, 2012
  I found a solution with 9 characters: KMRSKMRSE (sorry if this double-posts)

• Anonymous
  April 17, 2012
  Argh! Beat to it by seconds!

• Anonymous
  April 17, 2012
  The comment has been removed

• Anonymous
  April 17, 2012
  You need a sixth rule: "The naming relationship defined herein is the smallest such which satisfies the above rules." Otherwise I could say that "every string names every other string", and that also satisfies the rule set.

• Anonymous
  April 18, 2012
  @Another Anonymous: You don't need to brute force when you can direct! names(['s'|XE], X) :- append([X, ['e']], XE). names(['r'|X], YY) :- append(Y, Y, YY), names(X, Y). names(['m'|X], ['s'|YE]) :- append([Y, ['e']], YE), names(X, Y). names(['k'|X], R) :- [_|R] = Y, names(X, Y). names(['v'|X], RY) :- reverse(RY, Y), names(X, Y). self_naming(X, N) :- length(X, N), names(X, X). ?- self_naming(X, N). X = [k, m, r, s, k, m, r, s, e], N = 9 ; X = [r, k, m, k, s, e, r, k, m, k, s, e], N = 12 ; X = [r, k, k, m, s, e, r, k, k, m, s, e], N = 12 ; ...

• Anonymous
  April 18, 2012
  @Eric-FYI, there is no 14 letter solution.