# Message Boards

Answer
(Unmark)

GROUPS:

4

# [WSS22] Compiling different models of computation into hypergraph rewriting

Posted 20 days ago

Compiling different models of computation into hypergraph rewriting systems by Utkarsh Bajaj University of Waterloo By computational irreducibility, it is well known that Hypergraph rewriting systems are Turing complete i.e. they can compute any Turing-computable function. The goal of this project is to interpret a model of computation (such as a Turing Machine with imperative algorithms or functional lambda calculus) as a hypergraph rewriting system. For example, just as we can interpret a DFA (deterministic finite automaton) using a Turing machine with a set of states, a tape alphabet, and transition functions, we can interpret a DFA using a Hypergraph rewriting system with an initial Hypergraph and replacement rule. The first goal of this project is make a function that takes in a finite state machine and outputs the “equivalent” Hypergraph rewrite rule with an initial hypergraph (the input). The second goal of this project is to extend the same to imperative machines like Turing machines and register machines.The third goal of this project is to get the intuition for how we might formally define the notion of computability on Hypergraph rewriting systems, by creating a compiler from a high level Turing-complete functional language (called “Faux Racket”), which is defined below.
Section 0: Definitions, speculations, and some preliminary results To get started, let’s formally define hypergraph rewriting systems as a computational system, as is used in the Wolfram physics project literature [1]. ◼ Definition (Wolfram Model Hypergraph). A wolfram model hypergraph/hypergraph, denoted H=(V,E) E⊂(V)\∅ ◼ Definition (Update rule). An update rule, denoted R H=(V,E) H 1 H 2 H 1 H 2 ◼ Note that the word distinct is important here. That’s the reason why the multiway evolution graph is acyclic for a wolfram model system. ◼ Definition (HRS). A hypergraph rewriting system HRS (H,->) H -> ◼ Note: the set H ◼ Definition (Multiway Evolution Graph). A multiway evolution graph of an HRS, denoted G multiway (A,->) a->b a b a,b∈A ◼ Definition (Path). There is a path from a vertex s e s * -> s e s * -> (∀h∈H)¬(e->h) s ◼ It is obvious if there is a maximal path in the multiway system for a particular vertex, then there is a maximal path in that multiway system with G ◼ There is a subtlety here which is obvious mathematically but not obvious for our intuition: a HRS is (H,->) H H H H ◼ Definition (Halting set). Let (H,->) G∈H (H,->) Ω(H) G G G'∈G G∈H G↑ ◼ Note that maximal paths are defined in the multiway system. If a hypergraph is not in an halting set, then it means that every path through the multiway system doesn’t stop running. So yes, there is no maximal path in the multiway system. Because if there is, then the initial hypergraph will be in the halting set. To understand how hypergraph rewriting works in the Wolfram language, refer to [2]. Now, we might come up with a intuitive definition for what it means for a HRS to simulate a Turing machine. First, let’s define what it means by saying “the tape at some time t ◼ Definition (Tape at time t∈ T=(Q,Γ,δ, q halt q 0 Q Γ q halt q 0 w∈ * Γ t T(t) T(1)=w T(t+1)=δ(T(t)) t>=1 δ(w) w Now, the definition of a HRS simulating a Turing Machine. ◼ Definition (Hypergraph rewriting system simulates a Turing machine). Let T=(Q,Γ,δ, q halt q 0 Q Γ q halt q 0 (H,->) (H,->) T ∃f f: * Γ 1 .∀w∈Ω(T) f(w) G'∼f(w') w'=T(w)↓ 2 .∀w∈ * Γ (∀N∈)(∃n>=N)f(w) -> n G n G n It should be the case that if the HRS (H,->) T n∈ th (n+1) ◼ Definition (One parameter family of maps χ t We first define a few graphs like these. In[]:= cyclicgraph[n_]:=If[n0,{{0,0}},Join[Table[{i,i+1},{i,0,n-1}],{{n,0}}]] In[]:= cyclicgraph[n_,start_]:=If[n0,{{start,start}},Join[Table[{i+start,i+1+start},{i,0,n-1}],{{n+start,start}}]] In[]:= convertToStringRule[rule_]:=rule/.(Table[i"x"<>ToString[i],{i,Min[#1],Max[#1]}]&)[Join[rule〚1〛,rule〚2〛]] In[]:= χ1[n_]:=cyclicgraph[n,5](*CYCLICGRAPHS*) In[]:= χ2[n_]:=Join[cyclicgraph[n,4],stateGraph[0],{{3,4}}](*CYCLICGRAPHSWITH"STATE"ATTACHED*) In[]:= χ3[n_,k_]:=Ifk==1,cyclicgraph[n],Joincyclicgraph[n],Floor n 2 χ4[n_,k_]:=Ifk==1,χ2[n],Join n 2 In[]:= χ[2,{a_,b_},state_]:=Join[cyclicgraph[a],{{Floor[a/2],a+1}},cyclicgraph[b,a+1],JoinState[a+b+1,Floor[a/2],state]] In[]:= ResourceFunction["WolframModelPlot"][χ2[10],VertexLabels->Automatic] Out[]= In[]:= ResourceFunction["WolframModelPlot"][χ3[10,3],VertexLabels->Automatic] Out[]= In[]:= χ[2,{a_,b_},state_]:=Join[cyclicgraph[a],{{Floor[a/2],a+1}},cyclicgraph[b,a+1],JoinState[a+b+1,Floor[a/2],state]] χ2[2,{2,3},2] In[]:= ResourceFunction["WolframModelPlot"][χ[2,{2,3},2],VertexLabels->Automatic] Out[]= ◼ Definition (Partial computable). A partial function f: k (H,->) H -> H χ: k ∀n∈ f(n) χ(n)∈Ω(H) χ(n) G th f(n) n f χ(n) Now that we have a notion of computability, we can prove a few theorems/lemmas. ◼ Lemma. The successor function n↦n+1 ◼ Proof. Let χ χ 2 n χ 2 C n+1 In[]:= successor={{x1,x2},{x2,x3},{x3,x},{x3,x3},{x2,x2},{x1,x1},{x1,x4},{x4,x5}}<->{{x4,x6},{x6,x5}}; In[]:= FindWolframModelProof[χ2[2]<->cyclicgraph[3],successor] Out[]= ProofObject
where the FindWolframModelProof function is defined in the Appendix, taken directly from [3]. We can visualise the evolution: In[]:= ResourceFunction["WolframModel"][{{x1,x2},{x2,x3},{x3,x},{x3,x3},{x2,x2},{x1,x1},{x1,x4},{x4,x5}}->{{x4,x6},{x6,x5}},χ2[2],"EventsStatesPlotsList"] Out[]= , ◼ Lemma. The identity function n↦n ◼ Proof. Let χ χ 1 In[]:= identity={}; ◼ Lemma. The function n↦0 ◼ Proof. Let χ χ 1 In[]:= constant0=convertToStringRule[{{1,2},{2,3}}<->{{1,3}}]; In[]:= FindWolframModelProof[χ1[10]<->cyclicgraph[0],constant0] Out[]= ProofObject
◼ Lemma. The function n↦kn k∈ ◼ Proof. Let χ by χ 3 k In[]:= multiplybyconstant=convertToStringRule/@{{{1,2},{3,2},{3,4}}<->{{1,4},{3,2},{5,6},{6,7},{7,5},{5,5},{6,6},{7,7},{5,1}},{{1,2},{2,3},{3,1},{1,1},{2,2},{3,3},{3,4},{4,5},{5,6}}<->{{4,6}}}; In[]:= FindWolframModelProof[χ3[10,3]<->cyclicgraph[30],multiplybyconstant] Out[]= ProofObject
◼ Lemma. The function ( n 1 n 2 n 1 n 2 ◼ Proof. let’s choose χ[2,{ n 1 n 2 In[]:= add2[state_]:=convertToStringRule/@{Join[{{2,1},{2,3},{4,3}},JoinState[4,2,state]]->Join[{{4,1},{2,3}},JoinState[4,2,state+1]],Join[{{1,2},{2,3}},JoinState[3,1,state+1]]->{{1,3}}} In[]:= ResourceFunction["WolframModel"][add2[0],χ[2,{4,5},0],3,"EventsStatesPlotsList"] Out[]= , , These results provide some intuition on how we might define computability on hypergraph rewriting systems. However, I think that there are better ways of defining computability. Proving that computability on hypergraph rewriting systems is closed under function composition, primitive recursion, and minimalization is non-trivial. That’s why I decided to compile different existing models of computation into hypergraph rewriting systems and see which ones are the most “natural” to hypergraph rewriting systems because it is difficult, a priori, to come up with a definition of computability of partial functions that leverage the flexibility of hypergraph rewriting systems. So, I’ve decided to explicitly convert Finite state machines, single-tape Turing machines, register machines, and “Faux racket” into hypergraph rewriting systems. The conclusion is that that hypergraph rewriting systems, although Turing-complete like other models, are “powerful”/efficient enough to compile a functional language like Faux racket with only very minimal set of replacement rules. On a surface level, it has been realised that hypergraph rewriting systems are more efficient than a single-tape Turing machines for the same reason that multi-tape Turing machines are more efficient that single tape Turing machines. More precisely, the notion of concurrent programming is very natural to an HRS. For example, as opposed to how an ordinary compiler might create stack frames to perform computations sequentially, in hypergraph rewriting systems, we can a “new stack” itself by creating a disconnected hypergraph, and performing computations there. In this way, we can increase the “dimension” of an HRS to support concurrent programming whenever possible. These ideas are elaborated upon in the last section on faux racket to hypergraph conversion. It will be apparent to the reader that when we will simulate Turing machines and Register machines using hypergraph rewriting, we only use a very specific class of hypergraphs and rewrite rules.
Section 1: Converting FSMs into Hypergraph rewriting
Subsection 1. DFAs Given a DFA (Q,Σ,δ, q 0 It is quite trivial to convert DFAs to hypergraph rewriting. A DFA consists of a number of states and an alphabet. So we begin by defining simple graphs for symbols in an alphabet Σ In[]:= alphabetGraphHelper[n_]:=If[n==0,{{1,1},{1,2}},If[n==1,{{1,2},{2,1}},Module[{x},x=Last[#][[1]]&[alphabetGraphHelper[n-1]];Join[Drop[#,-1],{{x,x+1},{x+1,1}}]&[alphabetGraphHelper[n-1]]]]] In[]:= alphabetGraph[n_]:=If[n==0,{{1,1},{1,2}},Append[alphabetGraphHelper[n],{1,n+2}]] In[]:= ResourceFunction["WolframModelPlot"][#,VertexLabels->Automatic]&/@Table[alphabetGraph[n],{n,0,8}] Out[]= , , , , , , , , In[]:= stateGraph[n_]:=Join[Table[{i,i},{i,1,n+3}],Table[{i,i+1},{i,1,n+3-1}],{{n+3,1}}] In[]:= graphToHypergraph[g_]:=g/.x_Integery_Integer{x,y} In[]:= concatenategraphs[g1_,g2_]:=graphToHypergraph[Join[{Max[VertexList[g1]]Max[VertexList[#]]},#]]&[EdgeList[GraphDisjointUnion[g1,g2]]] In[]:= ResourceFunction["WolframModelPlot"][#,VertexLabels->Automatic]&/@Table[stateGraph[n],{n,1,8}] Out[]= , , , , , , , The reason why we have loops on state graphs is to ensure that when we apply rewrite rules, we have no overlapping subhypergraphs with state graphs. Essentially, we have to obey 4 conditions: no 2 distinct state graphs are subgraphs of each other, no 2 distinct alphabet graphs are subgraphs of each other, a state graph is not a subgraph of any alphabet graph, and any alphabet graph is not a subgraph of any state graph. The above encoding satisfies these conditions. The reason why we have starting iterating the state graphs from 3 is preuly due to some edge cases that need to be handled. At a particular step, there will be all types of rewrite rules. But we only want to make sure only one rewrite rule will be applied that brings the DFA onto the first step. That’s where we can use graph concatenation. For instance, let’s say 1 A 1 A 0 q 0 q 1 S 0 S 1 ( S 0 A 1 A 0 A 1 A 1 δ( q 0 R 01 ( S 0 A 1 A 0 A 1 A 1 ( S 1 A 0 A 1 A 1 δ( q i S i A j j ◼ Any state graph S i S j i≠j ◼ Any state graph S i A j j≠i A j S i ◼ Note that this implies that no graph S i A j S k A l (i,j)≠(k,l) ◼ The rule R ij δ(i,j) q i j S i A j A i 1 A i 2 A i 3 In[]:= concatenategraphs[g1_,g2_]:=graphToHypergraph[Join[{Max[VertexList[g1]]Max[VertexList[#]]},#]]&[EdgeList[GraphDisjointUnion[g1,g2]]] In[]:= initialWordToHypergraphHelper[word_List,acc_]:=If[word=={},acc,initialWordToHypergraphHelper[Drop[word,1],concatenategraphs[acc,alphabetGraph[word[[1]]]]]] In[]:= initialWordToHypergraph[word_List]:=initialWordToHypergraphHelper[Drop[word,1],concatenategraphs[stateGraph[0],alphabetGraph[word[[1]]]]] In[]:= Graph[initialWordToHypergraph[{0,1,2,3,4,5,5,2,2,3}],VertexLabels->Automatic] Out[]= So we can convert any word into an initial hypergraph. In[]:= DFARule[{stateI_,alphabet_,stateF_}]:=((#->ReplaceAll[stateGraph[stateF],Join[Table[i->Max[VertexList[#]]+i,{i,1,stateF+3-1}],{stateF+3->Max[VertexList[#]]}]])&)[concatenategraphs[stateGraph[stateI],alphabetGraph[alphabet]]] The following represents δ( q 1 q 0 In[]:= RulePlot[ResourceFunction["WolframModel"][DFARule[{1,2,0}]],VertexLabels->Automatic] Out[]= The preserved vertex is the link between the symbol (in Σ Σ In[]:= DFAtoHypergraph[rules_List,word_]:=ResourceFunction["WolframModel"][Table[DFARule[i],{i,Map[Join[#[[1]],#[[2]]]&,(rules/.Rule->List)]}],initialWordToHypergraph[word],Length[word],"EventsStatesPlotsList"] In[]:= DFAtoHypergraph[{{0,0}->{0},{0,1}->{1},{1,0}->{0},{1,1}->{1}},{0,1,1,1,1,1,0}] Out[]= , , , , , , , The DFA is constructed in such a way so that if the final symbol is 0, then the final state is 0. And if the final symbol is 1, the final state is 1. We can see that the above holds. In[]:= DFAtoHypergraph[{{0,0}->{0},{0,1}->{1},{1,0}->{0},{1,1}->{1}},{0,1,1,0,1,1,1}] Out[]= , , , , , , , So, DFAs are converted to Turing machines in a pretty direct manner. The state of a Turing machine is represented by a subgraph that attaches itself to the symbol it is currently reading, and then moves to the right to the next symbol. It continues to do so until there are no symbols left to read, and we end up with the final state. One may ask: why do we need a state subgraph? All models of finite state machines, Turing machines, and register machines are sequential in nature. So states in these models are used to impose a definite order of evaluation. In hypergraph rewriting systems, the analogy to a state is this subgraphs that moves along the hypergraph to dictate the application of a rule, to effectively impose a definite updating order. From here, it is also pretty easy to implement Turing machines because it is similar to a DFA, except that the state subgraphs can move either to the left or right, and can change the symbols.
Subsection 2. NFAs
Section 2. Converting Turing-complete Imperative machines into Hypergraph rewriting
Subsection 1. Turing Machines We use the same approach as in DFAs. In[]:= initialTapeToHypergraph[word_List]:=Module[{x,y,z},x=initialWordToHypergraph[word];y=Max[VertexList[concatenategraphs[stateGraph[0],alphabetGraph[word[[1]]]]]];z=Max[VertexList[x]];Join[x,{{y,z+1,z+2},{z,z+3,z+4,z+5}}]] In[]:= ResourceFunction["WolframModelPlot"][initialTapeToHypergraph[{0,1,2}],VertexLabels->Automatic] Out[]= The hyperedges at the ends indicate the left and right ends of the tape. I have introduced those so that if the head wants to move to the right, beyond the currently defined tape, there will be a special rewrite rule that will create the 0 symbol and join it to the existing tape, extending the right hyperdge to indicate the new end of the tape. Same goes for the left hyperedge. In[]:= TuringRule[{stateI_,symbolI_}->{stateF_,symbolF_}]:={#->Join[JoinState[Max[VertexList[#]],Max[VertexList[#]],stateF],JoinAlphabet[stateF+3+Max[VertexList[#]],Max[VertexList[#]],symbolF]]}&[concatenategraphs[stateGraph[stateI],alphabetGraph[symbolI]]] In[]:= TuringRule[{stateI_,symbolI_}->{stateF_,symbolF_,offset_}]:=If[offset==0,TuringRule[{stateI,symbolI}->{stateF,symbolF}],Module[{x=Max[VertexList[#]]},If[offset==1,(*theedgecases---literally*){Join[#,{{x,x+1}}]->Join[JoinState[x+1,x+1,stateF],JoinAlphabet[stateF+3+x+1,x,symbolF],{{x,x+1}}],Join[#,{{x,x+1,x+2,x+3}}]->Join[JoinState[x+4,x+4,stateF],JoinAlphabet[stateF+3+x+4,x,symbolF],JoinAlphabet[stateF+3+x+4+symbolF+2,x+4,0],{{x,x+4},{x+4,x+4+stateF+3+symbolF+6,x+4+stateF+3+symbolF+7,x+4+stateF+3+symbolF+8}}]},If[offset==-1,{Join[#,{{x+1,x}}]->Join[JoinState[x+1,x+1,stateF],JoinAlphabet[stateF+3+x+1,Max[VertexList[#]],symbolF],{{x+1,x}}],Join[#,{{x,x+1,x+2}}]->Join[JoinState[x+5,x+3,stateF],(*jointhestateatx+3*)JoinAlphabet[stateF+3+x+5,x,symbolF],(**)JoinAlphabet[stateF |