/*This is the computer program TIEv1.2 (Turing machine Inference Engine)

 Copyright (C) 2017 John Nixon
    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    A copy of the GNU General Public License can be obtained from
    <http://www.gnu.org/licenses/>.

This program is essentially the translation into D of TIEv1.0 (written in C++). It generates the set of all
irreducible regular rules (IRR) for any Turing Machine (TM) up to any specified
length, written by John Nixon (john.h.nixon1@gmail.com formerly john.h.nixon@spamcop.net).
Comments are welcome.
In the terminology of paper 1, "rule" is to be read as
"regular rule" i.e. RR. Likewise "irreducible_rule" and "reducible_rule" are
to be read as IRR and RRR respectively as defined in paper 1.
The latest version the program is available from www.bluesky-home.co.uk under Turing 
machine analysis. The paper describing the theory behind it and what the
output means has been published in paper 1:

Mathematica Aeterna, (2013) Vol. 3, no. 9, 709 - 738 (Paper 1)

and a second paper continuing this study is planned (Paper 2)

Modifications for this version
(1) The program has been translated from C++ into D (dlang.org).
[D is much easier to use than C++, has bounds checking making anything like Valgrind
unnecessary as far as I can see, has many more features and has similar syntax.
This otherwise excellent language does unfortunately require the programmer to set up
and use functions called ``dup" that duplicate things that I think should be done 
automatically in assignments and copying objects into arrays etc. If the programmer
forgets to do this correctly a new pointer will be assigned to the object instead
of making a new object copy, so if the object is subsequently changed, errors could
arise in code that appears naively to be correct.]

(2) The symbols are now in the alphabet {a,b,c,...z} and the states are numbered 1,2,3,...
allowing for Turing Machines with many more states and symbols to be analysed.
This also removes ambiguity in symbolic expressions where exponents are used and is in accord
with the notation in Paper 2.
(3) A much improved format for reading Turing machines.
(4) There was a modification to the way halting is handled: halting is now considered
to be a property of a TM instruction rather than a TM state. As such, the TM can either move right (R)
left(L) by one square, or halt (H) at each TM step. This avoids needing a distinguished state, but it means that
a configuration set (CS) reached as a result of a halt must specify this explicitly e.g. by putting (H) after it.
In any case my interest is mainly in describing non-terminating computations so I probably won't
make much use of this in future.

Modifications for the next version:
Improvements to the TIE algorithm suggested by the methods of Paper 2. 

The IRR are essentially the non-redundant set of computational short-cuts that
can be derived by running the Turing Machine(TM) on a finite length of tape.
Every computation of the TM as a sequence of single TM steps can be replaced
by an equivalent shorter sequence of applications of the short-cut rules,
(though the set of such rules may be and usually is infinite). Any computation with a TM
expressed in terms of its IRR is reduced in terms of the number of computation steps needed.

By correctly guessing the iterative formulae or method for obtaining the IRR for a particular TM
with the aid of the list of IRR generated by this program,
and verifying them by an induction argument, it is possible to obtain long-
term information on the behaviour of the TM that is not obvious initially, and
may shed light on the problem which the TM was designed to solve. Because TM's
can be set up to solve any problem that can be solved by an algorithm, the
possibilities of application of this method seem limitless.

The notation for each irreducible regular rule (IRR), including the original
Turing Machine (TM) table, is in the following order: two configuration sets (CS)'s
each defined by a quadruple (state,pointer position,length,tape symbols) representing
the input and output respectively of the rule, followed by the status of the rule 
(L left-moving,R right-moving,H halt), and finally the numbers of steps involved in its
derivation (number of derivation steps from rules of length n-1, number of TM steps).

This program must be compiled before it can be used. It was written in D and
originally had extension .d, but since webservers can misinterpret such files
I prefer to keep it on the web as a .txt file and rename it before compilation. To compile
it go to dlang.org and download one of the compilers (I use dmd).
then do for example 
mv tie_v1.2.txt tie.d
dmd tie.d
and run it with the command that includes the file name of the TM to be analysed.
./tie <TM_file_name>.txt
*/

