/*Program tm_dev.d to generate from a Turing machine the results produced by the development algorithm.
Date 2026-07-14
Before it can be used this program must be compiled with D (dlang.org)
I did the following on my mac: 
(1) Install homebrew (see docs.brew.sh)
(2) Install the compiler ldc by typing
Install the compiler with "brew install ldc"
This program was written in D and
originally had extension .d, but I prefer to keep it on the web as a .txt file and rename it before compilation. 
so do for example the following in a terminal program that takes text commands:
$mv tm_dev.txt tm_dev.d
Run the compiler for this program with the command ldc2 tm_dev.d
Then my program can be run with ./tm_dev <input_file_name>

The layout of this file is as follows:
(1)Copyright notice and literature references
(2)History of different versions what they do including the current one, in reverse order.
(3) The program code itself which is divided as follows
(3.1) Global variables and library imports
(3.2) Class definitions
(3.3) Write functions for the classes
(3.4) Other functions
(3.5) The main function which is where the program execution begins.

 Copyright (C) 2018 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/>.

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

a second paper continuing this study has now been published

Mathematica Aeterna, (2017) Vol. 7, no. 1, 19 - 56 (Paper 2)

Program modifications

Comments on D:
Function parameters: "ref" is sometimes needed to ensure proper functioning of functions using 2-way information flow
even if the arguments are ref types, so use it always for 2-way flow.
I use "out" for output-only.
I don't use "in" because it is confusing because it is unfortunately almost synonymous with "const", not just copying
input variables which is what the semantics suggests. It should be for input-only.
I use const instead.
You cannot declare a variable conditionally without restricting the scope of that variable to the
code in the conditional block. Could the scope of that variable be the next outer scope instead?
*/

import std.stdio;
import std.algorithm;
import std.string;
import std.file;
import std.conv;
import std.typecons;
import std.format;

//****************************************************************************************************
//Global variables: and definitions 
//Those used throughout:
File of;//output file;
int nsy, n;//# symbols, length beyond which dev skips over.
//bool lminus;//if true it reduces the length of the string of symbols by 1 for detecting a moving cycle. (See paper)
char[] index;
char[] question;
int nst;//# machine states
int nc = 0;//the number of branches that do not have cycles and would be continued if N was larger.
int elim;//limit on the value of e which is the number of symbols truncated to get a match.
bool halt;//The TM halts because no rule matches the CS.
bool limit, cycle;//True if any limits are set on N or e, false otherwise, and indication of cycling.
Rule [] TMrules;//TM definition rules
Rule [][] rulesL, rulesR;
CS[][] csw;//CS workspace containing the history and context of each computation path.
//The recursive function "dev" generates all the new results of the development algorithm.
//dev uses and can reuse memory space that does not have to be declared
//for each call and is conveniently packaged into one structure. The Type name is Store, and the instance is called st.
//alias Store = Tuple!(CS[], "L", bool, "right_at_end", CS[], "one_step_ori"); 
//Store st;
//alias int_pair = Tuple!(int, "j1", int, "j2");
//alias NOT = Tuple!(CS, "new_ori", int, "j1", char, "alpha");//new origins triplet
//alias NOOCO = Tuple!(CS, "cs0", NOT[], "nota");//new origins one cycle output
//************************** class 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.
class CS{
  char m = ' ';//to be used for indicating an end CS by setting m = '*'
  int s = 0;//state
  int p = 0;//pointer position
  int l = 0;//length of tape given
  char [] t = [];//part of tape of specified length
  
  @safe final this(const char m, const int s,const int p,const int l,const char[] t){
    this.m = m;
    this.s = s;
    this.p = p;
    this.l = l;
    this.t = t.dup;}

  @safe final this(){ 
}//needed for calling 'new' without an argument to create a default class object

