/*2021-11-22 This could be correct, but the comments are often out of date.
This is the computer program Tie version 3.0 draft version of the smarter version of tie versions 1 and 2. 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
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
.
/The original version is 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.
The latest version the program and draft papers are available from www.bluesky-home.co.uk under Turing
machine analysis. The first paper describing the theory behind it and what the
output means has been published (paper 1):
Mathematica Aeterna, (2013) Vol. 3, no. 9, 709 - 738 (Paper 1)
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.
Structs have been replaced by classes. This entailed recoding in connection with
their creation, and creating new write functions which are not defined by default for classes. I designed
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 has been changed to include generating the origins of the IRR i.e. the IRR are now
represented as triplets. This gives a more informative result providing the proof of the
reachability of the LHS's of the IRR 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 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 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 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.
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_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 .txt
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.
"out" is ok for output only.
"in" is unfortunately almost synonymous with "const", not just copying input variables. I use const.
*/
import std.stdio;
import std.algorithm;
import std.string;
import std.file;
import std.conv;
import std.typecons;
int nsy;//# symbols
int nst;//# machine states
// Global variable: The set of IRR for the TM, used by main and apply_rules
IRR [][] irrs = new IRR[][0];
IGR[][] igrs = new IGR[][0];//igrs[][i] is the set of IGR's that create the IRR(i+2) i.e. the IGR(i+2), so for example
//igrs[][1] is the set of IGR's that generate the IRR(3) i.e. the IGR(3) etc..
//************************************************ 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!(bool, "inside", bool, "dircheck", CS[], "L", bool, "cycle",bool, "right_at_end", bool, "left_at_end", bool, "cond_1", int, "j", int, "ind", int, "n_symbols", CS[], "one_step_ori", bool, "right_at_start");
Store st;
void Store_write(File of,const ref Store st){
write("\n\ninside = ",st.inside);
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("\nj = ",st.j);
write("\nind = ",st.ind);
write("\nn_symbols = ",st.n_symbols);
write("\none_step_ori = ");array_CS_write(stdout,st.one_step_ori);
writeln("\nright_at_start = ",st.right_at_start);}
alias NOT = Tuple!(CS, "new_ori", int, "n_symb", 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{
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){//there are 4 default "this" functions but they are not callable from my code
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" such that the truncation
//is for the least significant end of the tape in the sort order. Then truncation does not alter the sort order.
// @trusted override int opCmp(const Object o) const {
// auto rhs = cast(CS)o;//not allowed in safe code
final int opCmp(ref const CS rhs) const{
// write("\nCS.opCmp: this = ");CS_write(stdout,this);
// write("\nCS.opCmp: rhs = ");CS_write(stdout,rhs);
if (p != rhs.p) {
// write("\nCS.opCmp: return value = ");write(p - rhs.p);
return p - rhs.p;}
else if(s != rhs.s){
// write("\nCS.opCmp: return value = ");write(s - rhs.s);
return s - rhs.s;}
else if (p <= 1){
if (t != rhs.t) {
// write("\nCS.opCmp: return value = ");write(t < rhs.t ? -1 : 1);
return t < rhs.t ? -1 : 1;} else {
// write("\nCS.opCmp: return value = ");write("0");
return 0;}}
else if (p >= l){
char [] str1 = t.dup;
char [] str2 = rhs.t.dup;
if(str1 != str2) {
// write("\nCS.opCmp: return value = ");write(reverse(str1) < reverse(str2)? -1 : 1);
return reverse(str1) < reverse(str2)? -1 : 1;}else {
// write("\nCS.opCmp: return value = ");write("0");
return 0;}}
else {writeln("Error ocurred in opCmp"); return 0; }}//this should not ever happen (i.e. 2 <= p <= l-1). this does happen!
@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). 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 (c1).
override int opCmp(const Object o) const {
auto rhs = cast(IRR)o;
if(cs1 != rhs.cs1) return cs1 < rhs.cs1? -1: 1; else return 0;}
}
//************************************** class IRRP_set **************************************
//This class is for sets IRR patterns (IRRP) and the alpha value that generates them from another IRRP. see in my paper (2021 version).
//The RHS is unique but there can be many origins.
//The meaning of this is the IRRP given by $\text{set of origins}\to\text{lhs}\to \text{RHS}$ in latex. The origin and RHS in the paper
//include arbitrary strings $T_1$ and $T_2$ respectively. These are just place-holders and will not be represented in the class
//because the information is coveyed by the class name itself.
//This is for convenience when using apply_rules to generate RHS's. origins and
//rhs will be the same for different instances of the IRRP_set with different irr_2.
//The class IRRP_set is part of the class IGR below. class IGR is a superset of the IGR defined in the paper (2021 version).
//The extra variables are two ints, the int[], irr_2 and the alpha from the IRRP_set lhs in class IGR.
class IRRP_set{
char alpha = '*';//default value to permit sorting
CS[] origins = [];
// int[] n_symb = [];//The minimum number of symbols needed to represent the IGR of which this IRRP_set is a member of its rhs.
//This is an intermediate result and can only be obtained after
//origins and rhs have been obtained in the IRRP_set in the rhs of the newly derived IGR, and depends on the corresponding origin
//found at the same position in CS[] origins.
//n_symb is manifest from the IGR when finally obtained, and will then be the same for each origin, but an array is needed for the
//intermediate step.
CS rhs;
final this(const char alpha, CS[] origins, const ref CS rhs){
this.origins = origins.dup;
this.rhs = rhs.dup;
this.alpha = alpha;}
@safe final this(){}
final int opCmp(ref const IRRP_set irrps) const{//<,>,== should be exhaustive
if(alpha < irrps.alpha) return -1;
if(alpha > irrps.alpha) return 1;
if(rhs < irrps.rhs) return -1;
if(rhs > irrps.rhs) return 1;
if(origins[0] < irrps.origins[0]) return -1;
if(origins[0] > irrps.origins[0]) return 1;
return 0;}
// return cmp([alpha], [irrps.alpha]);}
final IRRP_set dup() { return new IRRP_set(alpha,origins,rhs);}
override bool opEquals(const Object o) const{//note this only checks origins and rhs, so it is not really equality
//but an equivalence
auto irrps = cast(IRRP_set)o;
write("\nIRRP_set.opEquals: origins = ");array_CS_write(stdout,origins);
write("\nrhs = ");CS_write(stdout,rhs);
write("\nalpha = ",alpha);
// write("\nn_symb = ");write(n_symb);
write("\nirrps = ");IRRP_set_write(stdout,irrps);
if(alpha != irrps.alpha) {write("\nby alpha return false"); return false;}
if(origins != irrps.origins) {write("\nby origins returning false");return false;}
if(rhs != irrps.rhs) {write("\nby rhs returning false");return false;}
write("\nreturning true");return true;}
}
//****************************************** class RHE *****************************************
//right hand element. An array of these form the rhs of an IGR.
class RHE{
IRRP_set irrp_set;
int n_TM_step = 0;
//n_TM_step is the number of TM steps from the original rhs to the final rhs on the right of the IGR that contains the RHE.
int n_Sub_step = 0;
//n_Sub_step is the number of substitution steps involved in this.
@safe final this(){}
final this(ref IRRP_set irrp_set, const int n_TM_step, const int n_Sub_step){
this.irrp_set = irrp_set.dup;
this.n_TM_step = n_TM_step;
this.n_Sub_step = n_Sub_step;}
/* override bool opEquals(const Object o) const {
auto rhs = cast(IGR)o;//not allowed in safe code
if(context != rhs.context) return false;
else if(lhs != rhs.lhs) return false;
else if(rhs != rhs.rhs) return false;
else return true;}
*/
final RHE dup(){ return new RHE(irrp_set, n_TM_step, n_Sub_step);}
final int opCmp(ref const RHE rhe){
return irrp_set.opCmp(rhe.irrp_set);}
}
//****************************************** class Context_pair *********************************
//This is for any pair of strings. It is used only as a context for an IGR to be added on the left and right respectively of the implication.
//
class Context_pair{
char [] s1 = [];//left
char [] s2 = [];//right
final this(const ref char [] s1, const ref char [] s2){
this.s1 = s1.dup;
this.s2 = s2.dup;}
override bool opEquals(const Object o) const {
auto rhs = cast(Context_pair)o;//not allowed in safe code
if( (s1 is null || s1 == []) && (rhs.s1 is null || rhs.s1 == []) ) return true;
// if( s1 == [] && s2 == []) return true;
if(s1 != rhs.s1) return false;
else if(s2 != rhs.s2) return false;
else return true;}
//This is needed to override default behaviour so that two empty context pairs are now equal.
final this(){}
final Context_pair dup(){ return new Context_pair(s1,s2);}
}
//***************************************** class IGR **************************************
//This class is for sets of IGR's with a common lhs IRRP and with a set of pairs of strings (contexts). Each instance of
//this class will correspond to an row of Table 3 or Table 4 with the addition of the LHS and RHS of the derived IRR
//for each context pair. see my paper (2021 version).
class IGR{
int ns;//minimum number of symbols on the "tape" needed to represent the IGR i.e. the length of the symbol strings.
Context_pair[] context = [];//this corresponds to a set of $T_1$ and $T_2$ pairs in the paper.
IRRP_set lhs;//This IRRP_set The meaning of this is $\text{cs1}\to\to \text{cs2}$ in latex.
RHE[] rhs = [];//context is the same for each IRRP_set i.e. for each value of alpha.
final this(ref Context_pair[] context, ref IRRP_set lhs, ref RHE[] rhs){
this.context = context.dup;
this.lhs = lhs.dup;
this.rhs = rhs.dup;}
final int opCmp(ref const IGR igr) const{
if(context[0].s1.length < igr.context[0].s1.length) return -1;
if(context[0].s1.length > igr.context[0].s1.length) return 1;
//compare IGR's by the rhs of the lhs. This won't work for incomplete IGR's i.e. those of length 2 created directly from the reversed TM.
//unless dummy values are put in, -- now done.
return lhs.opCmp(igr.lhs);}
//equality checking but ignoring the rhs's for now(they should be equal if the lhs's are).
override bool opEquals(const Object o) const {
auto rhs1 = cast(IGR)o;//not allowed in safe code
if(ns != rhs1.ns) return false;
if(context != rhs1.context) return false;
else if(lhs != rhs1.lhs) return false;
else if(rhs != rhs1.rhs) return false;
else return true;}
final this(){}
final IGR dup() { return new IGR(context,lhs,rhs);}
}
//*********************** 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 and IRR) and they agreed.
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 Context_pair_write(File of, const ref Context_pair sp){
if(sp !is null){
of.write("(");
of.write(sp.s1);
of.write(",");
of.write(sp.s2);
of.write(")");}
else of.write("null Context_pair");}
void IRR_write(File of,const ref IRR r){
if(r !is null){
of.write("IRR(");
of.write("[");
bool first=true;
foreach(ref x;r.cs0){if(!first)of.write(", ");
CS_write(of,x);first = false;}
of.write("]");
of.write(", ");
CS_write(of,r.cs1);
of.write(", ");
CS_write(of,r.cs2);
of.write(", '");
of.write(r.lsig);
of.write("', '");
of.write(r.sig);
of.write("', ");
of.write(r.n_derivation);
of.write(", ");
of.write(r.n_machine);
of.writeln(")");}
else of.write("null IRR");}
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 context_write(File of,const ref Context_pair[] array){
if(array !is null){
of.write("context[");
foreach(ref x;array){
of.write(" ");Context_pair_write(of,x);}
of.write(" ]");}
else of.write("null context");}
void array_IRR_write(File of,const ref IRR[] array){
if(array !is null){
bool first = true;
of.write(array.length);
foreach(ref x;array){
of.write(" ");if(!first)of.write("\n");IRR_write(of,x);first = false;}
of.writeln();of.writeln();}
else of.write("null IRR[]");}
void IRRP_set_write(File of, const ref IRRP_set irrp_set){
if(irrp_set !is null){
of.write("IRRP_set(");
of.write(irrp_set.alpha);
of.write(", ");
of.array_CS_write(irrp_set.origins);
of.write(", ");
of.CS_write(irrp_set.rhs);
of.write(")");
assert(irrp_set.rhs.l == irrp_set.origins[0].l);}
else of.write("null IRRP_set");}
void RHE_write(File of, const ref RHE rhe){
if(rhe !is null){
of.write(" RHE(");
of.IRRP_set_write(rhe.irrp_set);
of.write(", ");
of.write(rhe.n_Sub_step);
of.write(", ");
of.write(rhe.n_TM_step);
of.write(")");}
else of.write("null RHE");
}
void array_RHE_write(File of, const ref RHE[] array){
if(array !is null){
of.write("[ ");
bool first = true;
foreach(ref x; array){
if(!first)of.write("\n");
RHE_write(of,x);
first = false;}
of.write(" ]");}
else of.write("null RHE[]");}
void array_IRRP_set_write(File of,const ref IRRP_set[] array){
if(array !is null){
bool first = true;
of.write("[ ");
foreach(ref x;array){
if(!first)of.write("\n");IRRP_set_write(of,x);first = false;}
of.write(" ]");}
else of.write("null IRRP_set[]");}
void IGR_write(File of, const ref IGR igr){
if(igr !is null){
of.write("IGR(");
of.write(igr.ns);
of.write(", ");
of.context_write(igr.context);
of.write(", ");
of.IRRP_set_write(igr.lhs);
of.write(", ");
of.array_RHE_write(igr.rhs);
of.write(")");}
else of.write("null IGR");}
void array_IGR_write(File of,const ref IGR[] array){
if(array !is null){
bool first = true;
of.write(array.length);
foreach(ref x;array){
of.write(" ");if(!first)of.write("\n");IGR_write(of,x);first = false;}
of.writeln();}
else of.write("null IGR[]");}
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("\n y.n_symb = ",y.n_symb);
write("\n y.alpha = ",y.alpha);}}
//********************************** 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
@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,"",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: ");}
}
//***************************************** template function unique_sort_add ******************************************
//add element x to array in such a way as to maintain increasing order, and such that no elements are repeated
//in the array.
//Algorithm. Bisect the array segment repeatedly so as to locate between which pair of
//elements x is to be inserted to maintain inreasing order. When the pair of elements differ by 1 in index
//x can be inserted between them provided x is different from each of this pair.
void unique_sort_add(T)(ref T[] array, ref T x){
static if(is (T == IGR)){
write("\nunique_sort_add at start: x = ");IGR_write(stdout,x);
write("\nunique_sort_add at start: array = ");array_IGR_write(stdout,array);
}
int i;
int l = to!int(array.length);
if(l == 0){
// write("\nunique_sort_add: l = 0");
array ~= x;
// write("\nunique_sort_add: x added to array at end, l = 0");
}
else{
//deal with the end cases first
//if(i == 1)assert(false);
static if(is (T == IGR)){
write("\nunique_sort_add: x = ");IGR_write(stdout,x);
write("\nunique_sort_add: array[0] = ");IGR_write(stdout,array[0]);
write("\nl = ",l);
write("\nunique_sort_add: array[l - 1] = ");IGR_write(stdout,array[l - 1]);
//write("\n unique_sort_add: x.lhs.rhs = ");CS_write(stdout,x.lhs.rhs);
//write("\n unique_sort_add: array[0].lhs.rhs = ");CS_write(stdout,array[0].lhs.rhs);
//write("\n unique_sort_add: x = ");IGR_write(stdout,x);
//write("\n unique_sort_add: array[0] = ");IGR_write(stdout,array[0]);
//write("\n unique_sort_add: x < array[0] = ",x < array[0]);
}
if(x.opCmp(array[0]) < 0 ){ array = [x] ~ array;//neither this nor the next condition holds so control goes to the final while loop
write("\n x.opCmp(array[0]) = ",x.opCmp(array[0]));}//with i1=i2=0 which should not happen 2021-11-02
// this is because comparison of IGR's is by the RHS's of the LHS's only, and in this case they are the same!
//The two IGR's should not be being compared, they should be having their sets of origins combined, as happened later.
else if(x.opCmp(array[l - 1]) > 0){ array ~= x;
write("\n x.opCmp(array[l - 1]) = ",x.opCmp(array[l - 1]));}
else{//l != 0 and x is not to be inserted at an end.
//i1 and i2 are the indices which bracket the position where x is to be placed.
//and are at the lower and upper end of the range respectively.
int i3,i1 = 0;
int i2 = l - 1;
while(i2 - i1 > 1){
i3 = i1 + (i2 - i1)/2;
static if(is (T == IGR)){
//write("\n 633 unique_sort_add: i1 = ",i1," i2 = ",i2," i3 = ",i3);
//write("\n 633 unique_sort_add: x = ");IGR_write(stdout,x);
//write("\n 633 unique_sort_add: array[i3] = ");IGR_write(stdout,array[i3]);
//write("\n 633 unique_sort_add: x < array[i3] = ",x < array[i3]);
}
if(x.opCmp(array[i3]) < 0){//this never evaluated as true for IGR's!****************************8
i2 = i3;}
else{i1 = i3;}
write("\nunique_sort_add: i1 = ",i1," i2 = ",i2);
}
if(array[i1] != x && x != array[i2]){//should be included
static if(is (T == IGR)){
write("\nunique_sort_add: i1 = ",i1," i2 = ",i2);
write("\nunique_sort_add: array[i1] = ");IGR_write(stdout,array[i1]);
write("\nunique_sort_add: x = ");IGR_write(stdout,x);
write("\nunique_sort_add: array[i2] = ");IGR_write(stdout,array[i2]);
write("\narray[i1] == x ", array[i1] == x, " array[i2] == x ", array[i2] == x);
}
array = array[0 .. i1 + 1] ~ x ~ array[i2 .. $];}
else{
write("\nunique_sort_add: new element is not different");
}
}
}}
//******************************** function split_string ***************************
//pointer is at or one space beyond end of string when called and the length of the symbols strings is >= 2.
//Remove n_symbols from the string of a CS on the left or right opposite the pointer and put them in cont
void split_string(ref CS cs,const int n_symbols, out char[] cont){
write("\nsplit_string: cs = ");CS_write(stdout,cs);write(" n_symbols = ",n_symbols);
// if(cs.l < 2){write("\nError in split_string: l <= 1");write("\ncs = ");CS_write(stdout, cs);assert(cs.l >= 2);}
if(cs.t.length != cs.l){write("cs.l != cs.t.length");}
int i;
CS cs1 = cs.dup;
write("\nsplit_string: cs = ");CS_write(stdout,cs);writeln();
// writeln("cs.t.length = ",cs.t.length," n_symbols = ",n_symbols);
bool right = cs.p - cs.l == 0 || cs.p - cs.l == 1;//pointer is at right
writeln("\nright = ",right);
cs.l -= n_symbols;
if(right){
cs.p -= n_symbols;
i = to!int(cs.t.length) - n_symbols;
writeln("\ni = ",i," cs.t.length = ",cs.t.length);
assert(i >= 0);
rotate(cs.t,i);
writeln("\nn_symbols = ",n_symbols,"cs1.t.length = ",cs1.t.length);
cont = cs1.t[0 .. n_symbols];}//
else {
// write("\nsplit_string: cs1 = ");CS_write(stdout,cs1);
// write("\nsplit_string: n_symbols = ",n_symbols);
// for(i = 0; i <= n_symbols; ++i){
// write("\nsplit_string: i = ",i);write(cs1.t[$ - i .. $].dup);}
cont = cs1.t[$ - n_symbols .. $].dup;
// writeln("cont = ",cont);
}
cs.t.length -= n_symbols;
}
//******************************** function add_opposite_pointer *******************
//Add symbol string (not inplemented as a D string!) s at the opposite end of the string of symbols from the pointer. formerly add_at_x
//The routine assumes that the pointer is at one end of the known
//symbols on the tape (other cases will not be needed).
//This assumes that the length of the original symbol string in cs is > 1, and the length of s is >= 1.
@safe void add_opposite_pointer(ref CS cs,const char [] s){//symbols are added at right. Pointer is at left. ( i.e. cs.p=1)
int len = to!int(s.length);
cs.l += len;
cs.t ~= s;
if(cs.p > 1){//the symbol is added at the left, pointer is at right (cs.p=cs.l)
cs.p += len;
rotate(cs.t,len);}}
//********************************* function add_at_ptr_or_end ****************************
//Add symbol sy to cs (1) at or (2) adjacent to the pointer position at end of symbol string.
//The routine assumes that the pointer is at one end (case 2) or just off one end (case 1) of the known
//symbols on the tape. The added symbol never clobbers previous known symbols on the tape.
//This assumes that the length of the symbol string is > 1 for case (2). If l = 1 and case (1) then
//the other parameters cannot tell whether the symbol sy should be added at the left or right. In this case
//this is determined by the parameter direction (L or R) respectively. 'R' is the default value.
@safe void add_at_ptr_or_end(ref CS cs,const char sy, const char direction){
cs.t ~= sy;
if(cs.p <= 1 && cs.l > 1 || cs.p == 0 && cs.l == 1 || (cs.p == 1 && cs.l == 1 && direction == 'L')){
rotate(cs.t,1);//swaps added symbol from right to left end.
++(cs.p);}
++(cs.l);
}
//******************************** 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 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 st_init ************************************
//This initialises the Store object st.
void st_init(){
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.n_symbols = 0;}
//************************* function new_origins ************************************
//new origins is an algorithm 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. 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.
//The computation halts on a branch in case 1 and must necessarily halt on a branch in any of the other cases.
//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 before 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 respectively. This is used to distinguish
//case 1 and case 2 when the pointer ends up at the opposite end or same end respectively.
//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 this function.
//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 alphas 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 perhaps be declared as "append only".The "out ref" storage class combination is not possible.
//
@trusted void new_origins(const ref CS cs,ref NOOCO nooco_object){
//, ref CS[] ori, ref int[] n_symb, ref char[] alphas){
bool test;
write("\nnew_origins: cs = ");CS_write(stdout,cs);
st.cycle = canFind(st.L,cs);//not allowed in safe code
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
// writeln("st.cycle = ",st.cycle, " \nst.right_at_end = ",st.right_at_end, "\nst.left_at_end = ", st.left_at_end, "\nst.cond_1 = ",st.cond_1);
st.one_step_ori = [];
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
//writeln("k2 = ",k2," k1 = ",k1);
if(irrs[0][st.j].cs2.s == cs.s){//if new the 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)
//writeln("st.ind = ",st.ind);
st.inside = st.ind >= 0 && st.ind < cs.l;//pointer position after reverse TM step is within symbol string, otherwise it is at alpha
//writeln("st.inside = ",st.inside);
//writeln("irrs[0][st.j].cs2.p = ",irrs[0][st.j].cs2.p," st.ind = ",st.ind);
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,
//writeln("st.dircheck = ",st.dircheck);
//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);
//writeln("test = ",test);
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;
//writeln("test10");
if(st.inside){
ncs.l = cs.l;
ncs.t[st.ind] = irrs[0][st.j].cs1.t[0];
st.one_step_ori ~= ncs;//dup not needed: cs2 goes out of scope next, so it cannot provide a "back door" to one_step_ori
// write("\nncs = ");CS_write(stdout,ncs);
}
else{//reverse TM step takes pointer outside string, so terminating this branch of the search.
//Find st.n_symbols which is the number of symbols involved i.e. the length of the character string involved in finding
//the new origin in the current branch.
//writeln("test11");
if(st.right_at_start){//The TM is at the right hand end of the symbol string in the LHS
st.n_symbols = 1;//find n_symbols i.e. the number of symbols used in the computation
foreach(x; st.L) st.n_symbols = max(st.n_symbols, x.p);
st.n_symbols += 1;}//the extra symbol at the left shifts the symbol positions up by 1
else{//The TM is at the left in the LHS
st.n_symbols = cs.l;
foreach(x; st.L) st.n_symbols = min(st.n_symbols, x.p);
st.n_symbols = cs.l - st.n_symbols + 2;}
//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.
//writeln("test12");
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
// write("\nncs = ");CS_write(stdout,ncs);
// ori ~= ncs;
// n_symb ~= st.n_symbols;
// alphas ~= irrs[0][st.j].cs2.t[0];}//add in element to alphas
//write("\n784 st.n_symbols = ",st.n_symbols);
NOT noto;
noto.new_ori = ncs.dup;
noto.alpha = irrs[0][st.j].cs2.t[0];
noto.n_symb = st.n_symbols;
nooco_object.nota ~= noto;
}}}}}}
//This is the recursive bit
if(st.one_step_ori.length){
st.L ~= cs.dup;
//write("\nst.one_step_ori = ");array_CS_write(stdout,st.one_step_ori);
foreach(ref cs3;st.one_step_ori){
//Store_write(stdout,st);
new_origins(cs3, nooco_object);}}
if(st.L.length) --st.L.length;//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).
//write("\nori = ");array_CS_write(stdout,ori);
}
//It terminates the branch and is appropriate just prior to back-tracking from a branch that ends to follow another reverse TM step.
//************************* function apply_rules ************************************
//The function "apply_rules" applies the previously found IRR up to length one less than the current CS being
//processed to carry out substitution
//steps for the TM computation starting from the LHS named cs. n_steps is # substitution steps, nm = # TM steps.
//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 (i.e. substitution) 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.
//Each computation will end in state L,R,H or C, meaning the pointer is
//at the left,right, the computation halts or does not terminate, respectively.
//On output, cs now is the final result of the substitutions. The new rules get
//inserted into the array of arrays of IRR "irrs" in the main program.
@trusted void apply_rules(ref CS cs,out int n_steps,out int nm, out char d, out char lsig, out int n_symbols){
//d is "sig" for output cs: L,R,C, or H, lsig is sig for original cs (L or R).
// if(cs.p == 1)lsig = 'L'; else lsig = 'R';
CS[] cs_array;
cs_array ~= cs.dup;//dup is needed because cs_array is a record of the changing values of cs.
n_steps = 0;//# derivation steps
nm = 0;//# machine steps
n_symbols = 0;//number of symbols involved in the sequence of substitutions
bool match;
int j = cs.l;
d = '0';
IRR irr2;
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(ref irr3;irrs[k]){
if(subset(cs,irr3.cs1)){match=1;
irr2 = irr3;//irr3 next goes out of scope so dup not needed provided irr2 is not altered bolow.
break;}}
if(match==1)break;}
//match now indicates if a matching rule has been found. This should be true always
if(!match){
// write("cs = ");CS_write(stdout,cs);
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){//pointer at left in cs and irr2.
foreach(ref i;0 .. irr2.cs2.l){
cs.t[i] = irr2.cs2.t[i];}}
else if(cs.p > 1){//pointer at right in cs and irr2.
foreach(ref i;0 .. irr2.cs2.l){
cs.t[j - irr2.cs2.l+i] = irr2.cs2.t[i];}}
n_symbols = irr2.cs2.l;
cs.s = irr2.cs2.s;
cs.p += irr2.cs2.p - irr2.cs1.p;
cs.l = j;//cs is now the result of applying rule irr2 to previous cs
++n_steps;
if(n_steps>=2)n_symbols = cs.l;
nm += irr2.n_machine;
if(count(cs_array,cs) > 0 || irr2.sig == 'C')d = 'C';//not allowed in safe code
cs_array ~= cs.dup;//dup needed
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.
}}
/*
//******************************************** apply_F *************************************
//Starting with an IGR, add back its set of context pairs one at a time. For each, apply F to each of its RHS IRRP_sets i.e. for each
//allowed value of alpha in the original IGR. Each member of each of these (unless the set of new alpha values is empty)
//becomes the LHS of another IGR.
//sig and lsig are obtained by apply_rules but not used by apply_F. They could probably be removed later.
void apply_F(ref IGR igr, out IGR[] igr_set){//avoids copying all of igr but protects it from modification
//igr ought to be const but this creates problems creating a mutable copy of a const array of class (IRRP_set) objects
//could remove ref but this means wasting a copy!
int c, n, ns, n_derivation, n_machine;//ns is the # symbols involved in apply_rules
IGR[] igr_subset;
bool new_alpha, new_ns;
int[] n_symb_1, n_symb_2, d, d_ns;
CS cs0,cs2,cs3,cs4;
CS[] new_oris;
char lsig, sig, dir;
char[] alphas, d_alpha;
dir = ' ';
igr_set.length = 0;
IRRP_set[] t_irrp_set_array;//temporary array of IRRP_sets for an intermediate calculation step
n = igr.rhs[0].irr_2.cs1.l;//This is the length of the current IGR
++n;//n is now the length of the longest possible results of apply_F and is the length of all
//results after the first step of apply_F.
write("\napply_F output");
write("\nn = ",n);
CS[] cs0_list = new CS[0];
foreach (cp; igr.context){//add context strings to each element of the given IGR.rhs generating the LHS of a new IGR.
//This will be later split into a set of new IGR's with different lengths of context strings separated out.
write("\n igr.rhs.length = ", igr.rhs.length);
foreach(ref o_irrp_set;igr.rhs){//o is for old or original. This is a loop over old alpha, i.e. the set of values
//of alpha in the given IGR igr.
//The basic strategy is, for each context pair and old alpha, to generate the set of IRRP_sets representing the rhs of the new IGR's
//obtained by applying F to o_irrp_set. These are initially obtained without truncation to the minimum number of symbols involved in
//applying F. When these have been obtained, the results are shortened to the minimum number of symbols involved in F and arranged
//as a set of IGR's, one for each different number of symbols involved, with the corresponding context pairs giving those symbols
//that were removed. The IRRP_sets mentioned need to be completed (have all the origins included) before being submitted to the
//second step of this algorithm so that the number of times calculation of the new rhs is minimised. Therefore the loop
//over members of new_oris must be completed before sorting the results by the number of symbols involved.
//
//For this first step the results are classified as "new alpha" in which case a new IRRP_set is created and the values put in, or alpha
//is not new and just the new origin and number of symbols has to be added to an existing IRRP_set.
cs2 = o_irrp_set.rhs.dup;
CS_pair csp1 = o_irrp_set.irr_2;
if((o_irrp_set.origins[0].p == 1 && cs2.p > 0) || (o_irrp_set.origins[0].p > 1 && cs2.p == 0))continue;//check for the type of the IRRP. Only if it is LRL or RLR can F be applied.
add_opposite_pointer(cs2,cp.s2);//cs2 is now the RHS of a IRRP_set with context added
new_oris = [];//initialising 3 arrays in preparation for a set of runs of "new_origins"
n_symb_1 = [];
alphas = [];
cs0_list = [];
no1co[] no1co_array = new no1co[0];
foreach(ref ori;o_irrp_set.origins){
no1co no1co_object;
cs0 = ori.dup;
add_opposite_pointer(cs0,cp.s1);
cs0_list ~= cs0;
cs3 = cs0.dup;
// $cs3\to\to cs2$ is now the LHS of a new IGR to be found (before chopping out the unused
//For each shortening of this, see whether this has been found as the lhs of an IGR. If so don't continue
//this calculation, but add the corresponding context pair to this entry. To find this earlier result check the
//IGR[]s for each value of n including the current one, so as to generate for each n, the set of new IGR's (excluding the contexts) appearing
//in the analysis of the TM for that value of n and subsequent(larger) values of n.
//keep a count of the number of distinct IGR's (excluding contexts) for each value of n.
//For the IGR[] to be processed by apply_F in each cycle, include all results that are thus associated with smaller values of n.
st.L = [];//#1: Two initialisations needed for each run of "new_origins"
st.right_at_start = cs0.p == 1;//#2: i.e. pointer is at left in origin (it is at right in the LHS).
new_origins(cs0, no1co_object);
no1co_object.cs0 = cs0;
no1co_array ~= no1co;}
c = 0;//counter for the number of distinct new values of new alpha
d_alpha = [];//array of distinct values of the new alpha in the order they are found.
t_irrp_set_array = [];
foreach(q, ref new_ori; new_oris){//q is an automatic counter starting at 0
//Categorise the results by alpha only at first but record n_symb_1 for each origin as well as n_symb_2.
new_alpha = true;//this is a new value of new alpha
for(int j = 0; j < c; ++j){//there are currently c values of new alpha.
if(d_alpha[j] == alphas[q]){//d_alpha is the array of distinct values of (new) alpha
t_irrp_set_array[j].n_symb ~= max(n_symb_1[q],n_symb_2[j]);//puts in n_symb
t_irrp_set_array[j].origins ~= new_ori;//adds new origin to the IRR derived using the same value of alpha.
new_alpha = false; break;}}
if(new_alpha){
IRRP_set irrp_set = new IRRP_set;
d_alpha ~= alphas[q];
irrp_set.alpha = alphas[q];
irrp_set.origins ~= new_ori;
irrp_set.rhs = cs2.dup;
add_at_ptr_or_end(irrp_set.rhs, alphas[q], dir);
apply_rules(irrp_set.rhs,n_derivation,n_machine,sig,lsig,ns);//"sig" for output CS needed? No but keep sig and lsig
//and ignore these values, so that apply_rules works with IRR's as before
n_symb_2 ~= ns;
irrp_set.n_symb ~= max(n_symb_1[q],ns);//minimum number of symbols needed to represent the IGR is added.
irrp_set.n_derivation = n_derivation + 1;
irrp_set.n_machine = n_machine + o_irrp_set.n_machine;
++c;
t_irrp_set_array ~= irrp_set;}}
write("\n t_irrp_set_array = ");array_IRRP_set_write(stdout,t_irrp_set_array);//correct
//This has completed the intermediate calculation of the set of IRRP_sets
//obtained by F for the current cp and irrp_set (outer two loops). Each irrp_set has an associated value of (new) alpha.
//Results will be next classified by max(n_symb_1,n_symb_2) and reduced to this number of symbols with extra ones becoming the new contexts.
char[][] d_alpha_1 = [];//distinct values of alpha found so far in the order they were found, for each value of ns.
c = 0;//c is the number of distinct values of ns so far, for this value of alpha (or j)
d = [];//d[p] is the number of distinct values of alpha found so far for the p+1'th value of ns found so far
d_ns = [];//distinct values of ns
foreach(j,new_irrp_set;t_irrp_set_array){//this is a loop over (new)alpha
write("\nnew_irrp_set = ");IRRP_set_write(stdout,new_irrp_set);
//Fill in the new IRRP_sets, one for each possible value of n_symb.
//During the calculation of this double loop (for j and k) the following 2D array has to be filled in:
//For each value of ns, the distinct values of alpha found in the order they are found.
//Then using this array each new entry is first classified as new ns or not. If ns is new, the array for alpha values for
//that ns is initiated. If not, the array of alpha found for that ns is updated as either a new alpha or not.
//When a new value is found, (ns or alpha) its index number is recorded, so that when an old value is found, the result
//can be added to the appropriate IGR (in igr_subset) dependent on ns, and the appropriate IRRP_set (dependent on alpha).
foreach(k,ref ori; new_irrp_set.origins){
char[] cont_l, cont_r;
ns = new_irrp_set.n_symb[k];//number of symbols to shorten IGR to.
CS cs = ori.dup;
write("\ncs = ");CS_write(stdout,cs);
write("\n n = ",n," ns = ",ns);
new_ns = true;
for(int p = 0;p < c; ++p){
//write("\np = ",p, " ns = ",ns);
if(d_ns[p] == ns){
new_ns = false;
new_alpha = true;
for(int q = 0;q < d[p]; ++q){
if(d_alpha_1[p][q] == new_irrp_set.alpha){
new_alpha = false;
cs4 = cs.dup;
split_string(cs4, n - ns, cont_l);
//igr_subset[p].rhs[q].origins ~= cs4;//need to add cs4 to the array such that its sorted order is maintained.
unique_sort_add(igr_subset[p].rhs[q].origins,cs4);
break;}}
if(new_alpha){
IRRP_set irrps = IRRP_value(n, ns, cont_l, cont_r, new_irrp_set.alpha, cs, ns, new_irrp_set.rhs, csp1, new_irrp_set.n_derivation, new_irrp_set.n_machine);
igr_subset[p].rhs ~= irrps;
d_alpha_1[p] ~= new_irrp_set.alpha;
for( int i = 0;i < d_alpha_1.length; ++i){
write("\n");write(d_alpha_1[i]);}
++d[p];}
break;}}
if(new_ns){
IRRP_set irrps = IRRP_value(n, ns, cont_l, cont_r, new_irrp_set.alpha, cs, ns, new_irrp_set.rhs, csp1, new_irrp_set.n_derivation, new_irrp_set.n_machine);
write("\nirrps = ");IRRP_set_write(stdout,irrps);
++d.length;
++d[$ - 1];
++d_alpha_1.length;
d_ns ~= ns;
d_alpha_1[c] ~= new_irrp_set.alpha;
for( int i = 0;i < d_alpha_1.length; ++i){
write("\n");write(d_alpha_1[i]);}
igr_subset ~= new IGR;//a new IGR is started for each component (i.e. each value of the old alpha) of the RHS of the original IGR
IRRP_set irrp_set_old = new IRRP_set;
write("\ncs0_list = ");array_CS_write(stdout,cs0_list);
foreach(int i,ref cs11; cs0_list){//irrp_set_old should be cut down to the right size, and then unique_sort_added
//to the origins of the lhs of the new IGR
irrp_set_old.origins ~= cs11.dup;
write("\ni = ",i," n = ",n," ns = ",ns,"\nirrp_set_old.origins[i] = ");CS_write(stdout,irrp_set_old.origins[i]);
split_string(irrp_set_old.origins[i], n - ns, cont_l);}
irrp_set_old.rhs = cs2.dup;
split_string(irrp_set_old.rhs, n - ns, cont_r);
igr_subset[c].lhs = irrp_set_old;
igr_subset[c].rhs = [irrps];
igr_subset[c].context ~= new Context_pair(cont_l, cont_r);
++c;}}
//write("\n2: d_alpha_1 = ");
// for( int i = 0;i < d_alpha_1.length; ++i){
// write("\n");write(d_alpha_1[i]);}
}//ends loop over j
// write("\nigr_subset = ");
// array_IGR_write(stdout,igr_subset);
}//ends loop over origins of rhs of given IGR
igr_set ~= igr_subset;
}//ends loop over cp (context pairs)
}//ends function
//*********************************************** function IRRP_value ***************************************
//This function initialises an IRRP_set with the given values and removes the symbols that are not involved in its derivation
//thus this forms part of an IGR written without any redundant symbols.
IRRP_set IRRP_value(int n, ref char[] cont_l, ref char[] cont_r, const char alpha, CS origin, int n_symb, const ref CS rhs, const int n_derivation, const int n_machine){
IRRP_set irrps = new IRRP_set;
irrps.alpha = alpha;
irrps.origins ~= origin.dup;//only a single origin is obtained for the return IRRP_set. It is added to later if necessary.
irrps.n_symb ~= n_symb;
irrps.rhs = rhs.dup;
write("\nIRRP_value: calling split_string(irrps.origins[0],n-n_symb,cont_l)");
split_string(irrps.origins[0],n - n_symb, cont_l);
write("\nIRRP_value: calling split_string(irrps.rhs,n-n_symb,cont_r)");
split_string(irrps.rhs,n - n_symb, cont_r);
return irrps;
}
//symbols.
//Start creating igr_subset. This will have all the different cut-down versons of $cs1\to\to cs2$ as the LHS's of the set and the RHS's
//will be found after this.
foreach(l; 0 .. n - 1){//l is the number of symbols moved
cs9 = cs1.dup;
split_string(cs9,l,cont_l);
irrp.cs1 = cs9;
cs4 = cs2.dup;
split_string(cs4,l,cont_r);
irrp.cs2 = cs4;
if(igr_subset[l] is null)writeln("igr_subset[l] is null");//create the whole IGR then assign it to igr_subset[l]
IGR_write(stdout,igr_subset[l]);//segfault here
igr_subset[l].lhs = irrp;//segfault here
igr_subset[l].context.length = 0;
igr_subset[l].context ~= new String_pair(cont_l,cont_r);}// context pair added
// do calculation of F from a given IRRP with a single origin. It gives a single IGR as a result, which can be split into several
//as the result of removing different numbers of symbols that are not used, and these are then put into the context pairs.
//These are obtained at the same time for each value of alpha and constitute igr_subset when it is complete.
// Put these results including alpha directly into output IRRPsets
cs5 = cs1.dup;
writeln("test3.2");
st.right_at_start = cs1.p == 1;//i.e. pointer is at left in origin (it is at right in the LHS).
st_init();//initialise the Store st used by new_origins.
new_oris = [];
writeln("test3.3");
n_symb_1 = [];
alphas = [];
new_origins(cs1, new_oris, n_symb_1, alphas);
write("st.L = ");array_CS_write(stdout,st.L);writeln();
foreach(i, new_ori; new_oris){
//do the following only if alphas[i] has not occurred before
new_alpha = true;
for( int j = 0; j < i; ++j){
if(alphas[j] == alphas[i]){cs6 = cs6list[j]; new_alpha = false; break; }}
if(new_alpha){//record all cs6 in the array cs6list to avoid recalculation if alpha is the same.
cs6 = cs2.dup;
add_at_ptr_or_end(cs6,alphas[i], dir);
apply_rules(cs6,n_derivation,n_machine,sig,lsig,n_symb_2);
cs6list[i] = cs6;}
n_move = n + 1 - to!int(max(n_symb_1[i],n_symb_2));//maximum length of new IGR is igr.length + 1
i1 = to!int(alphas[i]) - 97;// i1 is the int form of st.alphas[i]
cs3 = new_ori;
split_string(cs3,n_move,cont_l);
writeln("test4");
cs8 = cs6.dup;
split_string(cs8,n_move,cont_r);
writeln("test5");
igr_subset[n_move].rhs[i1].rhs = cs8.dup;
igr_subset[n_move].rhs[i1].alpha = alphas[i];
igr_subset[n_move].rhs[i1].origins ~= new_ori.dup;
cs4 = cs1.dup;
add_at_ptr_or_end(cs4,alphas[i],dir);
igr_subset[n_move].rhs[i1].irr_2 = new CS_pair(cs4,cs6);}//LHS has alpha added to it. RHS must be i.rhs with cont_r combined i.e. original rhs cs6.
igr_set ~= igr_subset;
}}}}}
/*
}
}//sig applies to output cs6, lsig is 'L' or 'R' for LHS
//origins\to\to cs6 are the IRRP_set for the RHS of one of the derived IGR's
writeln("st.n_symb = ",st.n_symb," n_symb_2 = ",n_symb_2);
foreach(l, n_s; n_symb){//loop over different origins (equivalent to a loop over different values in n_symb_1)
writeln(" n_s = ",n_s);
writeln(igr.rhs[0].irr_2.cs1.l);
writeln(" igr.length = ",igr.length,"max(n_s,n_symb_2) = ",max(n_s,n_symb_2));
writeln("n_move = ",n_move);
writeln("l = ",l);
writeln("origins.length = ",origins.length);
cs3 = origins[l].dup;
//Take l symbols from the lhs's
//Take l symbols from the rhs
//add same cs8 to all elements of info
write("cs3 = ");CS_write(stdout,cs3);write(" n_move = ",n_move," i1 = ",i1);write(" cs6 = ");CS_write(stdout,cs6);write(" cs8 = ");CS_write(stdout,cs8);writeln(" cont_l = ",cont_l," cont_r = ",cont_r);
info_list ~= new Info(cs3, n_move, i1, cs6, cs8, cont_l, cont_r);//i1 is related to alpha
//take this # of symbols from the left of origin and cs2 and put them in "context"
// if(igr.lhs.rhs.p == igr.length){sig = 'L';}else {sig = 'R';}//type is LR or RL respectively. needed?
// ++freq_move[n_move];
}}}
//freq_move now has frequencies for all values of alpha combined
// igr_subset[l].lhs = irrp_set_l;//this will be needed when it works.
//at 790 it was set to zero!
//igr_subset[l].context.length = 0;//this also fails likewise!
}
//igr_subset[l].context ~= new String_pair(cont_l,cont_r);}//put in context pair
//# symbols moved in each IGR l is l
//second pass through set of all results for the same lhs IRRP
//put results in rhs IRRP_set
foreach(inf; info_list){//go through loop again this time knowing freq_move
writeln("apply_F.5");
n = inf.n_move;
//put in alpha, origins, rhs, irr_2
alpha = to!char(inf.i1 + 97);
// irrp_set.rhs = inf.cs8;
// irrp_set.alpha = alpha;
// irrp_set.origins ~= inf.ori;
// igr1.my_init;
// igr1.rhs[inf.i1] = irrp_set;
// igr_subset[n] = igr1.dup;
*/
//********************************* main program **********************************************
void main(string[] args){
writeln("This is TIEv3.0_draft copyright (C) 2018 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: ");
writeln("For example from the same directory as the program:");
writeln(" ./ ");
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[] array1;
int[] array2;
write("\n array1 is null = ",array1 is null);
write("\n array2 is null = ",array2 is null);
write("\n array1 is array2", array1 is array2);
write("\narray1 == array2 = ",array1 == array2);
array1 = [];
array1 ~= 0;
array1 = [];
write("\n array1 is null = ",array1 is null);
write("\n array2 is null = ",array2 is null);
write("\n array1 is array2", array1 is array2);
write("\narray1 == array2 = ",array1 == array2);
array2 = [];
write("\n array1 is null = ",array1 is null);
write("\n array2 is null = ",array2 is null);
write("\n array1 is array2", array1 is array2);
write("\narray1 == array2 = ",array1 == array2);
Context_pair cp1 = new Context_pair;
Context_pair cp2 = new Context_pair;
write("\ncp1 = ");Context_pair_write(stdout,cp1);
write("\ncp2 = ");Context_pair_write(stdout,cp2);
write("\ncp1 == cp2 ",cp1 == cp2);
cp1.s1.length = 0;
cp1.s1 ~= "a";
write("\ncp1 = ");Context_pair_write(stdout,cp1);
write("\ncp2 = ");Context_pair_write(stdout,cp2);
write("\ncp1 == cp2 ",cp1 == cp2);
cp1.s2.length = 0;
write("\ncp1 = ");Context_pair_write(stdout,cp1);
write("\ncp2 = ");Context_pair_write(stdout,cp2);
write("\ncp1 == cp2 ",cp1 == cp2);
//assert(false);
int n_symbols;
char alpha;
char dir;//direction for addition of new symbol alpha (will be 'L' or 'R').
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");
File of;//output file;
of.open(outputfilename.idup,"w");
infile.readf(" %s",&nst);infile.readf(" %s",&nsy);
int c=nsy*nst;
char [] question;
stdout.write("\nEnter the maximum length of derived computation rules: ");
int q,n;
input_int(n);
stdout.write("\nEnter 1 for showing all IRR, 2 for showing only IRR of type LL, or 3 for showing only IRR of type RR: ");
int opt;
input_int(opt);
irrs.length = n;
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 of length 1");
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;
r1.lsig=' ';
irrs[0] ~= r1;}//dup not needed because r1 goes out of scope next.
//its value can be udated and copied into irrs with .dup.
//array_IRR_write(of,irrs[0]);
//r1 is now out of scope so cannot be used to change irrs
stdout.write("\nThe numbers of irreducible regular (computation) rules");
of.write("\nThe numbers of irreducible regular (computation) rules");
stdout.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");
stdout.writeln("\nSee the output file "~outputfilename~" for the list of IRR obtained.");
int count;
//trusted void new_origins(ref Tuple!(bool inside, bool dircheck, int ext, CS[] L, CS[] ori, int[] n_symb, bool cycle,bool right_at_end, bool left_at_end, bool cond_1, int j, int ind, int n_symbols) st, const ref CS cs,
CS csi = new CS;
CS[][CS] rtm;//reversed Turing Machine steps represented as an associative array. This structure is filled in next.
//An effect of using the associative array is that each time it is constructed the
//key-value pairs are usually in a different order! The storage is using a hash table, whose elements are stored in an unordered way.
//This is a very sophisticated data structure designed for rapid retrieval of information not really needed here.
//Do this first for the TM steps going left
int index;
foreach(ref st;1 .. nst+1)foreach(ref sy;0 .. nsy){
CS cs1 = new CS;
cs1.s = st;
cs1.p = 0;
cs1.l = 1;
cs1.t.length = 1;
cs1.t[0] = to!char(sy+97);
rtm[cs1] = [];//declares that there are no CS(1)'s leading to this (state,symbol) combination yet found.
foreach(ref st1;1 .. nst+1)foreach(ref sy1;0 .. nsy){//search through TM table to find them all
index=(st1 - 1) * nsy + sy1;
//IRR_write(of,irrs[0][0]);
//array_IRR_write(stdout,irrs[0]);
if(irrs[0][index].cs2.p == 0 && irrs[0][index].cs2.s == st && irrs[0][index].cs2.t[0] == to!char(sy + 97)){//checks state and symbol and direction
CS cs2 = new CS;
cs2.s = irrs[0][index].cs1.s;
cs2.p = 1;
cs2.l = 1;
cs2.t.length = 1;
cs2.t[0] = irrs[0][index].cs1.t[0];
rtm[cs1] ~= cs2;//no dup needed because cs2 goes out of scope next.
// write("cs1 = ");CS_write(stdout,cs1);write("cs2 = ");CS_write(stdout,cs2);writeln("");
}}}
//then for the TM steps going right
foreach(ref st;1 .. nst+1)foreach(ref sy;0 .. nsy){
CS cs1 = new CS;
cs1.s = st;
cs1.p = 2;
cs1.l = 1;
cs1.t.length = 1;
cs1.t[0] = to!char(sy+97);
rtm[cs1] = [];
foreach(ref st1;1 .. nst+1)foreach(ref sy1;0 .. nsy){
index=(st1-1)*nsy+sy1;
if(irrs[0][index].cs2.p==2 && irrs[0][index].cs2.s == st && irrs[0][index].cs2.t[0] == to!char(sy+97)){
CS cs2 = new CS;
cs2.s = irrs[0][index].cs1.s;
cs2.p = 1;
cs2.l = 1;
cs2.t.length = 1;
cs2.t[0] = irrs[0][index].cs1.t[0];
rtm[cs1] ~= cs2;//no dup needed and it makes no difference!
// write("cs1 = ");CS_write(stdout,cs1);write("cs2 = ");CS_write(stdout,cs2);writeln("");
}}}
//generate the IRR(2)
//add symbols at the pointer s.t. forward TM step takes the pointer to opposite end of tape (l=2).
//alpha_n is the integer representation of the symbol called alpha in the papers: 0 for a ,1 for b etc. to give an irreducible rule
foreach(element;rtm.byKeyValue){
if(element.value == [])continue;
foreach(alpha_n;0 .. nsy){
dir = ' ';
index=(element.key.s - 1) * nsy + alpha_n;//use ordering of TM to compute index to find forward TM step
if(element.key.p==0 && irrs[0][index].cs2.p == 2) dir = 'L';//add symbol at left
if(element.key.p==2 && irrs[0][index].cs2.p == 0) dir = 'R';//add symbol at right
if(dir == 'L' || dir == 'R'){//this forward TM step does generate a member of IRR(2)
IRR r = new IRR;
foreach(cs0; element.value){
//construct the IRR triplet of length 2 and add it to the IRR
CS cs1 = cs0.dup;//cs0 is not modified by following statements
alpha = to!char(alpha_n + 97);
add_at_ptr_or_end(cs1,alpha, dir);//dir tells which side to add alpha
r.cs0 ~= cs1;}//ok because cs1 then goes out of scope.
//r.c1=key with alpha added on left or right
r.cs1 = element.key.dup;//this protects element.key from changes via cs
add_at_ptr_or_end(r.cs1,alpha,dir);
r.cs2 = r.cs1.dup;
apply_rules(r.cs2,r.n_derivation,r.n_machine,r.sig,r.lsig,n_symbols);
if(r.cs1.p == 1)r.lsig = 'L';else r.lsig = 'R';
irrs[1] ~= r;
write("r = ");IRR_write(stdout,r);
}}}
sort(irrs[1]);
array_IRR_write(stdout,irrs[1]);
//From the IRR(2) generate the IGR(2), the smallest IGR's. They are stored in igrs[0].
//These need to be consolidated i.e. origins combined if the rhs's are the same.
igrs.length = n - 1;
// igrs[0] = new IGR[0];
/* bool new_rhs,new_alpha;
char[][] d2_alpha;
write("\nd2_alpha.length = ",d2_alpha.length);
CS[] d_rhs = new CS[0];
foreach(ii,ref r; irrs[1]){
q = r.cs1.p > 1 ? 0 : r.cs1.l - 1;
alpha = r.cs1.t[q];//obtain the alpha value that was used to obtain the IRR r.
write("\nii = ",ii);
new_rhs = true;
write("\nr = ");IRR_write(stdout,r);
foreach(p2,rhs; d_rhs){//p2 is the index of the last distinct rhs found.
if(r.cs2 == rhs){
new_rhs = false;
new_alpha = true;
write("\np2 = ",p2);
foreach(p3, a; d2_alpha[p2]){
if(a == alpha){
new_alpha = false;
foreach(ref cs; r.cs0){
unique_sort_add(igrs[0][p2].rhs[p3].irrp_set.origins,cs);}//for results with the same rhs and alpha, origins are amalgamated
break;}}
if(new_alpha){
d2_alpha[p2] ~= alpha;
IRRP_set irrps_r = new IRRP_set;
irrps_r.alpha = alpha;
irrps_r.origins = r.cs0.dup;
irrps_r.rhs = r.cs2.dup;
RHE rhe = new RHE;
rhe.irrp_set = irrps_r;
rhe.n_TM_step = r.n_machine;
rhe.n_Sub_step = 1;
write("\nigrs[0][p2].rhs = ");array_RHE_write(stdout,igrs[0][p2].rhs);
write("\nrhe = ");RHE_write(stdout,rhe);
unique_sort_add(igrs[0][p2].rhs,rhe);}
break;}}
if(new_rhs){
d_rhs ~= r.cs2;
write("d2_alpha = ");foreach(s; 0 .. d2_alpha.length){
write("\ns = ",s," d2_alpha[s] = ");write(d2_alpha[s]);}
d2_alpha ~= [alpha];
write("\nd_rhs = ");array_CS_write(stdout,d_rhs);
IGR igr1 = new IGR;
IRRP_set irrps_l = new IRRP_set;
irrps_l.origins = [new CS(0,0,0,"*")];//these false values indicate that the IGR is direct from the RTM and permit sorting.
irrps_l.rhs = new CS(0,0,0,"*");//""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
RHE rhe = new RHE;
IRRP_set irrps_r = new IRRP_set;
irrps_r.alpha = alpha;
irrps_r.origins = r.cs0.dup;
irrps_r.rhs = r.cs2.dup;
rhe.irrp_set = irrps_r;
rhe.n_TM_step = r.n_machine;
rhe.n_Sub_step = 1;
Context_pair cp = new Context_pair;
cp.s1 = "".dup;
cp.s2 = "".dup;
igr1.ns = 2;
igr1.lhs = irrps_l;
igr1.context = [cp];
igr1.rhs = [rhe];
write("\nigr1 = ");IGR_write(stdout,igr1);
write("\nigrs[0] = ");array_IGR_write(stdout,igrs[0]);//this is null initially!
igrs[0] ~= igr1;
// unique_sort_add(igrs[0],igr1);//cannot use unique_sort_add here because LHS's of IGR's are with l = 2 here all the same but the IGR's are not.
write("\n igrs[0] = ");array_IGR_write(stdout,igrs[0]);}
// else{
// foreach(ref cs; r.cs0){
// write("\n igrs[0] = ");array_IGR_write(stdout,igrs[0]);
// write("\np2 = ",p2);
// write("\nigrs[0][p2] = ");IGR_write(stdout,igrs[0][p2]);
// write("\nigrs[0][p2].rhs[0].origins = ");array_CS_write(stdout,igrs[0][p2].rhs[0].irrp_set.origins);
// write("\nigrs[0] = ");array_IGR_write(stdout,igrs[0]);//this is null initially!:
// unique_sort_add(igrs[0][p2].rhs[0].irrp_set.origins,cs);
}
*/
//assert(false);
//generate the IRR(3) and beyond
writeln("length: ",2," # IRR = ",irrs[1].length);
of.writeln("length: ",2," # IRR = ",irrs[1].length);
// CS[] ori = new CS[0];//array of new origins on output.
CS[] new_oris = new CS[0];//combined array of origins.
// char[] alphas = new char[0];
char[] d_alpha;
// int [] n_symb_1;
int n_derivation,n_machine;
bool new_alpha;
//carry out analysis for the required number of iterations i.e.
foreach(ref i; 2 .. n){//given all irreducible rules (IRR) of length i, find all extensions of them to length i+1.
count = 0;//initialise count of the number of IRR found of length i.
foreach(ref r2; irrs[i - 1]){
if(!((r2.lsig == 'L' && r2.sig == 'R') || (r2.lsig == 'R' && r2.sig == 'L')))continue;//ignore IRR that are not of type LR or RL
IRR[] new_irrs = new IRR[0];//empty array of IRR's to be filled in
NOOCO[] nooco_array;
foreach(ref cs; r2.cs0){
NOOCO nooco_object;
// st.L = [cs];
st.L = [];
st.right_at_start = cs.p == 1;//i.e. pointer is at left in origin (it is at right in the LHS).
st_init();//initialise the Store st used by new_origins.
//Store_write(stdout,st);
write("\nabout to call new_origins: input CS is ");CS_write(stdout,cs);
new_origins(cs, nooco_object);
nooco_object.cs0 = cs.dup;
nooco_array ~= nooco_object;}
write("\nnooco_array = ");
foreach(x; nooco_array)NOOCO_write(stdout,x);
write("\nend of nooco_array\n");
//n_symb_1 is not used here. Only needed for IGR's
c = 0;//counter for the number of new values of alpha
d_alpha = [];//array of distinct values of alpha in the order they are found.
// foreach(q, ref new_ori; new_oris){//reformulate this in terms of no1co! *************************
foreach(x; nooco_array){
foreach(noto; x.nota){
new_alpha = true;
for(int j = 0; j < c; ++j){
if(d_alpha[j] == noto.alpha){
new_irrs[j].cs0 ~= noto.new_ori;//adds new origin to the IRR derived using the same value of alpha.
new_alpha = false; break;}}
if(new_alpha){
IRR new_irr = new IRR;
d_alpha ~= noto.alpha;
new_irr.cs0 ~= noto.new_ori.dup;
new_irr.cs1 = r2.cs1.dup;
add_opposite_pointer(new_irr.cs1,[noto.alpha]);
new_irr.cs2 = r2.cs2.dup;
add_at_ptr_or_end(new_irr.cs2, noto.alpha, dir);
apply_rules(new_irr.cs2,n_derivation,n_machine,new_irr.sig,new_irr.lsig,n_symbols);
if(new_irr.cs1.p == 1)new_irr.lsig = 'L';else new_irr.lsig = 'R';
new_irr.n_derivation = n_derivation + 1;
new_irr.n_machine = n_machine + r2.n_machine;
++ count;
++ c;
new_irrs ~= new_irr;
write("\nnew_irr = ");IRR_write(stdout,new_irr);
}}}
irrs[i] ~= new_irrs;
write("\n irrs[i].length = ",irrs[i].length);
write("\nnew_irrs = ");array_IRR_write(stdout, new_irrs);
}
// foreach(ref a; oris.sort.uniq) r.cs0 ~= a;//r.cs0 is the combined set oris, sorted and with duplicates removed.
writeln("length: ",i + 1," # IRR = ",irrs[i].length);
of.writeln("length: ",i + 1," # IRR = ",irrs[i].length);}
//Do iteration of this to get any new patterns on the left and their corresponding set of sets after F, to convergence.
//Then do iteration of the sets of LHS states to convergence by adding new LHS states as required.
//********************** End of the old program *********************
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(ref i; 0 .. n){
if(irrs[i].length != 0){
if(i)of.writeln("IRR of length ",i + 1);
else of.writeln("The Turing Machine table expressed as IRR of length 1");
sort!()(irrs[i]);
foreach(ref it;irrs[i]){
if((opt == 1)||(opt == 2 && it.cs1.p == 1 && it.cs2.p == 0)||(opt == 3 && it.cs1.p == it.cs1.l && it.cs2.p == it.cs2.l + 1))IRR_write(of,it);}}}
// int[] j2 = [to!int(igrs[0].length)];//The second index of igrs which is the index of the IGR's obtained as a result of F.
//
//It depends on the length of the IGR. When a new IGR of length ns is initiated the value of j2[ns - 2] is incremented.
//This is done for all values of i concurrently.
// IGR igr1 = new IGR;
int [] d_ns;
char[][] d2_alpha;
int n_steps, nm;
char[] cont_l,cont_r;
CS cs0,cs1,cs2,cs3,cs4,cs5;
char lsig,sig;
// int[] d,d_ns,n_symb_2;
bool new_ns, new_igr;
char direction, d;
IGR[] igr_array;
//Generate the IGR(2) from scratch
foreach(r; irrs[0]){//for each single TM step
write("\nr = ");IRR_write(stdout,r);
IGR igr = new IGR;
bool new_r = true;
foreach(sy; 0 .. nsy){
alpha = to!char(sy + 97);
write("\nalpha = ",alpha);
if(r.cs2.p > 1) direction = 'R';
if(r.cs2.p == 0) direction = 'L';
cs4 = r.cs2.dup;
cs5 = r.cs1.dup;
foreach(r2; irrs[0]){
if(r2.cs1.s == cs4.s && r2.cs1.t[0] == alpha){//matching row of TM table has been found
write("\nr2 = ");IRR_write(stdout,r2);
write("\ncs4 = ");CS_write(stdout,cs4);
if((cs4.p == 0 && r2.cs2.p == 2) || (cs4.p == 2 && r2.cs2.p == 0)){//new igr or new IRRP_set for the igr.rhs is needed.
add_at_ptr_or_end(cs4, alpha, direction);
add_at_ptr_or_end(cs5, alpha, direction);
apply_rules(cs4, n_steps, nm, d, lsig, n_symbols);
write("\ncs4 = ");CS_write(stdout,cs4);
if(new_r){//this is the first value of alpha for this r
IRRP_set irrps_l = new IRRP_set;
irrps_l.alpha = '*';
irrps_l.origins = [r.cs1];
irrps_l.rhs = r.cs2;
Context_pair cp = new Context_pair;
cp.s1 = "".dup;
cp.s2 = "".dup;
igr.ns = 2;
igr.context = [cp];
igr.lhs = irrps_l;}
IRRP_set irrps_r = new IRRP_set;
irrps_r.alpha = alpha;
irrps_r.origins = [cs5];
irrps_r.rhs = cs4;
RHE rhe = new RHE;
rhe.irrp_set = irrps_r;
rhe.n_TM_step = n_steps;
rhe.n_Sub_step = 1;
unique_sort_add(igr.rhs, rhe);
new_r = false;
write("\nigr = ");IGR_write(stdout,igr);
// igrs[0] ~= igr;
break;}}}}
unique_sort_add(igrs[0],igr);}
/* if(cs4.p == 0){// && TM goes right
foreach(r2; irrs[0]){
if(r2.cs1.s == cs4.s && r2.cs1.t[0] == cs4.t[0]){//matching row of TM table has been found
if(r2.cs2.p == 2){
new_igr = true;
apply_rules(cs4, n_steps, nm, d, lsig, n_symbols);
break;}}}}
if(cs4.p == 2){//&& TM goes left
foreach(r2; irrs[0]){
if(r2.cs1.s == cs4.s && r2.cs1.t[0] == cs4.t[0]){//matching row of TM table has been found
if(r2.cs2.p == 0){
new_igr = true;
apply_rules(cs4, n_steps, nm, d, lsig, n_symbols);
break;}}}}
if(new_igr){
IRRP_set irrps_l = new IRRP_set;
irrps_l.alpha = '*';
irrps_l.origins = [r.cs1];
irrps_l.rhs = r.cs2;
IRRP_set irrps_r = new IRRP_set;
irrps_r.alpha = alpha;
irrps_r.origins = [cs5];
irrps_r.rhs = cs4;
RHE rhe = new RHE;
rhe.irrp_set = irrps_r;
rhe.n_TM_step = n_steps;
rhe.n_Sub_step = 1;
IGR igr = new IGR;
igr.ns = 2;
igr.lhs = irrps_l;
igr.rhs = [rhe];
igrs[0] ~= igr;}}}
*/
write("\n1389: IGR's of length: 2");
write("\n");
foreach(y; igrs[0]){writeln(); IGR_write(stdout,y);}
// char[][] d2_alpha;//distinct values of alpha for each ns in the order ns are found (first index)
foreach(i; 1 .. n - 1){//The IGR's generating the IRR(2) have already been found, these are in igrs[0].
write("\n loop counter i = ",i);
//This is the main loop that when complete generates igrs, the 2D array of IGR's that generate the IRR's up to
//length n. For cycle i these IGR's are updated such that the IGR's included generate the IRR's
//of length i + 2. The sub-array igrs[i] contains only IGR's of reduced length i + 2 (i.e. excluding the length of the context).
//The first cycle (i = 1) will generate the IGR's for obtaining the IRR(3) and these will be put in igrs[0] and igrs[1].
//The additional ones put in igrs[0] will be those of length 2 with context pair(s) of length 1 having total length 3. At the end
//of the loop (i = n - 2) igrs[0] ... igrs[n - 2] will have been found generating the IRR up to length n.
//Cycle i starts with the set of members of igrs[0] with contexts having length i - 1 having total length i + 1
//and in general members of igrs[j] with contexts of length i - j - 1 have total length i + 1 giving IRR(i + 1), for
//j (now j1) such that 0 <= j <= i - 1.
//All these after F give members of IRR(i + 2) that are likewise partitioned into
//igrs[k] with context of length i - k for 0 <= k <= i.
//Each IGR under F can give a set of IGR's of different lengths and lengths of context string pairs. For each
//old alpha, a set results (IRRP_sets) in the temporary array is produced, one for each value of new alpha. As a result of the
//removal or extra symbols, some are reduced in length. One new IGR is started for each value of ns the minimum number
//of symbols needed to represent it. Therefore an array of counters is needed, one for each of the sub-arrays. It is called
//j2 and j2[k] is the counter for igrs[k] with IGR's of minimal length k + 2. j2[0] is initialised to the
//could just use igrs[k].length?
for(int j1 = 0;j1 < i; ++j1){
write("\n loop counter j1 = ",j1);
foreach(lc3,igr;igrs[j1]){//loop counter
write("\n loop counter lc3 = ",lc3);
foreach(lc4,cp; igr.context){
write("\n loop counter lc4 = ",lc4);
if(cp.s1.length != i - j1 - 1)continue;//if the total length of the IGR is not i + 1, skip this.
foreach(lc5,ref o_rhe;igr.rhs){//o is for old or original. This is a loop over old alpha.
write("\n loop counter lc5 = ",lc5);
//assert(false);
write("\n o_rhe = ");RHE_write(stdout,o_rhe);
//assert(false);
//write("\n o_irrp_set = ");IRRP_set_write(stdout,o_irrp_set);
cs2 = o_rhe.irrp_set.rhs.dup;
add_opposite_pointer(cs2,cp.s2);//cs2 is now the RHS of a IRRP_set with context added
foreach(lc6,ref ori; o_rhe.irrp_set.origins){
write("\n loop counter lc6 = ",lc6);
if((ori.p == 1 && cs2.p > 0) || (ori.p > 1 && cs2.p == 0))continue;//check for the type of the IRRP. Only if it is LRL or RLR can F be applied.
// IGR[] igr_array = new IGR[0];//array of IGR's. igr_array[j] is the IGR obtained having length j + 2.
d2_alpha.length = 0;
cs0 = ori.dup;
add_opposite_pointer(cs0,cp.s1);
cs3 = cs0.dup;
write("\ncs3 = ");CS_write(stdout,cs3);
// $cs3\to\to cs2$ is now the LHS of a new IGR to be found (before chopping out the context strings.
st.L = [];//#1: Two initialisations needed for each run of "new_origins"
st.right_at_start = cs0.p == 1;//#2: i.e. pointer is at left in origin (it is at right in the LHS).
st_init();//initialise the Store st used by new_origins. needed?
NOOCO nooco_object;
new_origins(cs0, nooco_object);
nooco_object.cs0 = cs0.dup;
NOOCO_write(stdout,nooco_object);
d_ns = [];
igr_array = [];
igr_array.length = i + 1;
write("\n1 cs2 = ");CS_write(stdout, cs2);
foreach(count2, ref y; nooco_object.nota){//new_origins_triplet_array
write("\n loop counter count2 = ",count2);
write("\n2 cs2 = ");CS_write(stdout, cs2);
write("\ny.alpha = ",y.alpha);
write("\ny.new_ori = ");CS_write(stdout,y.new_ori);
cs4 = cs2.dup;
write("\n cs4 = ");CS_write(stdout, cs4);
add_at_ptr_or_end(cs4, y.alpha, dir);
write("\n cs4 = ");CS_write(stdout, cs4);
int ns;
apply_rules(cs4,n_derivation,n_machine,sig,lsig,ns);//"sig" for output CS needed? No but keep sig and lsig
write("\n n_derivation = ",n_derivation," n_machine = ",n_machine," sig = ",sig," lsig = ",lsig," ns = ",ns);
write("\n3 cs2 = ");CS_write(stdout, cs2);
ns = max(y.n_symb,ns);
write("\nns = ",ns);
new_ns = true;
write("\nd_ns.length = ",d_ns.length);
//if(d_ns.length !is null)write("\nd_ns.length !is null");else write("\nd_ns.length is null");
for(int k = 0; k < d_ns.length; ++k){
write("\n4 cs2 = ");CS_write(stdout, cs2);
if(ns == d_ns[k]){
new_ns = false;
new_alpha = true;//this is assumed first to be a new value of (new)alpha.
for(int j = 0; j < d2_alpha[k].length; ++j){
if(d2_alpha[k][j] == y.alpha){
new_alpha = false;
write("\nk = ",k," j = ",j);
split_string(y.new_ori, i + 2 - ns, cont_l);
unique_sort_add(igr_array[ns - 2].rhs[j].irrp_set.origins, y.new_ori);//adds new origin to the IRR derived using the same value of alpha.
break;}}
if(new_alpha){
write("\n5 cs2 = ");CS_write(stdout, cs2);
RHE rhe_r = new RHE;
IRRP_set irrp_set_r = new IRRP_set;
d2_alpha[k] ~= y.alpha;
irrp_set_r.alpha = y.alpha;
split_string(y.new_ori, i + 2 - ns, cont_l);
irrp_set_r.origins = [y.new_ori];
irrp_set_r.rhs = cs4;
split_string(irrp_set_r.rhs, i + 2 - ns, cont_r);
rhe_r.n_TM_step = n_machine;
rhe_r.n_Sub_step = n_derivation;
rhe_r.irrp_set = irrp_set_r;
write("\n o_rhe.n_TM_step = ",o_rhe.n_TM_step);
write("\n new_alpha: irrp_set_r = ");IRRP_set_write(stdout,irrp_set_r);
igr_array[ns - 2].rhs ~= rhe_r;}
break;}}
if(new_ns){
write("\n6 cs2 = ");CS_write(stdout, cs2);
write("\nns = ",ns);
d_ns ~= ns;
write("\nd_ns = ");write(d_ns);
RHE rhe_r = new RHE;
IRRP_set irrp_set_r = new IRRP_set;
IRRP_set irrp_set_l = new IRRP_set;
d2_alpha ~= [y.alpha];//array of distinct values of the new alpha in the order they are found.
write("\nd2_alpha = ");
foreach(ii;0 .. d2_alpha.length){write(d2_alpha[ii]);write("\n");}
irrp_set_r.alpha = y.alpha;
irrp_set_r.origins = [y.new_ori];
write("\n irrp_set_r.origins[0] = ");CS_write(stdout,irrp_set_r.origins[0]);
write("\n i = ",i, " ns = ",ns);
write("\ni + 2 - ns = ",i + 2 - ns);
split_string(irrp_set_r.origins[0], i + 2 - ns, cont_l);
write("\n irrp_set_r.origins[0] = ");CS_write(stdout,irrp_set_r.origins[0]);
irrp_set_r.rhs = cs4;
write("\n irrp_set_r.rhs = ");CS_write(stdout,irrp_set_r.rhs);
split_string(irrp_set_r.rhs, i + 2 - ns, cont_r);
write("\n irrp_set_r.rhs = ");CS_write(stdout,irrp_set_r.rhs);
rhe_r.irrp_set = irrp_set_r;
write("\n7 cs2 = ");CS_write(stdout, cs2);
rhe_r.n_TM_step = n_machine;
write("\nn_machine = ",n_machine, " o_rhe.n_TM_step = ",o_rhe.n_TM_step);
rhe_r.n_Sub_step = n_derivation;
write("\n cs3 = ");CS_write(stdout,cs3);
write("\n7.3 cs2 = ");CS_write(stdout, cs2);
cs1 = cs3.dup;
split_string(cs1, i + 2 - ns, cont_l);//should happen once only for each new IGR
irrp_set_l.alpha = '*';//This removes old alpha from the lhs of the IGR's and results in sorting them by
//their left IRRP_sets i.e. by the rhs of the left IRRP_set, then by its origin.
write("\n old alpha = ",o_rhe.irrp_set.alpha);
write("\n7.5 cs2 = ");CS_write(stdout, cs2);
irrp_set_l.origins = [cs1];
write("\n irrp_set_l.origins[0] = ");CS_write(stdout,irrp_set_l.origins[0]);
irrp_set_l.rhs = cs2.dup;
split_string(irrp_set_l.rhs, i + 2 - ns, cont_r);
write("\n irrp_set_l.rhs = ");CS_write(stdout,irrp_set_l.rhs);
IGR igr1 = new IGR;
igr1.ns = ns;
igr1.rhs = [rhe_r];
igr1.lhs = irrp_set_l;
write("\n7.8 cs2 = ");CS_write(stdout, cs2);
igr1.context ~= new Context_pair(cont_l,cont_r);
write("\nigr1 = ");IGR_write(stdout,igr1);
igr_array[ns - 2] = igr1;
write("\n8 cs2 = ");CS_write(stdout, cs2);
}}
//sort each element of igr_array individually into z by IRRP_sets in their rhs's using alpha.
//then add z into main arrays igrs maintaining sort order.
write("\n sort elements of igr_array within and between");
foreach(lc10,x; igr_array){
write("\n loop counter lc10 = ",lc10);
if(x !is null){
write("\n sort within x");
IGR z = new IGR;
z.ns = x.ns;
write("\n x = ");IGR_write(stdout, x);//x is null
write("\n z = ");IGR_write(stdout, z);
z.lhs = x.lhs;//removing this removed segfault
z.context = x.context;
foreach(y; x.rhs){//this operation needs to be combined with a merging of sets of origins 2021-11-04 or at
//least grouping or sorting them so that they are in a group of similar IGR's.
write("\ny = ");RHE_write(stdout,y);
unique_sort_add(z.rhs, y);}
write("\n sorted igr z = ");IGR_write(stdout,z);
write("\nadd sorted igr to igrs");
unique_sort_add(igrs[z.ns - 2], z);}}
}
}//ends loop over o_irrp_set or equivalently old alpha
}//ends loop over cp (context pairs) of input IGR
}//ends loop over igr of a set of IGR's.
}//ends loop over j1
}//ends loop over i
foreach(i,x; igrs){
write("\n IGR's of length: ",i + 2);
write("\n");
foreach(y;x){writeln(); IGR_write(stdout,y);}}
}//ends program
/* for(int j1 = 0;j1 < i; ++j1){
write("\nj1 = ",j1);
foreach(igr;igrs[j1]){
foreach(cp; igr.context){
if(cp.s1.length != i - j1 - 1)continue;//if the total length of the IGR is not i + 1, skip this.
foreach(ref o_irrp_set;igr.rhs){//o is for old or original. This is a loop over old alpha i.e. the set of values
//write("\no_irrp_set = ");IRRP_set_write(stdout,o_irrp_set);
//of alpha in the original IGR igr.
//Find out whether this IRRP_set has been found as the LHS of an IGR including the current set of results for this value of n.
// bool found = false;
/* foreach(k; 0 .. i + 1){
if(igrs.length > k){foreach(igr2;igrs[k]){
if(igr2.lhs == o_irrp_set){igr.context ~= igr2.context; found = true;}}}}//when found there can be only one previous case
*/
// if(found == false){
//of alpha in the given IGR igr.
//The basic strategy is, for each context pair and old alpha, to generate the set of IRRP_sets representing the rhs of the new IGR's
//obtained by applying F to o_irrp_set. These are initially obtained without truncation to the minimum number of symbols involved in
//applying F. When these have been obtained, the results are shortened to the minimum number of symbols involved in F and arranged
//as a set of IGR's, one for each different number of symbols involved, with the corresponding context pairs giving those symbols
//that were removed. The IRRP_sets mentioned need to be completed (have all the origins included) before being submitted to the
//second step of this algorithm so that the number of times calculation of the new rhs is minimised. Therefore the loop
//over members of new_oris must be completed before sorting the results by the number of symbols involved.
//
//For this first step the results are classified as "new alpha" in which case a new IRRP_set is created and the values put in, or alpha
//is not new and just the new origin and number of symbols has to be added to an existing IRRP_set.
//write("\n1 o_irrp_set = ");IRRP_set_write(stdout,o_irrp_set);
/* IGR igr1;
CS cs0,cs3,cs4;
IRRP_set[] t_irrp_set_array;
char lsig,sig;
int[] d,d_ns,n_symb_2;
int ns;
bool new_ns;
CS cs2 = o_irrp_set.rhs.dup;
// CS[] cs0_list;
// CS_pair csp1 = o_irrp_set.irr_2;
add_opposite_pointer(cs2,cp.s2);//cs2 is now the RHS of a IRRP_set with context added
new_oris = [];//initialising 3 arrays in preparation for a set of runs of "new_origins"
n_symb_1 = [];
alphas = [];
// cs0_list = [];
//write("\ni = ",i," j1 = ",j1," cp.s1.length = ",cp.s1.length);
no1co_array = [];
foreach(ref ori;o_irrp_set.origins){
if((ori.p == 1 && cs2.p > 0) || (ori.p > 1 && cs2.p == 0))continue;//check for the type of the IRRP. Only if it is LRL or RLR can F be applied.
cs0 = ori.dup;
add_opposite_pointer(cs0,cp.s1);
// cs0_list ~= cs0.dup;
cs3 = cs0.dup;
no1co no1co_object;
// $cs3\to\to cs2$ is now the LHS of a new IGR to be found (before chopping out the unused
//For each shortening of this, see whether this has been found as the lhs of an IGR. If so don't continue
//IGR[]s for each value of n including the current one, so as to generate for each n, the set of new IGR's (excluding the contexts) appearing
//in the analysis of the TM for that value of n and subsequent(larger) values of n.
//keep a count of the number of distinct IGR's (excluding contexts) for each value of n.
//For the IGR[] to be processed by apply_F in each cycle, include all results that are thus associated with smaller values of n.
st.L = [];//#1: Two initialisations needed for each run of "new_origins"
st.right_at_start = cs0.p == 1;//#2: i.e. pointer is at left in origin (it is at right in the LHS).
st_init();//initialise the Store st used by new_origins.
//Store_write(stdout,st);
write("\nabout to call new_origins: input CS is ");CS_write(stdout,cs0);
new_origins(cs0, no1co_object);
no1co_object.cs0 = cs0.dup;
no1co_array ~= no1co_object;}
write("\ncs2 = ");CS_write(stdout,cs2);
//write("\ncs0 = ");CS_write(stdout,cs0);
//write("\nnew_oris = ");array_CS_write(stdout,new_oris);
//write("\nn_symb_1 = ");write(n_symb_1);
//write("\nalphas = ");write(alphas);
c = 0;//counter for the number of distinct new values of new alpha
d_alpha = [];//array of distinct values of the new alpha in the order they are found.
t_irrp_set_array = [];
foreach(ref x; no1co_array){
foreach(ref y; x.nota){
// foreach(q, ref new_ori; new_oris){//q is an automatic counter starting at 0
//write("\nnew_ori = ");CS_write(stdout,new_ori);
//Categorise the results by alpha only at first but record n_symb_1 for each origin as well as n_symb_2.
new_alpha = true;//this is a new value of new alpha
for(int j = 0; j < c; ++j){//there are currently c values of new alpha.
if(d_alpha[j] == y.alpha){//d_alpha is the array of distinct values of (new) alpha
t_irrp_set_array[j].n_symb ~= max(y.n_symb,n_symb_2[j]);//puts in n_symb
//also copy this value into no1co_array for getting the lhs of the new IGR's. This will replace n_symb_1 already there.
t_irrp_set_array[j].origins ~= y.new_ori;//adds new origin to the IRR derived using the same value of alpha.
new_alpha = false; break;}}
if(new_alpha){
IRRP_set irrp_set = new IRRP_set;
irrp_set.alpha = y.alpha;
irrp_set.origins ~= y.new_ori;
irrp_set.rhs = cs2.dup;
add_at_ptr_or_end(irrp_set.rhs, y.alpha, dir);
apply_rules(irrp_set.rhs,n_derivation,n_machine,sig,lsig,ns);//"sig" for output CS needed? No but keep sig and lsig
// write("\n0 i = ",i," j1 = ",j1," n = ",n," ns = ",ns);
//and ignore these values, so that apply_rules works with IRR's as before
n_symb_2 ~= ns;
y.n_symb = max(y.n_symb,ns);//update no1co with the correct n_symb taking forward computation into account
write("\ny.n_symb = ",y.n_symb);//can be 3
irrp_set.n_symb ~= y.n_symb;//minimum number of symbols needed to represent the IGR is added.
irrp_set.n_derivation = n_derivation + 1;
irrp_set.n_machine = n_machine + o_irrp_set.n_machine;
++c;
d_alpha ~= y.alpha;
t_irrp_set_array ~= irrp_set;}}}
write("\nno1co_array = ");
no1co_array_write(stdout,no1co_array);//does never have y.n_symb = 3 it seems
write("\nend of no1co_array\n");
write("\nt_irrp_set_array = ");array_IRRP_set_write(stdout,t_irrp_set_array);//correct
//This has completed the intermediate calculation of the set of IRRP_sets
//obtained by F for the current cp and irrp_set (outer two loops). Each irrp_set has an associated value of (new) alpha.
//Results will be next classified by max(n_symb_1,n_symb_2) and reduced to this number of symbols with extra ones becoming the new contexts.
char[][] d_alpha_1 = [];//distinct values of alpha found so far in the order they were found, for each value of ns.
// c = 0;//c is reused as the number of distinct values of ns found so far, for this value of alpha (or j)
d = [];//d[p] is the number of distinct values of alpha found so far for the p+1'th value of ns found so far
d_ns = [];//distinct values of ns
foreach(j,new_irrp_set;t_irrp_set_array){//loop is over new alpha
//write("\nnew_irrp_set = ");IRRP_set_write(stdout,new_irrp_set);
//i + 2 is the total length of of the derived IGR's in cycle i. This takes the place of n in IRRP_value and split_string.
//this is a loop over (new)alpha
//Fill in the new IRRP_sets, one for each possible value of n_symb.
//During the calculation of this double loop (for j and k) the following 2D array has to be filled in:
//For each value of ns, the distinct values of alpha found in the order they are found.
//Then using this array each new entry is first classified as new ns or not. If ns is new, the array for alpha values for
//that ns is initiated. If not, the array of alpha found for that ns is updated as either a new alpha or not.
//When a new value is found, (ns or alpha) its index number is recorded, so that when an old value is found, the result
//can be added to the appropriate IGR (in igr_subset) dependent on ns, and the appropriate IRRP_set (dependent on alpha).
foreach(k,ref ori; new_irrp_set.origins){
char[] cont_l, cont_r;
ns = new_irrp_set.n_symb[k];//number of symbols to shorten IGR to.
// write("\n n = ",n," ns = ",ns);
CS cs = ori.dup;
//write("\ncs = ");CS_write(stdout,cs);
//write("\n n = ",n," ns = ",ns);
new_ns = true;
for(int p = 0;p < d_ns.length; ++p){
//write("\np = ",p, " ns = ",ns);
if(d_ns[p] == ns){
new_ns = false;
new_alpha = true;
for(int q = 0;q < d[p]; ++q){
if(d_alpha_1[p][q] == new_irrp_set.alpha){
new_alpha = false;
cs4 = cs.dup;
write("\ncalling split_string(cs4, i + 2 - ns, cont_l); i = ",i," ns = ",ns);
split_string(cs4, i + 2 - ns, cont_l);
unique_sort_add(igrs[ns - 2][$ - 1].rhs[q].origins,cs4);
break;}}
if(new_alpha){
// write("\n1 n = ",n," ns = ",ns);
IRRP_set irrps = IRRP_value(i + 2, cont_l, cont_r, new_irrp_set.alpha, cs, ns, new_irrp_set.rhs, new_irrp_set.n_derivation, new_irrp_set.n_machine);//csp1 is a CS_pair not needed
igrs[ns - 2][$ - 1].rhs ~= irrps;
d_alpha_1[p] ~= new_irrp_set.alpha;
++d[p];}
break;}}
if(new_ns){
IRRP_set irrps = IRRP_value(i + 2, cont_l, cont_r, new_irrp_set.alpha, cs, ns, new_irrp_set.rhs, new_irrp_set.n_derivation, new_irrp_set.n_machine);
d ~= 1;
d_ns ~= ns;
d_alpha_1 ~= [new_irrp_set.alpha];
//for( int i1 = 0;i1 < d_alpha_1.length; ++i1){
// write("\n");write(d_alpha_1[i1]);}
igr1 = new IGR;
// igrs[ns - 2] ~= new IGR;
//write("\ncs0_list = ");array_CS_write(stdout,cs0_list);
//foreach(int i1,ref cs11; cs0_list){
//cs0_list is calculated once for each value of old alpha and is the set of new origins.
//irrp_set_old should be cut down to the right size, and then unique_sort_added
//to the origins of the lhs of the new IGR. cs0_list is modified but it is not used again in this loop iteration.
//this is not correct -- see line 356 in output
//old code
// irrp_set_old.origins ~= cs11.dup;
// split_string(irrp_set_old.origins[i1], i + 2 - ns, cont_l);}
//write("\ni = ",i," ns = ",ns,"\nirrp_set_old.rhs = ");CS_write(stdout,irrp_set_old.rhs);
igr1.rhs = [irrps];
igr1.context ~= new Context_pair(cont_l, cont_r);
if(igrs.length <= ns - 2) ++igrs.length;
// write("\ncomparing lhs irrp_sets");
// write("\nigr1.lhs = ");IRRP_set_write(stdout,igr1.lhs);
if(igrs[ns - 2].length){
// write("\nigrs[ns - 2].length = ",igrs[ns - 2].length);
// write("\nigrs[ns - 2] = ");array_IGR_write(stdout,igrs[ns - 2]);//element is null IGR
// write("\nigrs[ns - 2][$ - 1] = ");IGR_write(stdout,igrs[ns - 2][$ - 1]);
// write("\nigrs[ns - 2][$ - 1].lhs = ");IRRP_set_write(stdout,igrs[ns - 2][$ - 1].lhs);
if(igr1.lhs == igrs[ns - 2][$ - 1].lhs){//if new IGR.lhs == previous IGR.lhs then the rhs's should be the same
// write("\ncontext pairs combined");
igrs[ns - 2][$ - 1].context ~= igr1.context;}//and the new context pair(cp) is added the the old set of cp's.
else{igrs[ns - 2] ~= igr1;}}
else{igrs[ns - 2] ~= igr1;}
}}
}//ends loop over j or equivalently new alpha
write("\nd_ns = ");write(d_ns);
foreach(ns1; d_ns){
char[] cont_l,cont_r;
IRRP_set irrp_set_old = new IRRP_set;
irrp_set_old.rhs = cs2.dup;
write("\n calling split_string(irrp_set_old.rhs, i + 2 - ns1, cont_r); i = ",i," ns1 = ",ns1);
split_string(irrp_set_old.rhs, i + 2 - ns1, cont_r);
//need condition based on no1co to find which origins in the rhs of the original IGR to include for that ns.
foreach(x; no1co_array){
foreach(y; x.nota){
if(ns1 == y.n_symb){
if(ns1 == 3){
write("\ni = ",i," ns1 = ",ns1);
write("\n x.cs0 = ");CS_write(stdout,x.cs0);}
write("\nno1co_array = ");
no1co_array_write(stdout,no1co_array);//does never have y.n_symb = 3 it seems
write("\nend of no1co_array\n");
write("\ncalling split_string(x.cs0, i + 2 - ns1, cont_l); i = ",i," ns1 = ",ns1);
split_string(x.cs0, i + 2 - ns1, cont_l);
if(ns1 == 3){write("\n x.cs0 = ");CS_write(stdout,x.cs0);}
unique_sort_add(irrp_set_old.origins, x.cs0);
//write("\nx.cs0 = ");CS_write(stdout, x.cs0);
if(ns1 == 3){write("\nirrp_set_old.origins = ");array_CS_write(stdout,irrp_set_old.origins);}
break;}}}
//write("\nirrp_set_old = ");IRRP_set_write(stdout,irrp_set_old);
igrs[ns1 - 2][$ - 1].lhs = irrp_set_old;
write("\nnew IGR is ");IGR_write(stdout,igrs[ns1 - 2][$ - 1]);}
}//ends loop over o_irrp_set or equivalently old alpha
}//ends loop over cp (context pairs) of input IGR
}//ends loop over igr of a set of IGR's.
}//ends loop over j1
}//ends loop over i
foreach(i,x; igrs){
write("\n IGR's of length: ",i + 2);
write("\n");
foreach(y;x){writeln(); IGR_write(stdout,y);}}
}//ends program
/*
IGR[] igr_subset = [];
igr_subset = [];
igrs.length = 2;
igrs[1] = [];
foreach(ref igr; igrs[0]){
apply_F(igr,igr_subset);
igrs[1] ~= igr_subset;
igr_subset = [];}
//This set of IGR's now needs to have equivalent forms with the same lhs and rhs IRRP_sets but different
//contexts to be combined. The resulting IGR will have a set of > 1 context pairs and a corresponding
//set of CS_pairs that will be given in the corresponding order.
//Strategy: Sort igr_set2 by its lhs's, i.e. by the rhs of the IRRP_set, then by the set of origins of it.
//Then look for consecutive identical lhs's and if found, amalgamate the new IGR with the previous one.
//This requires each IGR to have previously had its origins sorted. (It may be advantageous to also
//sort their rhs IRRP_sets by alpha, and by origins within each to maximise sorting.)
//Alternatively in apply_F, when a new IRRP_set origin and rhs have been found with a non-zero number of symbols to be
//removed to contexts, check for that reduced origin and rhs in all the earlier results of the run for a given n
//and if found, add the contexts to the result, otherwise start a new IGR. This needs apply_F to be given an input argument
//which is an array of IGR's for a given n.
writeln("\n igrs[1] = ");
array_IGR_write(stdout,igrs[1]);
}
TM notes
IGRs are generated that differ only by context, and those that differ only by the origin of the LHS and the origin of the RHS.
Can these always be combined to a single composite?
if
context E1, A1 to\to B \to C1\to\to D
context E2, A1 to\to B \to C1\to\to D
context E1, A2 to\to B \to C2\to\to D
for the same alpha
C1, C2 are sets of CSs.
then is it always true that
context E2, A2 to\to B \to C2\to\to D
for the same alpha yes because the statement itself excludes the context. It can be anything.
and would this result be produced by the algorithm?
2, 1, 2 ce and 5 1 2, cc have the same rhs i.e. the same E and B.
in (3), alpha2 takes the place of the context. The proposition is true if each result of (3) gives a different B.
2cb_ 3_bd 2_ab
2db_ 2db_ 2_aa
2ab_ 5_cd 5_ca
3bc_ 4_cc
May be I'll just combine them if only the context is different.
why is IGR in line 7057 in the IGR's of length 3?
why are some IGR's of length 3 listed among those of length 2?
the last 2 entries of IRRP_set are always 0
what is the array prior to them for? needed?
RHE has no closing bracket
*/