import std.stdio;
import std.container;
import std.algorithm;
import std.string;
import std.file;
import std.conv;
//global variables
int nsy;//# symbols
char[] outfile;
char[] question;

//********************************** function can_write **************************************
//This function finds a filename to be written to for output and returns it. It ensures
//that no file is overwritten without the consent of the user. "base_name" is usually the input
//datafile name and "extension" is the default file extension for output (including the dot)
//arrays and class objects are not copied
char[] can_write(const char[] base_name,const char[] extension){
  char[] filename = (base_name ~ extension).dup;
  char[] chars;
  char[] question;
  bool write1,fn,overwrite=false;
  do{
    fn = exists(filename);
    if(fn){
      writeln("The file ",filename," already exists.");
      question="Do you want me to overwrite it?".dup;    
      overwrite=yes(question);
      if(!overwrite){
        writeln("The new path and file name is ",base_name,"<extra characters>",extension);
        write("Enter the extra characters: ");
        readln(chars);chars=chomp(chars);
        filename=base_name ~ chars ~ extension;}}
    write1=(!fn) || overwrite;}
  while (!write1);
  writeln("Output will be to the file ",filename);
  return filename;}

//************************************** function yes *****************************************
//This function asks the user the question by dispaying the text 'question' and waits for
//the response y (for yes) or n (for no)
bool yes(const char[] question){
  char ans='*';
  bool ret;
  char[] res;
  while(ans!='y' && ans!='n'){
    std.stdio.write(question,"(y/n): ");
    res=chomp(readln().dup);
    ans=res[0];
    if(res.length==1){
      if(ans=='y')ret = true;
      else if(ans=='n') ret = false;}
    else{ans='*';}}
  return ret;
}

//*********************************** input_int ***************************************
//The purpose of this function is to extract an int from the input stream and handle
//the error that occurs when a non-number is entered, and allow the user to enter it again.
void input_int(ref int i){
  bool error;
  char[] line;
  for(;;){
    line = chomp(readln().dup);
    error=false;
    try{i = to!int(line);} catch (Exception){error=true;}
    if(error == false)break;
    write("An error occurred. Please try again: ");}
}
//************************** struct CS ************************************************
//This class represents a configuration set(CS) as defined in the paper.
//I will use the convention that if p>0, symbols will be added to the left
//of the pointer, and if p=0, symbols will be added to the right.
//This distinguishes the two cases when l=0 because then p=1 and 0 respectively.
struct CS{
  CS dup()const{
    CS cs;
    cs.s = this.s;
    cs.p = this.p;
    cs.l = this.l;
    cs.t = this.t.dup;
    return cs;}
  int s;//state
  int p,l;//pointer position,length of tape given
  char[] t;//part of tape of specified length
}
//********************************** function at_ptr *********************************
//Returns the symbol at the pointer as a char.
//This function assumes the pointer is at the first or last symbol on the tape
//otherwise the error message is given. (The other cases will not be needed) 
char at_ptr(const ref CS cs){
  if(cs.p==1)return cs.t[0];
  if(cs.p==cs.l)return cs.t[cs.l-1];
  throw new Exception("Error in at_ptr: argument doesn't have pointer at one end of the tape.\nThe offending argument was ");
  write("cs = ",cs);}

//********************************** function del_sy ********************************
//Delete the symbol at the pointer. This assumes the pointer is at one end
//of the known string of symbols on the tape.
//If cs.p=1 delete symbol at left else delete symbol at right.
//q is only needed to distinguish the two cases when l=1: is the CS to be treated as
//with the pointer at the left or right end?
void del_sy(ref CS cs,const ref bool q){
  if(cs.p==1 && cs.l>1){//rotate first element to last place
    rotate(cs.t,cs.l-1);//should it be cs.t.dup?
    cs.p=0;}
  if(cs.p==1 && cs.l==1){
    cs.p=!q;}//if (!q)cs.p=1;else cs.p=0;
  --(cs.l);
  cs.t=chop(cs.t);}