  @safe final CS dup() const {return new CS(m,s,p,l,t);}

//Order relation for sorting CS's: Compare first by pointer positions. If
//these are the same compare by machine states, if these are equal
//and the pointer is at the left ( <= 1), compare by symbol strings on the "tape", and if the pointer
//is at the right ( >= l), compare by the reversed symbol strings on the "tape". This is such that the most
//significant end of the tape is the end closest to the pointer. Then truncation at the other end does not alter the sort order.
  final int opCmp(ref const CS rhs) const{
    if (p != rhs.p) return p - rhs.p;
    else if(s != rhs.s)return s - rhs.s;
    else if (p <= 1){
      if (t != rhs.t) {
        return t < rhs.t ? -1 : 1;} else return 0;}
    else if (p >= l){
      char [] str1 = t.dup;
      char [] str2 = rhs.t.dup;
      if(str1 != str2) {
        return reverse(str1) < reverse(str2)? -1 : 1;}else return 0;}
    else {writeln("Error ocurred in opCmp"); return 0; }}

//This is needed though it seems superfluous! needed to equality test class objects by their values
  @trusted override bool opEquals(const Object o) const {
    auto rhs = cast(CS)o;//not allowed in safe code
    if(s != rhs.s) return false;
    else if(p != rhs.p) return false;
    else if(l != rhs.l) return false;
    else if(t != rhs.t) return false;
    else return true;}
}
/*
//***************************************** class CS_triplet ****************************
class CST{//CS triplet
  CS cs1;
  CS cs2;
  CS cs3;
  final this(){}
  
  @safe final this(ref CS cs1, ref CS cs2, ref CS cs3){
    this.cs1 = cs1.dup;
    this.cs2 = cs2.dup;
    this.cs3 = cs3.dup;
  }

}
*/
//******************************** class Rule **************************************
//relation between two CS's cs1 and cs2 defined by the action of the TM.
class Rule{
  CS cs1;
  CS cs2;
  char sig = ' ';//L,R,H, or C i.e. left moving, right moving, halting, or cycling resp.

  @safe final this(ref CS cs1,ref CS cs2, const char sig){
    this.cs1 = cs1.dup;
    this.cs2 = cs2.dup;
    this.sig = sig;
  }
  @safe final this(){}

  @safe final Rule dup(){ return new Rule(cs1, cs2, sig);}

//Compare Rules by their RHS CS's (cs2) then by cs1. The reasoning is that cs2 is always available in Rule's and IGR's but cs1 is often not available
//eg in IGR's but could be used to disabiguate sort orders.
  final int opCmp(const ref Rule rhs){
    if(cs2 != rhs.cs2) return cs2 < rhs.cs2? -1: 1;
    else if(cs1 != rhs.cs1) return cs1 < rhs.cs1? -1: 1; else return 0;}
}
//*********************** Several write functions ****************************
//A "write" function is not supplied by default for classes, but is for structs. I wrote
//CS_write, array_CS_write, Rule_write, array_Rule_write to mimic the results of the default struct write functions to compare
//the program outputs with classes and structs (for CS's and Rules) and they agreed and other write functions were added later
//in the similar way.

void CS_write(File of,const ref CS cs){
  if(cs !is null){
    of.write("CS(");
    of.write(cs.m);
    of.write(cs.s);
    of.write(", ");
    of.write(cs.p);
    of.write(", ");
    of.write(cs.l);
    of.write(", ");
    of.write('"');
    of.write(cs.t);
    of.write('"');
    of.write(")");}
  else of.write("null CS");}

void array_CS_write(File of,const ref CS[] array){
  if(array !is null){
    of.write("[");
    foreach(ref x;array){
      of.write(" ");CS_write(of,x);}
    of.write(" ]");}
  else of.write("null CS[]");}

void Rule_write(File of,const ref Rule rule){
  of.CS_write(rule.cs1);of.write(" --> ");
  of.CS_write(rule.cs2);of.writeln();
  }

//********************************** 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)
@trusted 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);
        std.stdio.write("Enter the extra characters: ");
        readln(chars);chars=chomp(chars);//not allowed in safe code
        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)
@trusted 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);//not allowed in safe code
    ans=res[0];
    if(res.length==1){
      if(ans=='y')ret = true;
      else if(ans=='n') ret = false;}
    else{ans='*';}}
  return ret;
}

//*********************************** function 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.
 @trusted void input_int(ref int i){//ref is needed here
  bool error;
  char[] line;
  for(;;){
    line = chomp(readln().dup);//not allowed in safe code
    error = false;
    try{i = to!int(line);} catch (Exception){error = true;}
    if(!error) break;
    std.stdio.write("An error occurred. Please try again: ");}
}
//********************************* function add_at_ptr ****************************
//Add symbol sy to cs at the pointer position at end of symbol string.
//The routine assumes that the pointer is just off one end by one space 
//of the known symbols on the tape so that the added symbol never clobbers previous known symbols on the tape.
//This assumes that the length of the symbol string is >= 1.
//end is l or r for the left/right respective ends where the pointer is.
 void add_at_ptr(ref CS cs,const char sy, out char end){
  cs.t ~= sy;//add new symbol on the right hand end of the string of known symbols.
  end = 'r';
  if(cs.p == 0){//the pointer as at the left just off the end
    end = 'l';
    rotate(cs.t,1);//swaps added symbol from right to left end.  
    cs.p = 1;}//and the pointer is now at position 1.
//in the other case, (i.e. the pointer is at the right just off the end (cs.p >0) don't swap the added symbol round.
//and leave the pointer position unchanged.
//In both cases the state is the same as before and the length is increased by 1.
  ++ cs.l;
  }
