Programming Brain Teaser #6: Fixed-point principle

9 May 2013 by Roman Kaspar - Category: Puzzles

As promised last time, let’s do something more serious today…

Let a be any expression. We will call x the fixed point of expression a if x names ax. (Reminder: lower-case letters in our programming language represent a combination of upper-case letters.)

The fixed-point principle says that for each expression a there exists its fixed point x. Furthermore there is a (quite simple) “manual” for constructing the fixed point x of any expression a.

So the question of the day is: can you find that “manual” proving fixed-point principle?
(E.g. a program x that names ABCx, for a = ABC.)

 

Solution

0 comments

Programming Brain Teaser #5: More curiosities

23 April 2013 by Roman Kaspar - Category: Puzzles

Next time, we’ll explore more serious aspect of our programming language, but let’s have some fun for today finding expressions (programs) with strange properties, similar to what we did last time (but a bit more difficult today).

As usual, we’ll use only Q and R rules (described here).

Question 1: Find expressions x so that RQx names (resolves to) QRx.

Question 2: … RRx –> QQx

Question 3: … RQx –> RRx

(You can check how previous riddles were solved. This could help a lot in case you don’t know how to approach solving this.)

 

Solution

0 comments

Programming Brain Teaser #4: More Rx riddles

9 April 2013 by Roman Kaspar - Category: Puzzles

Today, we’ll do something easier for change (but you’ll need to answer two questions). Again, we’ll use only two rules R and Q described here..

Question 1:
For what statement x the following is true:
Rx = x

Question 2:
For what statement x the following is true:
Rx = Qx

 

Solution

0 comments