//******************************** function add_at_x *******************************
//Add symbol sy at the opposite end of the string of symbols from the pointer.
//The routine assumes that the pointer is just off one end of the known
//symbols on the tape (other cases will not be needed).
void add_at_x(ref CS cs,char sy){//
  ++(cs.l);
  cs.t.length++;
  cs.t[cs.l-1]=sy;
  if(cs.p){//the symbol is added at the left
    ++(cs.p);
    rotate(cs.t,1);}}
//********************************* function add_at_ptr ****************************
//Add symbol sy to cs at the pointer position.
//The routine assumes that the pointer is just off one end of the known
//symbols on the tape.
void add_at_ptr(ref CS cs,char sy){
  ++(cs.l);
  cs.t = leftJustify(cs.t,cs.l,sy);
  if(!cs.p){
    cs.p=1;
    rotate(cs.t,1);
  }}

//********************************* function same **********************************
//Returns whether two CS's are equal or not
bool same(const ref CS cs1,const ref CS cs2){
  if(cs1.s!=cs2.s)return 0;
  if(cs1.p!=cs2.p)return 0;
  if(cs1.l!=cs2.l)return 0;
  if(cs1.t!=cs2.t)return 0;
  return 1;}

//******************************** function rotate *********************************
//Rotates a char[] array of length l by r places to the right. 

void rotate(char[] str,int r){
  char[] temp = str.dup;
  int l=to!int(str.length);
  temp.length = 2*l-r;
  foreach(i;0 .. l-r)temp[i+l] = temp[i];
  foreach(i;0 .. l)str[i] = temp[i+l-r];}
//********************************** function superset *****************************
void superset(ref CS cs,int x){//truncate the string in the CS to
//x symbols closest to the pointer position.
//This assumes that the CS on input has the pointer just off the rightmost or leftmost
//end of the known symbols.
  int n=to!int(cs.t.length);
  char[] temp;
  temp.length=x;
  if(cs.p){
    foreach(i; 0 .. x)temp[i]=cs.t[i+n-x];
    cs.p=x+1;}
  else{
    foreach(i; 0 .. x)temp[i]=cs.t[i];}
  cs.t=temp;//dup needed? no it's not changed again
  cs.l=x;
  return;}

//********************************** function combine ******************************
//Returns the combination of two CS's i.e. combines two CS's for use in the
//implementation of the algorithm associated with theorem 9.3.
//rhs is the first CS mentioned in Theorem 9.3 and lhs is the CS in the LHS of the first
//rule in the existential quantifier in the result of the theorem. The combination returned is
//the RHS of the second rule in the result of the theorem. 
//t is the variable t in the theorem.
CS combine(const ref CS lhs,const ref CS rhs,int t){
  CS cs;
  cs.s=lhs.s;
  cs.l=rhs.l-1;
  cs.t=rhs.t.dup;
  if(rhs.p){
    cs.p=rhs.p-1;
    foreach(i; 0 .. rhs.l-t)cs.t[t-1+i]=lhs.t[i];}
  else{
    cs.p=0;
    foreach(i;rhs.l-t .. rhs.l-1)cs.t[i]=rhs.t[i+1];
    foreach(i;0 .. rhs.l-t)cs.t[i]=lhs.t[i+1];}
  cs.t = chop(cs.t);
  return cs;}

//******************************* function subset **********************************
//Returns whether cs1 is a subset of cs2 (includes equality)
bool subset(const ref CS cs1,const ref CS cs2){
  int ll;
  if(cs1.s!=cs2.s)return 0;//false if states differ
  ll=cs1.p-cs2.p;//difference between left end of tape represented
  if(ll<0)return 0;
  if((cs2.l-cs2.p)>(cs1.l-cs1.p))return 0;
  char[] sub;
  sub.length=cs2.l;
  foreach(i;0 .. cs2.l)sub[i]=cs1.t[i+ll];
  return sub==cs2.t;}