//*********************************** function add_at_end ************************
//Add symbol sy to cs at the right(r) or left(l) end of the cs. The char ( r or l) dir (direction) deciding which
//is the third parameter.
  void add_at_end(ref CS cs, const char sy, const char dir){
    cs.t ~= sy;
    if( dir == 'l'){
      rotate(cs.t,1);
      ++(cs.p);}//if symbol is added on the left, everything else goes right by one space.
  ++(cs.l);
  }
//************************************* function del_at_ptr **********************
//Delete the symbol at the pointer in cs.
//The char dir is 'l' or 'r' if the pointer is at the left or right respectively.
//If the pointer is at the left or the length is 1, its position goes from 1 to 0.
void del_at_ptr(ref CS cs, out char dir){
   if(cs.p == cs.l && cs.l > 1) {//pointer is at right and length > 1
     -- cs.t.length;
     dir = 'r';}
   else if(cs.p == 1){//pointer is on left or the length = 1
     dir = 'l';
     cs.p = 0;
     rotate(cs.t, cs.l - 1);
     -- cs.t.length;}
   -- cs.l;}

//******************************** function rotate *********************************
//Rotates a char[] array of length l by r places to the right. 
@safe void rotate(ref char[] str,int r){
  int l=to!int(str.length);
  r = r % l;//reduce r mod l.
//  writeln("str.length = ",str.length);
//  writeln("str = ",str);
  if(r != 0){
    char[] temp = str.dup;
    temp.length = 2 * l - r;
    foreach(ref i;0 .. l - r)temp[i + l] = temp[i];//copy temp to the right by l places i.e. cyclically to not alter the original l values.
//    writeln("str = ",str," temp = ",temp, " l = ",l," r = ",r);
    foreach(ref i;0 .. l)str[i] = temp[i + l - r];}//Copy the values back shifting by r. str[0] = temp[l-r] = temp [-r] if temp is cyclically extended.
}

//******************************* function subset **********************************
//Returns whether cs1 is a subset of cs2 (includes equality)
@safe bool subset(const CS cs1,const 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(ref i;0 .. cs2.l)sub[i]=cs1.t[i + ll];
  return sub == cs2.t;}

//******************************* function match **************************************
//Returns whether or not a pair of CS's have configurations in common.
//Let j = i (tape position) - cs.p; this is the position relative to the pointer.
//These values have a range for each input CS. They overlap on the range
//max(1 - cs1., 1 - cs2.p)  to min(cs1.l - cs1.p, cs2.l - cs2.p)
//To convert tape positions to array indices subtract 1.
  bool match(const CS cs1, const CS cs2){
//    write("match: cs1 = ");CS_write(stdout,cs1);writeln("");
//    write("match: cs2 = ");CS_write(stdout,cs2);writeln("");
    if (!(cs1.s == cs2.s)){
//write("returning 0");
      return 0;}
    int ma = max(1 - cs1.p, 1 - cs2.p);
    int mi = min(cs1.l - cs1.p, cs2.l - cs2.p);
    for (int k = ma + cs1.p; k <= mi + cs1.p; ++k){
      if(cs1.t[k - 1] != cs2.t[k + cs2.p - cs1.p - 1]) {
//write("returning 0");
        return 0; break;}}
//    write("returning 1");
  return 1;}

//***************************** function truncate **************************************
//This removes x symbols from cs from the dir end where dir is 'l' or 'r' for left/right respectively.
CS truncate(ref CS cs, const int x, const char dir){
  if(dir == 'l'){
    cs.p -= x;
    rotate(cs.t, cs.l - x);}//brings symbols to be deleted to the right
  cs.l -= x;
  cs.t.length -= x;
  return cs;}

