Conference rusure::math

    
    Ask Archilles...
    
    /Bevin

    re .-1: No, Bevin, ask Zeno, the Greek Mathematician who invented
    the paradox of Achilles (no 'r') and the Tortoise. Of course, Zeno
    is dead and Achilles may never have actually existed, so you won't
    get an answer in either case.
    
    	Greater fleas have Lesser fleas
    	And lesser fleas to bite 'em
    	And lesser fleas have lesser fleas
    	... ad infinitum.

The smaller picture is a unimodular transformation that also shrinks the size
of the larger.  That is, any point (x+c,y+f) in the larger picture becomes
(ax+by+c,dx+ey+f) in the smaller, with <some expression> less than one.

Given the transformation, it should be possible to find the limiting
point that results from an infinite number of such transformations.

    re. .1, .2
    
    I see you have read "Godel, Escher, and Bach: The internal golden brade"
    by Hofstader, I may have mispelled the title and author.

    kgg

    It goes back earlier than that. Lewis Carroll made reference to
    Ach. and Tort. in some of his stories and puzzles. I got interested
    in Zeno in High School, probably before Hofstader was born...

    And I first encountered it in the Time-Life book on Maths.
    
    /Bevin

    
    Let see if we can answer the original problem:
    
    >  What becomes of the diminishing pictures when a picture includes
    >  a picture of itself?

    
    Let  r  be the reduction factor, that is the number by which any
    dimention in the picture is multiplied to give the corresponding
    dimension in the next containined picture.
    
    I will attempt to drow a box with a label on it showing a picture
    of the box, etc ...
    
    
                 +--------------------+
                /                    /|
               +--------------------+ |
               |                    | |
               |      +-------+     | |
               |     +-------+|     | |
               |     |       ||     | |
               |     | [ ]   ||     | |
               |     |       |+     | |
               |     +-------+      | +
               |                    |/      
               +--------------------+  

    
    Concider as vectors the lines from one point to the next corresponding
    point. The lengths of these vectors will form a geometric progression.
    Call the first one  a  and the ration  r , then their lengths are

        a,  ar,  ar^2,  ar^3,  . . .
    
    
    
                 +--------------------+
                /                    /|
               +--------------------+ |
               |                    | |
               |      +-------+     | |
               |     +-------+|     | |
               |     |       ||     | |
               |     | [ ]   ||     | |
               |     |       |+     | |
               |   A1+-------+      | +
               |                    |/      
               +--------------------+  
               ^
               |
             Origin
    
    If the vector from the origin to A1,  has the polar coordinates
    (a, c)  and  d  represents the angle by which successive pictures
    are turned, the angles of successive vectors are:
    
       c,  c+d,  c+2d,  c+3d, . . .

    
    then if we represent the successive vectors by imaginaries, the
    are:
    
          ci       (c+d)i     2  (c+2d)i
       a e  ,  ar e      ,  ar  e       ,  . . . 
    
    and the sum of these vectors will be the vector from the origin
    that locates the last point of the series.
    
    Oh, well I have to take care of the baby so I will finish this 
    some other time, unless someone else wants to finished, by all means
    take over.
    
    Enjoy,
    
    Kostas G.
    

    If you look at it as an affine transformation, then in any neighborhood
    of the fixed point there will be an infinite number of the labels.

    The limit point itself doesn't belong to the set of labels though,
    somewhat like the number 1 does not appear in the set

		{ 1/2, 2/3 ... n/(n+1), ... }

    - Jim