//******************************* function inlist **********************************
//Returns whether or not cs is in the list lst.
bool inlist(const ref CS cs,ref CS[] lst){
  foreach(cs1;lst){
    if(same(cs,cs1))return 1;}
  return 0;}

//******************************** struct IRR **************************************
//relation between two CS's defined by the action of the TM. In the paper
//special types of rule were defined: regular rules i.e. rules defined by a simple 
//recursive definition, and the subset of these that are non-redundant i.e. derived
//in more than one step. These the the irreducible regular rules (IRR).
struct IRR{
  CS c1,c2;
  char sig;//L,R,H, or C i.e. left moving, right moving, halting, or cycling resp.
//See the paper for details.
  int n_derivation;//# derivation steps
  int n_machine;//# machine steps
  IRR dup()const{
    IRR r;
    r.c1 = this.c1.dup;
    r.c2 = this.c2.dup;
    r.sig = this.sig;
    r.n_derivation = this.n_derivation;
    r.n_machine = this.n_machine;
    return r;}
}

//The set of IRR for the TM.
IRR [][] irreducible_rules;
//************************** function is_irreducible_rule_rhs *********************
//This is part of the implementation of the procedure to determine the IRR of length n
//from the IRR of length n-1 based on the theorems in section 9 of the paper.
//Understanding Theorem 9.3 is necessary to understand this.
//Outline of algorithm:
//get length of rhs string
//Look up a given RHS to see if is in the list of RHS's of all the IRR of the
//appropriate length.
//Only include the corresponding LHS's if the pointer is at the same end of the
//string of symbols on the LHS and RHS of the rule. Add such LHS's to the list.
//The return value has the meaning "is IRR RHS?" as applied to the second argument.
//All appropriate LHS's must be given if they are required by the first argument.
bool is_irreducible_rule_rhs(bool need_lhss,const ref CS rhs,ref CS[] lhss){
  bool ret=0;
  if(need_lhss)lhss.length = 0;
  int j=rhs.l-1;
  foreach(lr;irreducible_rules[j]){
    if(same(lr.c2,rhs)){
      ret=1;
      if(!j ||(!rhs.p && lr.c1.p==1) || (rhs.p>1 && lr.c1.p==lr.c1.l)){
        if(need_lhss)lhss ~= lr.c1.dup;}}}
  return ret;}

//********************* function is_reducible_rule_rhs ******************************
//This function, when combined with "is_irreducible_rule_rhs", "combine" and "superset"
//implements the method defined principally by Theorem 9.3 of the paper.
bool is_reducible_rule_rhs(const ref CS rhs){
  int n=rhs.l;
  CS[] lhss;
  bool ans,res;
  CS c;
  CS sup = rhs.dup;
  foreach(t; 2 .. n+1){
    lhss.length = 0;
    superset(sup,n-t+1);
    ans=is_irreducible_rule_rhs(true,sup,lhss);//need to generate every possible LHS
    if(ans){
      foreach(lhssit;lhss){
        c=combine(lhssit,rhs,t);
        res=is_rule_rhs(c); 
        if(res){
          return 1;}}}}
  return 0;}

//***************************** function is_rule_rhs ********************************
//The function is_rule_rhs determines whether or not the CS rhs
//is the RHS of a rule, and this boolean value is returned.
bool is_rule_rhs(const ref CS rhs){
  bool ans;
  CS[] lhss;
  ans=is_irreducible_rule_rhs(0,rhs,lhss);
  if(ans)return 1;
  else ans=is_reducible_rule_rhs(rhs);
  if(ans)return 1;else return 0;}

