Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!bloom-beacon!tub-tfs.UUCP!alti
From: alti@tub-tfs.UUCP (Thorsten Altenkirch)
Newsgroups: comp.lang.scheme
Subject: Re: self-replicating-code, self-replicating-messages
Message-ID: <8810241240.AA20497@tub-tfs.uucp>
Date: 24 Oct 88 12:40:34 GMT
Sender: daemon@bloom-beacon.MIT.EDU
Organization: The Internet
Lines: 58

I find it more interesting to discuss things like self replicating
code than technical details of SCHEME Implementations. Perhaps I am
on the wrong mailing list. Is there one about functional-programming,
lambda-calculus, theory and application ???

The most solutions to the problem were quite tricky. The reason is
that the problem was ill defined. The most interesting contributioon
came from
"G.OULSNAM" <uunet!MITVMA.MIT.EDU!STCS8004%IRUCCVAX.UCC.IE@tub.UUCP>

                  ((lambda (x) (x x)) (lambda (x) (x x)))

The critic was that these expression has no normal form - even worse
it is an example for an so called non solvable term, which puts even
a lazy evaluator (which does only head reductions) into an infinite
loop.

But the point is, that every solution to the proble has no normal
form, because if :

x ---> x

(---> means reduces to), than you can go on reducing x...

More interesting is another question : Is there a function, which
returns itself for every argument ?

This problem can be solved more straightforward. You just need a
solution for the equation

f x = f , for every x.

This can be done with the fixed-point-combinator Y. The solution is

f = Y K

or in lambda notation :

f = lambda f . ( lambda x . f x x ) ( lambda x . f x x )
        (lambda x y . x)

The Y - Kombinator is a relative of letrec in scheme, so in scheme you
would write :

(define y-k (letrec ((h (lambda (x) h))) h))

It is also possible to define Y in terms of simple scheme expressions
without refering to letrec at all :

(define (yy y f x) ((f ((y y) f)) x))
(define y (yy yy))

So now you can just write :

(define (k x) (lambda (y) x))
(define y-k (y k))

Thorsten