/* Date: 2024-03-14
This a cut down version of TIE to just find all the origins of a CS by running the TM backwards as far as possible

Allowing for T1 and T2 to have different lengths appears to be done and correct.
The dialogues have changed and I've done a lot of tidyng up, i.e. deleting out of date
comments and unwanted commented out code. The IGR(2) are now correct. 
This is the computer program TIE (Turing machine Inference Engine) version 3.0 draft. It employs
the strategies described in the latest draft manusript of the Turing Machine analysis paper to be found
on www.bluesky-home.co.uk
It generates IRR's and IGR's (see references and latest draft paper) from a Turing Machine. This works for
non-terminating TM's, and it has not all been checked for TM's that halt. TM's that don't halt are a simpler concept
that it makes sense to analyse first, and the analysis of halting TM's could be obviously based on this.

This program must be compiled before it can be used. It 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. To compile
it go to dlang.org and download one of the compilers (I use dmd)
then do for example the following in a terminal program that takes text commands:
$mv tie_v2_0.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
An alternative if the user is familiar with the dialogue is to ignore the screen output
and redirect the output to any file eg
$./tie TM_file_name > out.txt, and then put the answers to the dialogues.

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).
The lines of the TM machine table must be sorted first by old state increasing, and
then by symbol read in alphabetical order a to z.

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

New in version 3.0:
The latest draft of the paper describes the construction and use of IGR's (IRR generating rules). These are rules that
describe the generation of new IRR's from old ones using the general procedure called F in the paper. This version of the
program generates these IGR's up to a given length. The motivation for doing this is that a small number of IGR's could be
combined to generate a large indeed infinite number of IRR's. It is unknown at this stage under what conditions on a TM
is the number of IGR's for that TM finite.

New in version 2.1:
Foreach loops over arrays of class objects do not need ref to avoid unnecessary copying.
them to exactly mimic the output from the default write functions for structs to aid in program testing, but
which could now be modifed if needed.
I did this to understand the difference between structs and classes, and to attempt to write the program
more efficiently. I have simplified the code a little and eliminated some unnecessary copying, but
probably not much. I was motivated by the elegant way in which I could implement Tarjan's algorithm with a class that was much more awkward with a struct.
I have almost always used ref parameters for functions to ensure 2-way passing of information though this is sometimes unnecessary. I think this should be the default with the use of const where possible to
aid in undertanding the program.
 
New in version 2.0:
The procedure for generating the IRR's has been changed to include generating the origins of the IRR's i.e. the IRR's are now
represented as triplets. This gives a more informative result providing the proof of the
reachability of the LHS's of the IRR's and the algorithm has been changed as a result and
is now much easier to describe. It also runs about twice as fast as version 1.3 which is partly due to avoiding the
unnecessary copying of IRR's through the default method D has for copying objects (pointer
copies) instead of physical copies obtained with .dup. I had concerns about doing this at
first until I realised that it is quite easy to check the program for the absence of  "back doors"
i.e. other variables that point to the same memory that could be used to change such a variable. There
will often be such other variables initially and it must be checked that they go out of scope without modifying
the variable of interest. This mostly deals with my earlier comment about .dup.
New in version 1.3: the IRR's are printed with the additional "L" or "R" giving the
pointer position on the LHS of the IRR. This is just a convenience because the pointer
position is included as before, but the 'type' of the rule e.g. LL, LR, RL or RR can now be
read off quickly after the second CS e.g. to determine if the rule has type RL or LR which allows
it to be extended by an additional symbol and not be reducible.

New in version 1.2:
(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.

The original version 1.1 was based on 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.

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;

//Global variables:
File of;//output file;
int nsy;//# symbols
int nst;//# machine states
IRR [][] irrs = new IRR[][0];//The set of IRR's for the TM, used by main and apply_rules

//************************************************ Store **********************************************************
//The recursive function "new_origins" was probably the most difficult part of the program to write and the most important. 
//It generates all the new endpoints of the reverse computation from a given CS as a result of adding a single extra symbol
//to the finite part of the TM machine tape considered. new_origins 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!(int, "count" ,bool, "inside", bool, "dircheck", CS[], "L", bool, "cycle",bool, "right_at_end", bool, "left_at_end", bool, "cond_1", bool, "cond_2", int, "j", int, "ind", int, "j1", CS[], "one_step_ori", bool, "right_at_start"); 
Store st;

//alias int_pair = Tuple!(int, "j1", int, "j2");

void Store_write(const ref Store st){
  write("\n\ninside = ",st.inside);
  write("\ncount = ",st.count);
  write("\ndircheck = ",st.dircheck);
  write("\nL = ");array_CS_write(stdout,st.L);
  write("\ncycle = ",st.cycle);
  write("\nright_at_end = ",st.right_at_end);
  write("\nleft_at_end = ",st.left_at_end);
  write("\ncond_1 = ",st.cond_1);
  write("\ncond_2 = ",st.cond_2);
  write("\nj = ",st.j);
  write("\nind = ",st.ind);
  write("\nj1 = ",st.j1);//extreme pointer position counted from the alpha end of the string st. pointer starts at position 0.
  write("\none_step_ori = ");array_CS_write(stdout,st.one_step_ori);
  writeln("\nright_at_start = ",st.right_at_start);}

alias NOT = Tuple!(int, "count", CS, "new_ori", int, "j1", char, "alpha");//new origins one cycle output
alias NOOCO = Tuple!(CS, "cs0", NOT[], "nota");//new origins 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{
  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 int s,const int p,const int l,const char[] t){
    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(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 IRR **************************************
//relation between two CS's cs1 and cs2 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's). Later the
//array of CS's cs0 was added to the definition. These are all the CS's that lead by
//one or more TM steps to cs1.
class IRR{
  CS[] cs0 = [];
  CS cs1;
  CS cs2;
  char lsig = ' ';//pointer position in cs1 i.e. LHS: 'L' for 1 and 'R' for cs1.p > 1, blank if cs1.l=1
  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 = 0;//# derivation steps from cs1 to cs2.
  int n_machine = 0;//# machine steps from cs1 to cs2.

  @safe final this(ref CS[] cs0,ref CS cs1,ref CS cs2, const char lsig, const char sig, const int n_derivation,const int n_machine){
    this.cs0 = cs0.dup;
    this.cs1 = cs1.dup;
    this.cs2 = cs2.dup;
    this.lsig = lsig;
    this.sig = sig;
    this.n_derivation = n_derivation;
    this.n_machine = n_machine;}

  @safe final this(){ }

  @safe final IRR dup(){ return new IRR(cs0, cs1, cs2, lsig, sig, n_derivation, n_machine);}

//Compare IRR's by their LHS CS's (cs1).
  final int opCmp(const ref IRR rhs){
    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, IRR_write, array_IRR_write to mimic the results of the default struct write functions to compare
//the program outputs with classes and structs (for CS's and IRR's) 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.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 NOOCO_write(File of, const ref NOOCO nooco){
    write("\n nooco.cs0 = ");CS_write(stdout,nooco.cs0);
    foreach(y; nooco.nota){//new origins triplet array
      write("\n y.new_ori = ");CS_write(stdout,y.new_ori);
      write(" y.j1 = ",y.j1);
      write(" y.alpha = ",y.alpha);
      write(" y.count (# TM steps) = ", y.count);}}

//********************************** 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 == false)break;
    std.stdio.write("An error occurred. Please try again: ");}
}
//******************************** function rotate *********************************
//Rotates a char[] array of length l by r places to the right. 
@safe void rotate(ref char[] str,const int r){
  char[] temp = str.dup;
  int l=to!int(str.length);
  temp.length = 2 * l - r;
  foreach(ref i;0 .. l - r)temp[i + l] = temp[i];
  foreach(ref i;0 .. l)str[i] = temp[i + l - r];
}

//******************************* function st_init ************************************
//This initialises the Store object st.

void st_init(){
  st.count = 0;
  st.inside = false;
  st.dircheck = false;
  st.L = [];
  st.cycle = false;
  st.right_at_end = false;
  st.left_at_end = false;
  st.cond_1 = 0;
  st.j = 0;
  st.ind = 0;
  st.j1 = 0;}

//************************* function new_origins ************************************
//This is a version that has been modified so that the results in condition 2 are added to the set of results in nooco_object. These
//are the Residual CS's (RCS's) in the latest version of the paper of 2024.
//new origins is a recursive algorithm (i.e. it calls itself) to perform the following tasks, but more efficiently.
//Initially the CS cs is augmented by adding an arbitrary symbol (called alpha in the papers) at the 
//same end where the pointer is for the first call to new_origins. (This is the opposite end of the string to where
//the pointer is in IRR.cs1 i.e. its LHS.)
//All values of alpha are included in the search.
//Then new_origins finds all single backward TM steps from there and their
//resulting CS's. This is repeated for each branch recursively, until
//one of 4 conditions occurs in each branch. Condition 1: the pointer finishes at the opposite end from 
//where it started in the LHS which is the same end where it was in cs (CS A in the paper). Condition 2: the pointer finishes at the same end
//to where it started in the LHS which is the opposite end where it started in cs.
//Condition 3: the computation can go no further because backward steps from there are impossible.
//Finally, condition 4: a CS is reached that has been entered before.
//All the CS's arrived at as a result of branches ending in condition 1 constitute the array ori on exit.

//The algorithm is based on a depth-first search of the tree. An array of the cs's obtained on
//the way (L) must be maintained in order to check for a loop (condition 4). This has to be updated at each step of
//the search. The first time new_origins is called for a CS cs, L is empty. Otherwise L is the current list of all
//previous CS's in the backward search for origins, excluding the one that has just been or being found.
//The new element of L is added first for each call to new_origins.
//To avoid repetition, alpha is not actually added to the string until the pointer reaches the end.

//The initial pointer position in the original LHS i.e. right or left end of the string, is passed down through the variable
//"right_at_start" meaning the pointer is at the right in IRR.cs1 (its LHS) which is true or false. This is used to distinguish
//case 1 and case 2 when the pointer ends up at the opposite end or same end.
//n_symbols is the number of symbols involved in this calculation for this branch. This is needed in order to find
//the number of symbols involved in apply_F to express it with no redundant symbols.
//n_symb is the array of values of n_symbols, one for each branch. n_symb is empty on first calling new_origins.
//The variables cycle, right_at_end, left_at_end, cond_1, j, ind, n_symbols and one_step_ori are in a global structure st of type Store
//of which there is just one instance to avoid creating new variables each time new_origins calls itself.
//ref is needed for all parameters (value and reference types) to guarantee 2-way information flow
//and avoid new copies being used for each call.
//The values in ori, n_symb, and alpha in nooco_object at the first call do not affect the running of new_origins except that these
//values will be prepended to any subsequent values added to these arrays by new_origins. So in a sense they are
//"out" only variables, but not quite. They should be ideally declared as "append only" array arguments but this is not possible.
//
@trusted void new_origins(ref CS cs,ref NOOCO nooco_object){
  bool test;
  st.cycle = canFind(st.L,cs);//not allowed in safe code
  st.L ~= cs;
  st.right_at_end = cs.p == cs.l;
  st.left_at_end = cs.p == 1;
  st.cond_1 = (st.right_at_start && st.left_at_end) || (!st.right_at_start && st.right_at_end);//condition 1
  st.cond_2 = (st.right_at_start && st.right_at_end) || (!st.right_at_start && st.left_at_end);//condition 2
  if(st.cond_2){
    NOT noto;
    noto.new_ori = cs.dup;
    noto.alpha = '*';
    noto.count = st.count;
    noto.j1 = cs.l;
    nooco_object.nota ~= noto;}
  st.one_step_ori = [];
  ++ st.count;//increment TM step counter. This is the number of nested calls of new_origins needed to get each output CS.
//Note that condition 2 is already satisfied by the cs, this does not contribute an extra step so the counter increment takes place
//after the result is recorded in "nooco_object".
  if(!st.cycle && ((!st.right_at_end && !st.left_at_end) || st.cond_1)){//conditions under which current branch is not required to stop i.e.
// non-cycling or condition 1. This eliminates cycling and condition 2.
//get the array (one_step_ori) of all CS's ncs that go to cs in 1 TM step with the pointer on the tape and all CS's in ori that
//do so from a new pointer position just outside the existing tape. The latter includes 
//the extra symbol in place of the symbol alpha added.
    foreach(ref k2; 1 .. nst+1){//look for a possible reverse TM step
      foreach(ref k1; 0 .. nsy){//through the whole TM table
        st.j = (k2 - 1) * nsy + k1;//index of TM table row
        if(irrs[0][st.j].cs2.s == cs.s){//if the new TM state is the state of cs (1st condition for reverse step)
          st.ind = cs.p - irrs[0][st.j].cs2.p;//array index of symbol matched. st.ind + 1 =  (cs.p - 1 if TM step to be reversed goes right,cs.p + 1 otherwise)
          st.inside = st.ind >= 0 && st.ind < cs.l;//pointer position after reverse TM step is within symbol string, otherwise it is at alpha
          st.dircheck = (irrs[0][st.j].cs2.p == 2 && st.ind == -1) || (irrs[0][st.j].cs2.p == 0 && st.ind == cs.l);//checks that if condition 1 is true,
//the direction of the next reverse TM step takes the pointer just outside the current symbol string.
          test = (st.inside && irrs[0][st.j].cs2.t[0] == cs.t[st.ind]) || (!st.inside && st.dircheck);
          if(test){//if the new TM symbol is the symbol at ind (2nd condition for reverse step)
            CS ncs = new CS;
            ncs.s = irrs[0][st.j].cs1.s;//This would be k2 if TM table is written in order in file.
            ncs.p = st.ind + 1;
            ncs.t = cs.t.dup;
            if(st.inside){
              ncs.l = cs.l;
              ncs.t[st.ind] = irrs[0][st.j].cs1.t[0];
              st.one_step_ori ~= ncs.dup;}
            else{//reverse TM step takes pointer outside string, so terminating this branch of the search because these CS's
//don't get into one_step_ori.
//Find the number of symbols involved i.e. the length of the character string involved in finding
//the new origin in the current branch.
              if(st.right_at_start){//The TM is at the right hand end of the symbol string in the LHS (alpha is on left)
                st.j1 = 1;//find n_symbols (here called st.j1 because it is called j1 in the paper p10 - 12) i.e. the number of symbols used in the computation
                foreach(ref x; st.L) st.j1 = max(st.j1, x.p);
                st.j1 -= 1;}//because j1 = i1 - 1 is needed.
              else{//The TM is at the left in the LHS
                st.j1 = cs.l;
                foreach(ref x; st.L) st.j1 = min(st.j1, x.p);
                st.j1 = cs.l - st.j1;}
//find ncs when the new pointer position is just beyond the symbol string, remembering that if the
//reverse TM step goes left, then the new symbol is on the left increasing all the symbol positions by 1.
              ncs.l = cs.l + 1;
              ncs.t ~= irrs[0][st.j].cs1.t[0];
              if(st.ind == -1) {++(ncs.p); rotate(ncs.t,1);}//add irrs[0][j].cs1.t[0] at position 0 or at right end of string otherwise
              NOT noto;
              noto.new_ori = ncs.dup;
              noto.alpha = irrs[0][st.j].cs2.t[0];
              noto.count = st.count;
              noto.j1 = st.j1;              
              nooco_object.nota ~= noto;              
}}}}}}
//This is the recursive bit
    foreach(ref cs3;st.one_step_ori){
      new_origins(cs3, nooco_object);}
    if(st.L.length) {-- st.L.length; -- st.count;} //remove last item in L if there are any after all other branches of the search have ended. (this CS cannot be an intermediate CS) and decrement TM step counter.
//It terminates the branch and is appropriate just prior to back-tracking from a branch that has been completely searched, to follow another reverse TM step.}
}
//********************************* main program **********************************************
void main(string[] args){
//1 Initial statement output and dialogues 
  writeln("This is the little program called origins to run the TM backwards from a user supplied CS. copyright (C) 2024 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) 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;}
  int n_symbols;
  char alpha;
  char dir1, dir2;//direction for addition of new symbol(s) for the context strings dir1 will be used, for alpha 
//dir2 will be used. ( values will be 'L' or 'R' or possibly ' ' if is not needed).
  string inputfilename=args[1];
  File infile = File(inputfilename,"r");
  if(!exists(inputfilename)){writeln("I cannot find file ",inputfilename);return;}
  infile.readf(" %s",&nst);infile.readf(" %s",&nsy);
  int c=nsy*nst;
  char [] question;
  int q, n, opt;
  irrs.length = 1;
  stdout.write("See the documentation in the program source file for the notation.\n");
//  of.write("See the documentation in the program source tie.d file for the notation.\n");
  writeln("The Turing Machine table expressed as IRR's of length 1");
//2 Reading in the input Turing Machine file
  foreach(ref oc;0 .. c){
    IRR r1 = new IRR;//"new" is needed (a class object) to avoid a segmentation fault with r1.dup
    CS[] cs0;
    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.cs0 = cs0;
    r1.cs1 = cs1;
    r1.cs2 = cs2;
    r1.n_derivation = 1;
    r1.n_machine = 1;
    irrs[0] ~= r1;}//dup not needed because r1 goes out of scope next.
  NOOCO nooco_object;
  CS cs3 = new CS;
  char[] tape_string;
  char ans;
  bool ct;
  for(;;){
    write("\nEnter state: ");
    input_int(cs3.s);
    write("Enter pointer position: ");
    input_int(cs3.p);
    write("Enter length: ");
    input_int(cs3.l);
    cs3.t.length = cs3.l;
    write("Enter tape string: ");
    readln(cs3.t);
    cs3.t = chomp(cs3.t);
  


/*
@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;
}
*/
  char[] res;
  do{
    write("The arbitrary symbol will be added on the left (l) or right (r) of the string");
    write("\nEnter 'l' or 'r': ");
    res = chomp(readln().dup);
    ans = res[0];
    if(ans == 'l') st.right_at_start = 1;
    if(ans == 'r') st.right_at_start = 0;
    }
  while (ans!='l' && ans!= 'r');
//    question = "The arbitrary symbol called alpha will be added on the\nright or left end of the string. Is it to be added on the right?".dup;
//    if(yes(question)) st.right_at_start = 0; else st.right_at_start = 1;
//note this variable refers to the pointer position at some point where this is opposite
//to alpha
    nooco_object.cs0 = cs3.dup;
    st_init();
    nooco_object.nota.length = 0;  
    new_origins(cs3, nooco_object);
    NOOCO_write(stdout, nooco_object);}
  }//ends program