Continuation of 548.7

    
    Let see if we can answer the original problem:
    
    >  What becomes of the diminishing pictures when a picture includes
    >  a picture of itself?

    
    Let  r  be the reduction factor, that is the number by which any
    dimention in the picture is multiplied to give the corresponding
    dimension in the next containined picture.
    
    I will attempt to drow a box with a label on it showing a picture
    of the box, etc ...
    
    
                 +--------------------+
                /                    /|
               +--------------------+ |
               |                    | |
               |      +-------+     | |
               |     +-------+|     | |
               |     |       ||     | |
               |     | [ ]   ||     | |
               |     |       |+     | |
               |     +-------+      | +
               |                    |/      
               +--------------------+  

    
    Concider as vectors the lines from one point to the next corresponding
    point. The lengths of these vectors will form a geometric progression.
    Call the first one  a  and the ration  r , then their lengths are

        a,  ar,  ar^2,  ar^3,  . . .
    
    
    
                 +--------------------+
                /                    /|
               +--------------------+ |
               |                    | |
               |      +-------+     | |
               |     +-------+|     | |
               |     |       ||     | |
               |     | [ ]   ||     | |
               |     |       |+     | |
               |   A1+-------+      | +
               |                    |/      
               +--------------------+  
               ^
               |
             Origin
    
    If the vector from the origin to A1,  has the polar coordinates
    (a, c)  and  d  represents the angle by which successive pictures
    are turned, the angles of successive vectors are:
    
       c,  c+d,  c+2d,  c+3d, . . .

    
    then if we represent the successive vectors by imaginaries, the
    are:
    
          ci       (c+d)i     2  (c+2d)i
       a e  ,  ar e      ,  ar  e       ,  . . . 
    
    and the sum of these vectors will be the vector from the origin
    that locates the last point of the series.



                     
                       A2 +
                         /     
                        /     d     
                    A1 +------------
                      /             
                     /              
                 a  / c             
                   /                
                  +-----------------
                  ^
                  |
               Origin

    
    We observe that this succession of vectors is a geometric progression in

                                ci                        di  
    which the first term is  a e   , and the ratio is  r e  .

    So its sum is :


                                      di  n
                        ci   1 - ( r e   )
                     a e   ------------------
                                       di
                                1 - r e    


    The term containing  n  approaches zero as  n --> oo, ( oo means infinity)
    so for the vector from the origin to the limiting point we have


                                   ci
                                a e 
                           --------------------
                                       di
                                1 - r e    


    This may be simplified by multiplying the numerator and the denominator by 
    the the conjugate of the denominator


                                       -di
                                1 - r e    


    which gives it as 


                         a     ci       (c-d)i
                        --- ( e   -  r e       )
                         K

    where 

                         di          -di 
           K  = ( 1 - r e ) ( 1 - r e   )


                        di    -di     2
              = 1 - r( e   + e   ) + r 



        or 
                                 2
           K  = 1 - 2 r cos d + r


     We can now express the abscissa and ordinate of the limiting
     point by means of real numbers:


         x = ( a/K ) ( cos c - r cos ( c - d ) )

         y = ( a/K ) ( sin c - r sin ( c - d ) )



    Enjoy,
    
    Kostas G.
    

Even if seems impossible in the beginning, I once had a PL/I program that
printed its own [complete] source as output. In what other languages can
it be done?

Nitsan

    re. .10

    I believe it can be done in most other languages, I will give a
    Pascal and a DCL example in the next reply.
    
    kgg
    

PROGRAM XEROXPAS (INPUT, OUTPUT );

{<><><><><><><><><><><><><><><><><><><><><><><><><><><><>}
{                                                        }
{  AUTHOR : KOSTAS G. GAVRIELIDIS                        }
{                                                        }
{ VERSION : V1.0-000  KGG  14-AUGUST-1985                }
{                                                        }
{ PURPOSE :                                              }
{          TO MAKE A XEROX COPY OF ITSELF MY PRESERVING  }
{          THE SAME FILE STRUCTURE                       }
{                                                        }
{<><><><><><><><><><><><><><><><><><><><><><><><><><><><>}

VAR 
  F, 
  G  : TEXT;
BEGIN { MAIN }
  OPEN( F, 'XEROXPAS.PAS', OLD );   { input file }
  RESET ( F );
  OPEN( G, 'XEROXPAS.OUT', NEW );   { output file }
  REWRITE( G ) ;
  WHILE NOT EOF(F) DO BEGIN
    WHILE NOT EOLN( F ) DO 
      BEGIN
         G^ := F^;
         PUT( G );
         GET( F );
      END;
    READLN( F );
    WRITELN( G );
  END;
END. { MAIN }

