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?
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.)
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..