//****************************** function compare **********************************
//Order relation for sorting rules: Compare first by machine states of the LHS's. If
//these are the same compare by pointer positions of the LHS's, if these are equal
//and the pointer is at 1, compare by symbol strings on the "tape", and if the pointer
//is not at 1, compare by the reversed symbol strings on the "tape".
bool compare(const ref IRR rule1,const ref IRR rule2){
  if(rule1.c1.s!=rule2.c1.s){
    return rule1.c1.s< rule2.c1.s;}
  else if(rule1.c1.p != rule2.c1.p){
    return rule1.c1.p < rule2.c1.p;}
  else if(rule1.c1.p==1){
    return rule1.c1.t < rule2.c1.t;}
  else{
    char[] rule1_string_rev=rule1.c1.t.dup;
    reverse(rule1_string_rev);
    char[] rule2_string_rev=rule2.c1.t.dup;
    reverse(rule2_string_rev);
    return rule1_string_rev < rule2_string_rev;}}

//************************* function apply_rules ************************************
//"apply_rules" applies the previously found IRR up to length j to carry out substitution
//steps for the TM computation starting from the LHS named lhs.
//Do this repeatedly until one of the following
//results occurs: (1)pointer moves outside the length of tape with known symbols,
//to the right (R) or left(L).
//(2) a halt condition occurs (H), (3) an infinitely repeating cycle occurs(C).
//The result is a new rule with the stopping condition (LRHC) indicated and
//the numbers of derivation and machine steps involved. In the case C there
// is no final CS. In the output there must be one, but C is
//indicated showing that it is not really final.
//The new rule is added to IRR, because it must be irreducible
//as the result of the correct functioning of this computer program.
void apply_rules(const ref CS lhs){//cslist is working space
  Array!CS cs_array = make!(Array!CS)();
  int n_steps=0;//# derivation steps
  int nm=0;//# machine steps
  CS cs=lhs.dup;
  cs_array.insertBack(cs.dup);
  bool match;
  int j=lhs.l;
  IRR irr2;
  char d='0';
  for(;;){//repeatedly apply appropriate rules to continue computation
    if(cs.p==0){d='L';break;}
    if(cs.p>cs.l){d='R';break;}
    match=0;
    for(int k=j-2;k>=0;--k){//find the longest applicable rule
      foreach(irr3;irreducible_rules[k]){
        if(subset(cs,irr3.c1)){match=1;
          irr2 = irr3.dup;
          break;}}
      if(match==1)break;}
//match now indicates if a matching rule has been found. This expected
//to be true always
    if(!match){
      throw new Exception("Error: no matching rule found");}
//Do substitution. The first position is element 0 as far as replace is concerned
    if(cs.p==1){
      foreach(i;0 .. irr2.c2.l){
        cs.t[i]=irr2.c2.t[i];}}
    else if(cs.p>1){
      foreach(i;0 .. irr2.c2.l){
        cs.t[j-irr2.c2.l+i]=irr2.c2.t[i];}}
    cs.s=irr2.c2.s;
    cs.p+=irr2.c2.p-irr2.c1.p;
    cs.l=j;//cs is now the result of applying rule irr2 to previous cs
    ++n_steps;
    nm+=irr2.n_machine;
    if(count(cs_array[],cs)>0 || irr2.sig=='C')d='C';
    cs_array.insertBack(cs.dup);
    if(irr2.sig=='H'){d='H';break;}
    if(d=='C')break;
//if this CS was found before, there
//is an endless stationary loop so go to next case.
    }
//Each computation has now ended in state L,R,H or C, meaning the pointer is
//at the left,right, the computation halts or does not terminate, respectively.
//Add new rule to list
  IRR r;
  r.c1=lhs.dup;
  r.c2=cs.dup;
  r.n_derivation=n_steps;//# subtitutions needed to derive rule
  r.n_machine=nm;
  r.sig=d;//and add new symbol L,R,C, or H
  ulong len = irreducible_rules[j-1].length;
  irreducible_rules[j-1].length++;
  irreducible_rules[j-1][len]=r.dup;
  return;}

//********************************* class map ******************************************
//This object is used to construct all the LHS's of new IRR that are derived from the given
//CS object cs.
struct map{
  CS cs;
  bool[] at_x,at_ptr;
  void initialise(int nsy){at_x.length = nsy;at_ptr.length = nsy;}
  map dup()const{
    map m;
    m.cs = this.cs.dup;
    m.at_x = this.at_x.dup;
    m.at_ptr = this.at_ptr.dup;
    return m;}
  }