$!
$!  This is file : [KOSTAS]XEROXME.COM
$!
$on error then goto check
$open/read infile xeroxme.com
$loop:
$  read/end_of_file=done infile record
$  write sys$output record
$  goto loop
$check:
$  write sys$output "Error opening file: ''f$message($status)'"
$done:
$  close infile
$exit:
$!  End of file : [KOSTAS]XEROXME.COM
$exit

    Now,
    
       The interesting problem will then be what is the smallest program
       that containts itself and recreates itself at run time? In what
       ever language it may be written in. I believe in MACRO will be
       the smallest because you can make reference to memory locations
       which will have the begining of your program mapped in, so you
       will not have to read it self in from the source code, which
       means that the source file does not have to exist in order for
       the program to work, like the previous two examples in Pascal
       and DCL.
    
    Enjoy,
    
    Kostas G.
    
       

    In .10 Nitsan had intended to say that "No input statements are allowed".
    That makes it a bit more difficult ... I'll personally award a prize
    (to wit:  a cookie from Mike Moroney) to the first person to demonstrate
    a BLISS program that outputs itself without doing any file input.
    
      John

I've recently had a need to create a program that replicates itself over an
Ethernet since I needed to run the same program on several systems attached
via an Ethernet at once.  It won't win any prizes for shortness, however!

Now, here's the world's shortest Macro-11 code that replicates itself.
Drum roll, please?

X:	MOV	-(PC),-(PC)
	.END	X

Now, where's my prize :-)  Yeah, it's not BLISS (I don't know Bliss) but
I think it deserves a prize for its length, anyway! (One word)

-Mike

    Uh, I think that this problem needs some better definition.  Either
    that, or somebody (bodies) is pulling our leg here.
    
    I first heard this problem around 1975 or '76, and I believe that
    David Ahl was the author of it then (though I suspect that he got
    it from elsewhere).  As I heard it ran like this:
    
    	1) Write a BASIC program that will produce the same output when
    RUN as when LISTed.  Assume that you will not be able to refer to
    the source program it self.  (IE your program may be compiled, the
    source deleted, and it will stiil work the same).
    
    	2) What is the shortest legal program that can do this?
    
    Now in those days BASIC was BASIC, and there wasn't much difference
    between various implementations.  The two important points I wish
    to make here are that:
    
    	1) You can't read in the source.  Thats not the problem.
    	2) You must output the program, on a terminal, or in a file.
     Copying the program around memory, a la Core Wars is not the point
    either.
    
    I would also say that referring to the executable code was not really
    part of the problem either because the problem originaly implied
    that it would work in the language, independent of cpu, or operating
    systems.
    
    The solution is cute, but not very difficult.  I don't have any
    of my solutions, or I would print them, but I do recall that BASIC's
    line numbers (required then) presented an additional twist to the
    problem.  I belive that the ALGOL derivitave languages (Pascal,
    Bliss, et al) would require their own special twist to accomodate
    the beginning and ending control structures.
    
    -- Barry
    