//******************************************* function apply_TM ******************************************
//This routine develops the computation from an existing end CS (the pointer is just off one end of the symbol string) with the new symbol alpha
//added at the pointer position, and continues as far as possible without specifying any new symbols on the tape.
//This is done while updating the variable csw.
//apply_TM carries out TM steps repeatedly until one of the following
//conditions occurs: (1) the pointer moves outside the length of tape with known symbols,
//to the right (R) or left(L), (2) a halt condition occurs (H), or (3) an stationary infinitely repeating cycle occurs(C).

//The result is a new rule with the stopping condition (LRHC) indicated in "sig" and
//the number of 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.
//Each computation will end in one of the conditions L,R,H or C as above.

//It also checks the final result (the current CS) for potentially repeating moving cycles that could occur if appropriate new symbols appear.
@trusted void apply_TM(const char alpha){
  halt = 0;//Assume the TM does not halt.
  bool mat;//result of match routine for a pair of CS's
  char end;
  int m;//the number of TM steps in a cycle.
  int minp, maxp;
  CS bcs, z, start;
  Rule rule2;
  z = csw[csw.length - 1][0].dup;
  add_at_ptr(z, alpha, end);//add symbol alpha to final (current) CS in csw.
  csw[csw.length - 1] ~= z;
  csw[csw.length - 1][1].m = '*';//put mark indicating it is an end CS
//Prior to updating csw with the effect of new TM steps, the new symbol alpha must be added to a new CS placed at the bottom of each sub-array of csw.
//In the last one alpha is added at the pointer and the side where this is indicates the end of the string where alpha is added as above.
//start is the current starting CS with the pointer just off one end.
  foreach(i, ref list; csw){
    if(i != csw.length - 1){
      bcs = list[list.length - 1].dup;//bottom (final) CS
      add_at_end(bcs, alpha, end);//on same side as in current CS 
      list ~= bcs.dup;}}
  start = csw[csw.length - 1][1].dup; 
//do main loop
  for(;;){
    if(start.t == "" || start.p == 0 || start.p > start.l)break;//in these cases the symbol read is not yet known so terminate routine
    mat = 0;
//of.writeln("test1");
    foreach(ref rule; TMrules){
      if(match(start, rule.cs1)){mat = 1;
        rule2 = rule;//rule (the next TM step) next goes out of scope so dup not needed provided rule2 is not altered bolow.
        break;}}
//mat now indicates if a matching rule has been found. This should be true always
    if(!mat){halt = 1; break;}//this means no rules match so a halting condition has been found.
//Do substitution. This updates the current CS start. The first position is element 0 as far as replace is concerned
    start.t[start.p - 1] = rule2.cs2.t[0];
    start.m = ' ';//this deletes mark indicating an end CS
    start.s = rule2.cs2.s;
    start.p += rule2.cs2.p - 1;//increment of pointer position. This works because rule.cs1.p = 1 for single TM steps
//start.l is unchanged. start is now the result of applying rule2 to the previous value of start
    csw ~= [start.dup];//copy into csw the new CS resulting from the last TM step.
//test for a stationary cycle i.e. the identity of start with a previous value of it.
    cycle = 0;//the bool variable cycle means a cycle has been found. Begin by assuming no cycle found.
    foreach(i,list; csw){
      if(i != csw.length - 1){//need to eliminate the last comparison which is an identity.
      z = list[list.length - 1];//final element of list a sub-array of csw
      cycle = 1;
      if(z.s != start.s)cycle = 0;
      else {if(z.p != start.p)cycle = 0;
        else if(z.t != start.t)cycle = 0;}//start.l is not altered so no need to test for it.
      if(cycle) break;}}
    if(cycle) {
      break;}//beaks out of main loop
    }//ends main loop. 
//This happens when the pointer reaches just beyond the end of the known symbols on the tape. 
//The next section checks for repetition or cycle only involving the symbols that are visited between the earlier end CS and the current CS.
//In addition, a proper subset of these symbols can be used with the deleted symbols being furthest from the pointer in the current CS.
//This establishes a more complex type of cycle. 
//To do this go back from the current CS along the bottom of the columns of CS's in csw to look for a repetition while
//keeping track of the farthest position of the pointer from its position in the current CS.
//Generate all the cycles possible by comparing the current CS with all previous end CS's having the same state, having first deleted all symbols that were
//not involved in the computation. Keep deleting one symbol at a time from the end away from the pointer at the end of the computation until a match
//is reached or one of strings has length 0. If a match is found this loop ends.
//The notation on the arrow is number of extra symbols deleted, 't', number of TM steps between these CS's.
//Limits can be set on the length of the strings of symbols in the CS's, and the number of extra symbols that are deleted to get a match.
    int len = csw[csw.length - 1][0].l;//length of the string
    CS ocs, tocs, ccs, tccs;
    int e;
    of.write(index);of.write(": ");
    if(halt){of.write("Halt");} else{
//write the overall effect of the branch or stationary cycle:
      if(cycle){ of.write("stationary cycle: start = ");CS_write(of,start);of.writeln();}
        of.write("effect: ");
      m = to!int(csw.length - 1);
      CS_write(of,csw[0][csw[0].length - 1]);//write original CS that would lead to the current CS.
      of.write(" -");of.write(m);of.write("-> ");CS_write(of,csw[csw.length - 1][0]);of.writeln();//write current CS
      of.writeln("     cycles:");
//search for moving cycles with previous end CS's and search backwards to get most informative (longest) string for the cycle in each case.
      if(csw[csw.length - 1][0].p > 0){//if pointer is at right in the current CS
        minp = csw[csw.length - 1][0].l + 1;//pointer position
        for(int k = to!int(csw.length - 2); k >= 0; --k){//loop over all previous CS's
          ocs = csw[k][csw[k].length - 1].dup;//get copy of old CS being compared
          ccs = csw[csw.length - 1][0].dup;//get fresh copy of current CS
          m = to!int(csw.length - 1 - k);//the number of TM steps between ocs and ccs
          minp = min (minp, ocs.p);//keep running minimum
          tocs = truncate(ocs, minp - 1, 'l');//truncated CS's
          tccs = truncate(ccs, minp - 1, 'l');
          if(ocs.m == '*' && ocs.s == ccs.s){//check for a match if the states agree and the old CS is an end CS.
            e = 0;
            for(int l = minp; l > 0; --l){//loop over different numbers of extra symbols deleted.
              if(match(ocs,ccs)){
                cycle = 1;
                of.write("     ");CS_write(of, tocs);of.write(" -");of.write(e);of.write('t');of.write(m);of.write("-> ");CS_write(of, tccs);of.writeln();//write cycle
                break;}
              ++ e;
              if(limit && e > elim){
                of.writeln("******* e > elim search terminated *******");
                break;}
              truncate(ocs, 1, 'l');
              truncate(ccs, 1, 'l');}}}}
      if(csw[csw.length - 1][0].p == 0){//pointer at left in current CS
        maxp = 0;
        for(int k = to!int(csw.length - 2); k >= 0; --k){
          ocs = csw[k][csw[k].length - 1].dup;//get copy of old CS being compared
          ccs = csw[csw.length - 1][0].dup;//get fresh copy of current CS
          m = to!int(csw.length - 1 - k);//the number of TM steps between ocs and ccs
          maxp = max (maxp, ocs.p);
          tocs = truncate(ocs, len - maxp, 'r');
          tccs = truncate(ccs, len - maxp, 'r');
          if(ocs.m == '*' && ocs.s == ccs.s){
            e = 0;
            for(int l = maxp; l > 0; --l){   
              if(match(ocs,ccs)){
                cycle = 1;
                of.write("     ");CS_write(of, tocs);of.write(" -");of.write(e);of.write('t');of.write(m);of.write("-> ");CS_write(of, tccs);of.writeln();//write cycle
                break;}
              ++ e;
              if(limit && e > elim){
                of.writeln("******* e > elim search terminated *******");
                break;}
              truncate(ocs, 1, 'r');
              truncate(ccs, 1, 'r');}}}}}
}//ends function
//************************************************ function dev *****************************************************
//Index is the state and symbols of a branch of the search tree written in the order they are used to arrive
// at any branch i.e. the state, then each symbol as it is needed at the pointer position to continue the computation
//where no symbol in that position has been read before,
//whether it is on the left or right end of the string. The computer output
//has the index values sorted into lexicographical order so it is easy to find the computations for any branch.
//dev maintains index as well as implementing the symbol limit N.
  void dev(){
    char alpha, end;
    if(limit && csw[csw.length - 1][0].l >= n){
      writeln("n = ",n);
      ++ nc;//count the number of times the search for cycles is terminated by the limit n on the number of symbols per CS.
      of.writeln("**Search terminated -- lines too long**");}
    else{
      foreach(sy; 0 .. nsy){
        alpha = to!char(sy + 97);//convert sy to a symbol and 
        index ~= alpha;//maintains index
        apply_TM(alpha);
        if(!cycle && !halt){//no match so carry on developing further "up" the search tree
          dev();}
//undo the effect of the last call of apply_TM on csw.
//First remove all elements from csw that have length 1.
      while(csw.length >= 1 && csw[csw.length - 1].length == 1) -- csw.length;
//Then remove the last element of all the remaining elements of csw.
      if(csw.length > 0){
        for(int k = to!int(csw.length - 1); k >= 0; --k){
        -- csw[k].length;}}
      -- index.length;//delete last symbol of index.
        }}}