//******************************************* function slist_print *******************************
//prints a SList of map objects.
void slist_print(SList!map lst){
  foreach(ref map;lst){//foreach calls a mutable method that won't compile if lst is const.
    write(map);}
  writeln("");}

//******************************************* function slist_print *******************************
//prints an array of CS objects.
void slist_CS_print(CS[] lst){
  foreach(cs;lst){//foreach calls a mutable method that won't compile if lst is const.
    write(cs);}
  writeln("");}

//************************************** function add **********************************
//Add a new CS to the current set of CS's and update this set's representation as a list
//of maps. Each map specifies a CS and the set of new symbols that can be added to generate
//LHS's of new IRR of length greater by 1.
//Algorithm:
//Add the CS to the list lst in the obvious way i.e. if the CS is not in lst
//add it to lst with the symbol as a map; otherwise add the new symbol to the map having the CS
  void add(SList!map lst,const ref CS cs,bool q){//q is the pointer position for the
//rhs of the rule with lhs equal to cs. It is needed only for the case when l=1.
//(0 and 1 mean false and true respectively)
  CS cs2=cs.dup;
  char sy2;
//Record the pointer symbol (sy) in cs in the map associated with
//"cs with the pointer symbol removed" (cs2) if it is already in the
//list of maps & return.
    char sy=at_ptr(cs2);
    del_sy(cs2,q);
    foreach(lstit;lst){
      if(same(lstit.cs,cs2)){
        lstit.at_ptr[to!int(sy)-97]=1;
        return;}
}
//otherwise
    map mymap;
    mymap.initialise(nsy);
    mymap.cs=cs2.dup;
    CS cs3;
    foreach(i;0 .. nsy){
      mymap.at_ptr[i]=0;
      cs3=cs2.dup;
      sy2 = to!char(i+97);
      add_at_x(cs3,sy2);
      mymap.at_x[i]=is_rule_rhs(cs3);
}
    mymap.at_ptr[to!int(sy)-97]=1;
    lst.insertFront(mymap.dup);
    }