module xerox (main=main, addressing_mode(external=general))=
begin
external routine lib$put_output, str$concat, lib$spawn;
bind x = uplit(
	%ascid'''',
	%ascid'	%ascid',
	%ascid',',
	%ascid'mail nl: aurora::hallyb /subj="Gilbert loves cookies!"',
	%ascid'module xerox (main=main, addressing_mode(external=general))=',
	%ascid'begin',
	%ascid'external routine lib$put_output, str$concat, lib$spawn;',
	%ascid'bind x = uplit(',
	%ascid'	0): vector;',
	%ascid'routine main=',
	%ascid'    begin',
	%ascid'    local dyn: block[8,byte] initial ((2*256+14)*65536,0);',
	%ascid'    incr i from 4 to 7 do lib$put_output(.x[.i]);',
	%ascid'    str$concat (dyn, .x[1], .x[0], .x[0], .x[0], .x[0], .x[2]);',
	%ascid'    lib$put_output(dyn);',
	%ascid'    incr i from 1 do if .x[.i] eql 0 then exitloop else begin',
	%ascid'	str$concat (dyn, .x[1], .x[0], .x[.i], .x[0], .x[2]);',
	%ascid'	lib$put_output(dyn);',
	%ascid'	end;',
	%ascid'    incr i from 8 do if .x[.i] eql 0 then exitloop else',
	%ascid'	lib$put_output(.x[.i]);',
	%ascid'    lib$spawn (.x[3]);',
	%ascid'    return 1;',
	%ascid'    end;',
	%ascid'end eludom',
	0): vector;
routine main=
    begin
    local dyn: block[8,byte] initial ((2*256+14)*65536,0);
    incr i from 4 to 7 do lib$put_output(.x[.i]);
    str$concat (dyn, .x[1], .x[0], .x[0], .x[0], .x[0], .x[2]);
    lib$put_output(dyn);
    incr i from 1 do if .x[.i] eql 0 then exitloop else begin
	str$concat (dyn, .x[1], .x[0], .x[.i], .x[0], .x[2]);
	lib$put_output(dyn);
	end;
    incr i from 8 do if .x[.i] eql 0 then exitloop else
	lib$put_output(.x[.i]);
    lib$spawn (.x[3]);
    return 1;
    end;
end eludom

$ A[0,8]=34
$ B="$ A[0,8]=34!/$ B=!AS!AS!AS!/$ C=F$FAO(B,A,B,A)!/$ WRITE SYS$OUTPUT C"
$ C=F$FAO(B,A,B,A)
$ WRITE SYS$OUTPUT C

p="p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}

                 <<< CLT::ULTRIX$:[NOTES$LIBRARY]MATH.NOTE;1 >>>
                           -<  Mathematics at DEC  >-
================================================================================
Note 548.21      <><><>   Picture with itself in it.   <><><>           21 of 21
KEEPER::KOSTAS "Wisdom is the child of experience."  28 lines   4-AUG-1986 20:50
            -< A program  P  has degree  n  if  P = P' =...=P^n ' >-
--------------------------------------------------------------------------------

    Well then,
    
       Given all these programs which contain themselves I will like to
       introduce a terminology for all such programs.
    
    Definition 1:  We say a program  P  is of degree  1  if and only if
                   when run it produces a program  P'  such that P = P'.
                   (i.e. when a character by character comparison of 
                   P  and  P' is done the number of differences is zero.
    
    Definition 2:  We say the derivative of a program  P  is  2  if and
                   only if  P = P' = P'' . And where  P'  is optained
                   by the steps in the first definition, and  P''  is
                   optained by substituting  P'  for  P  and  P'' for
                   P'  in the first definition.
    
    
    Definition 3:  We say that the derivative of a program  P   is 
                   n  if and only if :
                                                        (n ' s)
                        P  =  P'  =  P''  =  . . .  =  P
    
    Enjoy,
    
    Kostas G.
    
     
                 

    Re .21:
    
    With that definition, every program with degree 1 also has degree 2, 3,
    and all other integers.
    
    
    				-- edp 

    re. .22
    
    I do not agree. Take a look at the programs given in this entry.
    The derivative of the BLISS program is not the same as the original,
    even if it produces itself. So the degree of this one is one, because
    if you take the output of the original program and compile and run
    it it will not produce itself.
    
    Have you got a better definition?
    
    kgg
    

    re. .22
    
    The degree of the DCL is one. 
    
    (i.e.  P = P', and P <> P'', and  P' <> P'')
    
    I have extracted and executed the DCL command file given in here
    and this is what I found which let me to conclude the degree of
    it.
    
file: xeroxme1.com
--------------------------------------------------    
    
$ A[0,8]=34
$ B="$ A[0,8]=34!/$ B=!AS!AS!AS!/$ C=F$FAO(B,A,B,A)!/$ WRITE SYS$OUTPUT C"
$ C=F$FAO(B,A,B,A)
$ WRITE SYS$OUTPUT C

--------------------------------------------------    

$spawn/nowait  @xeroxme1.com/out=xeroxme2.com
    
file: xeroxme2.com
--------------------------------------------------    
    
        
$ A[0,8]=34
$ B="$ A[0,8]=34!/$ B=!AS!AS!AS!/$ C=F$FAO(B,A,B,A)!/$ WRITE SYS$OUTPUT C"
$ C=F$FAO(B,A,B,A)
$ WRITE SYS$OUTPUT C
$ A[0,8]=34
$ B="$ A[0,8]=34!/$ B=!AS!AS!AS!/$ C=F$FAO(B,A,B,A)!/$ WRITE SYS$OUTPUT C"
$ C=F$FAO(B,A,B,A)
$ WRITE SYS$OUTPUT C

--------------------------------------------------    

$spawn/nowait  @xeroxme2.com/out=xeroxme3.com

file: xeroxme3.com
    
--------------------------------------------------    
    
$ A[0,8]=34
$ B="$ A[0,8]=34!/$ B=!AS!AS!AS!/$ C=F$FAO(B,A,B,A)!/$ WRITE SYS$OUTPUT C"
$ C=F$FAO(B,A,B,A)
$ WRITE SYS$OUTPUT C
Invalid numeric value - check for invalid digits
 \34
$\

--------------------------------------------------    
    

    Enjoy,
    
    Kostas G.    

    Re .23:
    
    If the output isn't the same, the program hasn't reproduced itself, so
    it does not have degree one.
    
    
    				-- edp

    re. .25
    
    Yes you are correct. Its degree is zero not one.
    
    kgg
    

    well,
    
        It looks like the program in  C  has the highest degree 
    ( i.e.  n = infinity )

    the output of the original program is the same as the program itself
    for at least the first 3 programs (that's were I stoped looking).
    
    So, here we go:
    

$type xerox_me_c.c
p="p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}

$gocc xeroc_me_c  ! gocc does  compile, and link a  C  program    
$assign xerox_me_c_2.c sys$output
$run xerox_me_c
$deassign sys$output
$type xerox_me_c_2.c
p="p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}

$gocc xeroc_me_c_2  ! gocc does  compile, and link a  C  program    
$assign xerox_me_c_3.c sys$output
$run xerox_me_c_2
$deassign sys$output
$type xerox_me_c_3.c
p="p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}

$gocc xeroc_me_c_3  ! gocc does  compile, and link a  C  program    
$assign xerox_me_c_4.c sys$output
$run xerox_me_c_3
$deassign sys$output
$type xerox_me_c_4.c
p="p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}
    
    
    Enjoy,

    Kostas G.

    Re .27:
    
    If you use DEFINE/USER SYS$OUTPUT XEROX_ME_C_n.C, you won't have to
    deassign it afterwards; it only stays in effect for the next run of a
    program.
    
    
    				-- edp 

< Note 548.27 by THEBUS::KOSTAS "Wisdom is the child of experience." >

>    the output of the original program is the same as the program itself
>    for at least the first 3 programs (that's were I stoped looking).

You didn't have to look that far, since if the output of the original program
is identical to the original program, the output of THAT program must be
identical, also.  Otherwise, the output of the original program couldn't
be identical to the original, which is a contradiction.

-Mike

Now, can you write a program whose output is a DIFFERENT program whose output
is the original program?

More generally - does there exist a sequence of programs (p1,p2,p3,...) where
p(i+1) is the output of p(i), not all the p's are identical but some of them
are?

(I don't know the answer to this one)

Enjoy,
Nitsan.

    
    re. .29
    
    I do not agree. Take a closer look at the DCL example, specifically
    the reply in 548.24, where the program (procedure) produced will
    not be the same (will not run to produce it self) after the first
    time ( even it it looks the same as the creator of it .)
    
    /kgg

    
    

    Re .30:
    
p="p=%c%s%c;main(){printf(p,34,p,34,1-%d);}";main(){printf(p,34,p,34,1-0);}
    
    Obviously, the function "1-x" (in C, !x would have the same result
    here) can be changed to any number of functions to produce sequences of
    different programs that loop. 
    
    
    				-- edp

re .31:  That's irrelevant.  If a program produces an output that's identical
to it, than THAT program's output must be identical to it (and the first
one...) otherwise it wouldn't be identical.  Remember, computers are
deterministic machines. 

The example you gave is a program whose output is NOT identical to itself,
it just happens to look the same when displayed on a CRT.  $ DIFFERENCE
will show the difference in this case.

-Mike

re .32:
	See note 135.

    Being new to this conference, I'm wandering randomly through it,
    so even though this note's been quiet for a year or so, I thought
    I'd mention the resemblance of this stuff to John von Neumann's
    work on self-reproducing automata.  
    
    len.