//********************************* main program **********************************************
void main(string[] args){
//1 Initial statement output and dialogues 
  writeln("This is tm_dev copyright (C) 2026 John Nixon,to generate from a Turing machine the results of the development algorithm described
on the web at https:www.bluesky-home.co.uk/Turing_machine_analysis.pdf.\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 informat");
    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) of");
    writeln("whitespace characters (tabs spaces newlines etc).");
    writeln("to allow great flexibility of presentation:");
    writeln("Number of TM states (nst), Number of TM symbols(nsy), 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("The states are 1,2,... nst, and the symbols are a,b,c,...");
    writeln("The lines of the TM machine table must be sorted first by old state increasing, and then by");
    writeln("symbol read in alphabetical order a to z.");
    writeln("This last requirement simplifies the algorithm for searching for reverse TM steps");
    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 first shown.");
    return;}
  string inputfilename=args[1];
  File infile = File(inputfilename,"r");
  if(!exists(inputfilename)){writeln("I cannot find file ",inputfilename);return;}
  char[] outputfilename=can_write(inputfilename,"_out.txt");
  of.open(outputfilename.idup,"w");
  infile.readf(" %s",&nst);infile.readf(" %s",&nsy);
  int c = nsy*nst;
  char [] question;
  int opt;  
  of.writeln("The Turing Machine table expressed as Rules of length 1");
  writeln("The Turing Machine table expressed as Rules of length 1");
  stdout.write("See the documentation in the program source file for the notation.\n");
//2 Reading in the input Turing Machine file
  writeln("c = ",c); 
  foreach(ref oc;0 .. c){
    Rule r1 = new Rule;//"new" is needed (a class object) to avoid a segmentation fault with r1.dup
    CS cs1 = new CS;//new is needed here
    infile.readf(" %d",&cs1.s);
    cs1.l=1;
    cs1.t.length = 1;
    infile.readf(" %s",&cs1.t[0]);
    cs1.p=1;
    CS cs2 = new CS;    
    infile.readf(" %d",&cs2.s);
    cs2.l=1;
    cs2.t.length = 1;
    infile.readf(" %s",&cs2.t[0]);
    infile.readf(" %s",&r1.sig);
    if(r1.sig == 'L')cs2.p = 0;else if(r1.sig == 'R')cs2.p = 2;else cs2.p = 1;
    r1.cs1 = cs1;
    r1.cs2 = cs2;
    TMrules ~= r1;
    Rule_write(stdout,r1);
    Rule_write(of,r1);
}
//dup not needed because r1 goes out of scope next.
  question = "Do you want to enter limits on either the number of symbols in the CS's or the number of extra symbols\nto be
 deleted other than those not involved?".dup;
  limit = 0;
  if(yes(question)){
    limit = 1;
    write("\nEnter n the number of symbols that cannot be exceeded in the strings of symbols: ");
    input_int(n);
    stdout.writeln("n = ",n);
    of.writeln("n = ",n);
    write("\nEnter elim the maximum number of extra symbols that are deleted from the strings of symbols to get a match: ");
    input_int(elim);
    stdout.writeln("\nelim, the maximum number of extra symbols that are deleted from the strings of symbols to get a match = ",elim);
    of.writeln("\nelim, the maximum number of extra symbols that are deleted from the strings of symbols to get a match = ",elim);}
  foreach(st; 1 .. nst + 1){
    CS start = new CS(' ',st,0,0,"");//convert st to a CS called start
    index = [to!char(st + 48)]; 
    csw.length = 1;
    csw[0].length = 1;
    csw[0][0] = start;
    dev();}
  of.writeln("nc = ",nc);
  writeln("nc = ",nc);
}//ends program