//********************************* main program **********************************************
void main(string[] args){
  writeln("This is TIEv1.2 copyright (C) 2017 John Nixon.\nThis program comes with ABSOLUTELY NO WARRANTY;\nThis is free software, and you are welcome to redistribute it\nunder certain conditions; for more information see the source code file.\n");
  if(args.length!=2){
    writeln("Usage: <directory and program name>  <input file for Turing Machine>");
    writeln("For example from the same directory as the program:");
    writeln(" ./<executable program name> <input file for Turing Machine>");
    writeln("See the initial comments in the program source file for more information.");
    writeln("The information in the file of the Turing Machine must be presented in the following");
    writeln("order with each element separated from the next by any number (including zero) whitespace characters (tabs spaces newlines etc).");
    writeln("This allows great flexibility of presentation:");
    writeln("Number of TM states, Number of TM symbols, then for each combination of these:");
    writeln("Old state,symbol read,new state,symbol printed,direction of movement (L or R) or halt (H).");
    writeln("For example\n3 \n2 \n1a2bR\n1b1bH\n2a3bR\n2b3aL\n3a1aL\n3b1aR\n");
    writeln("For verification, the program's interpretation of the user specified TM is printed at the beginning of the program operation.");
return;}
    
  string inputfilename=args[1];
  int count;
  File infile = File(inputfilename,"r");
  if(!exists(inputfilename)){writeln("I cannot find file ",inputfilename);return;}
  char[] outputfilename=can_write(inputfilename,"_out.txt");
  File of;//output file;
  of.open(outputfilename.idup,"w");
  int j,n,opt;
  int nst,c;
  char[] str;
  IRR r;
  infile.readf(" %s",&nst);infile.readf(" %s",&nsy);
  c=nsy*nst;
  char[] line;
  ulong len1;
  irreducible_rules.length = 1;
  write("See the documentation in the program source file for the notation.\n");
  of.write("See the documentation in the program source tie_v1.2.d file for the notation.\n");
  writeln("The Turing Machine table expressed as IRR of length 1");
  foreach(oc;0 .. c){
    infile.readf(" %d",&r.c1.s);
    r.c1.l=1;
    r.c1.t.length=1;
    infile.readf(" %s",&r.c1.t[0]);
    r.c1.p=1;
    infile.readf(" %d",&r.c2.s);
    r.c2.l=1;
    r.c2.t.length=1;
    infile.readf(" %s",&r.c2.t[0]);
    infile.readf(" %s",&r.sig);
    if(r.sig=='L')r.c2.p=0;else if(r.sig=='R')r.c2.p=2;else r.c2.p=1;
    r.n_derivation=1;r.n_machine=1;
    irreducible_rules[0]~=r.dup;
    writeln(r);
}
  write("\nEnter the maximum length of derived computation rules: ");
  input_int(n);
  write("\nEnter 1 for showing all IRR, 2 for showing only IRR of type LL, or 3 for showing only IRR of type RR: ");
  input_int(opt);
  irreducible_rules.length = n;
  CS cs;
  auto lst_map = make!(SList!map)();
  map mymap;
  write("\nThe numbers of irreducible regular (computation) rules");
  of.write("\nThe numbers of irreducible regular (computation) rules");
  write("\n(IRR) derived from this Turing Machine for different tape lengths are as follows:");
  of.write("\n(IRR) derived from this Turing Machine for different tape lengths are as follows:\n");
  writeln("\nSee the output file "~outputfilename~" for the list of IRR obtained.");
//carry out analysis for the required number of iterations
  foreach(i;1 .. n){//given all irreducible rules (IRR) of length i (index j),
//find all extensions of them to length i+1.
    j=i-1;//
    lst_map.clear();//error here now ok after initialising with make!
    count=0;//initialise count of the number of IRR found of length i.
    foreach(r1;irreducible_rules[j]){
     // add <cs,sy> to a list of pairs "map"<CS,subset of the symbols>}
      if((j==0 && r1.sig!='H') || (j>0 && (r1.sig=='R' || r1.sig=='L') && ((r1.c1.p==1 && r1.c2.p>2) || (r1.c1.p>1 && !r1.c2.p)))){//j==0 or r is type LR or RL
        add(lst_map,r1.c1,r1.c2.p>0);
}}
    if(lst_map.empty)break;
    foreach(map1;lst_map){
      foreach(i1; 0 .. nsy){
        if(!map1.at_x[i1])continue;
        foreach(k;0 .. nsy){
          if(!map1.at_ptr[k])continue;
          cs=map1.cs.dup;
          add_at_x(cs,to!char(i1+97));
          add_at_ptr(cs,to!char(k+97));
          apply_rules(cs);//adds a new rule to irreducible_rules
          count++;
}}}
    writeln("length: ",i+1," # IRR = ",irreducible_rules[i].length);
    of.writeln("length: ",i+1," # IRR = ",irreducible_rules[i].length);
}
  if(opt==1)of.write("All IRR are shown\n");
  if(opt==2)of.write("Only IRR of type LL are shown\n");
  if(opt==3)of.write("Only IRR of type RR are shown\n");
  foreach(i; 0 .. n){
    if(irreducible_rules[i].length!=0){
      if(i)of.writeln("Rules of length ",i+1);
      else of.writeln("The Turing Machine table expressed as IRR of length 1");
      sort!(compare)(irreducible_rules[i]);
      foreach(it;irreducible_rules[i]){
        if((opt==1)||(opt==2 && it.c1.p==1 && it.c2.p==0)||(opt==3 && it.c1.p==it.c1.l && it.c2.p==it.c2.l+1))of.writeln(it);}}}//modified to only print IRR of type LL or RR or all
  return;}