A selfreproducing Pascal program

Oliver Knill


A program is called selfreproducing, if it produces itself as an output. more information. During a logic course taught by Ernst Specker around 1985-1986, some of our class was playing with selfreproducing programs. My solution below was heavily influenced by Goedel numbering, a topic, we just had covered in that course. The Pascal program itself will not yet reproduce itself, but it will produce a Pascal program, whose output will produce a selfreproducing Pascal program. You can download the Makefile to run it. It was last tested with the Free Pascal compiler/ Version 1.0.10.

Dynamical reformulation: Fix a programming language like Pascal. Denote by T(x) the output of a program x. Denote by X the class of all programs which have the property that the orbit T(x), T(T(x)), T(T(T(x))) stays in X. Think of (T,X) as a dynamical system on the countable set X. By definition, selfreproducing programs are fixed points of T. The program reflexion.pas is in X and is preperiodic. It is attracted to a fixed point of T. Similarly to producing fixed points, it is also possible to construct periodic points of any period of T or orbits in X, which are not periodic.


program reflexion(output); 
type st=packed array[1..54] of char; 
var i,j,z :integer;
goedel :array[0..9] of st;
begin 
  goedel[0]:='112712271327142715276061626364656667686916271727182719'; 
  goedel[1]:='272127512527413311374233123743331337443314374533153746'; 
  goedel[2]:='331637473317374833183749331937262752252741332137423322'; 
  goedel[3]:='374333233744332437453325374633263747287727483328374933'; 
  goedel[4]:='293726275325274129323642333231364333333932364433343932'; 
  goedel[5]:='364533353136463438313647283532393138313648333831364933'; 
  goedel[6]:='393136262754337131397639317431365533723139763931743136'; 
  goedel[7]:='563473753139763931787931393239757678393239317731365725'; 
  goedel[8]:='274133713742337237433373374433743745337537463376374733';
  goedel[9]:='773748337837493379372627222723272427272727272727272727'; 
  for j:=0 to 9 do
    for i:=1 to 27 do 
    begin 
    z:=ord(goedel[j][2*i])-48; 
    case (ord(goedel[j][2*i-1])-48) of
    1: case z of 
      1: write('program reflexion (output);                        ');
      2: write('type st=packed array[1..54] of char;               '); 
      3: write('var i,j,z :integer;                                '); 
      4: write('goedel :array[0..9] of st;                         ');
      5: write('begin                                              ');
      6: write(' for j:=0 to 9 do                                  ');
      7: write('  for i:=1 to 27 do                                ');
      8: write('  begin                                            ');
      9: write('  z:=ord(goedel[j][2*i])-48;                       ');
   end;
   2: case z of
      1: write(' case (ord(goedel[j][2*i-1])-48) of                ');
      2: write(' end;                                              ');
      3: write(' end;                                              ');
      4: write('end.                                               ');
      5: write('case z of                                          ');
      6: write('      end;                                         ');
      7: writeln;  
      8: write('writeln'); 
      9: write('write(');
   end; 
   3: case z of 
     1: write(chr(39));
     2: write('chr(39)');
     3: write('write(',chr(39));
     4: write('writeln(',chr(39)); 
     5: write('('); 
     6: writeln(');');
     7: writeln(chr(39),');') ; 
     8: write(');'); 
     9: write(','); 
   end;
   4: write('   ',z,': ');
   5: write(' ',z,': ');
   6: writeln('  goedel[',z,']:=',chr(39),goedel[z],chr(39),';');
   7: case z of 
    1: write('   '); 
    2: write(' '); 
    3: write('  '); 
    4: write(': '); 
    5: write('goedel['); 
    6: write('z');
    7: write(';');
    8: write(']'); 
    9: write(':='); 
  end; 
 end; 
end; 
end.