Programming Brain Teaser #1: Getting Started

25 February 2013 by Roman Kaspar - Category: Puzzles

With this post we start a series of brain teasers about logical programming. The stories are taken from Raymond Smullyan’s book Satan, Cantor and Infinity (an excellent book, by the way, worth reading for sure!). The correct solution to each riddle is posted here directly, so you can verify your answer right away. The estimated time needed to solve each puzzle is about 15 to 30 minutes at the most.

So if you are interested, take your seat and let’s get started with the first story.

The isle of robots, cloning program

Once upon a time, there was an island, which was very noisy. There were plenty of robots buzzing among piles of their own spare parts, busy with creating new robots, fighting each other, meeting their “friends”, or planning conspiracies against their “enemies”.

Each robot had a label written on its chest. At first glance, one could say that the string was some sort of identification, but it turned out that it actually was a program telling the robot what exactly to do.

There were many different kinds of robots (very likely as many as programming languages), we’ll check a few of them.

Let’s start the discussion about the first programming system with the following definitions:

  • A term is a sequence of (any number of) CAPITAL letters, e.g. LLAZBPWS.
  • Lower case letters (e.g. x, y, z, a, b, c, …) are used as shortcuts for terms, e.g. we can say that x represents ABC, or that y stands for DEFGHI.

We can combine terms with shortcuts, to get the final term, we substitute all lower case letters with what they represent. For example, using the definitions for x and y above, the statement AxC corresponds to term AABCC, and statement LxQy evaluates to term LABCQDEFGHI.

In the programming system we are about to explore now, certain selected statements are used as names for other statements. The system contains two rules for naming the terms:

  • Rule Q (quotation): For every statement x, the statement Qx names x.
  • Rule R (repetition): For every statement x that names y, the statement Rx names yy.

You can imagine that operation Q takes the rest of the statement and creates a quoted string out of it. E.g. QABC –> “ABC”.
The rule R can be thought of as a function that takes a string and creates another string: R “ABCD” –> “ABCDABCD”.

But let’s see some examples in the syntax of the explored programming language now, where the quotation marks are NOT part of the syntax: RQB names BB (because QB names B). Similarly, RQBR names BRBR (because QBR names BR). Remember: the terms are (as usual programs in any other programming languages) interpretted from left to right.  That means that the first Q in the term makes the rest of the term a string / an argument for function “calls” of the operators to the left.

To complete the initial set of programming rules, let’s add one rule for creating new robots:

  • Rule C (creation): If x names y, then Cx constructs robot y.

Examples: For any statement y we know that robot CQy creates robot y (simply because Qy names y).  And robot CRQA will create a new robot with program AA.

OK, enough definitions and rules, now something for you to solve (using the programming system described above):

Describe a program of the robot creating its own clone. That is: the resulting program of the newly created robot must be the same as is its creator’s program.

 

Solution

To see the correct solution, click 'Show' button... SelectShow

« - »
COMMENTS