Fabulous Adventures In Coding
Eric Lippert is a principal developer on the C# compiler team. Learn more about Eric.
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:
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!
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.
I only found the two 18 letter solutions, KMKRVKVMSKMKRVKVME and KKMRVKVMSKKMRVKVME.
I totally missed the idea of using S and E between themselves.
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
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
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
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.
Nice! -- Eric
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
I found a solution with 9 characters: KMRSKMRSE
(sorry if this double-posts)
Argh! Beat to it by seconds!
** NOTE: I've never read the puzzle book, so this solution is just a stab in the dark.
Remembering back to my days in university, I'm reminded of Context-Free Grammars, and I believe that you wrote post(s) a while back discussing CFGs (in relation to regexes iirc). It seems to be the case that if you described the rules as a CFG, you could build a corresponding state machine/regex that would validate the grammar, and test solutions. Brute forcing strings with such a limited alphabet should be somewhat trivial for short (<100) length patterns.
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.
@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],
@Eric-FYI, there is no 14 letter solution.