Message Boards

GROUPS:

Utkarsh Bajaj

[WSS22] Compiling different models of computation into hypergraph rewriting

Utkarsh Bajaj, DPS International

Posted 20 days ago

278 Views

1 Reply

4 Total Likes

Follow this post

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)

, is a finite collection of hyperedges (ordered):

E⊂(V)\∅

◼

Definition (Update rule). An update rule, denoted

, for a spatial hypergraph

H=(V,E)

is an abstract rewriting rule of the form

in which a subhypergraph matching pattern

is replaced by a distinct subhypergraph matching pattern

◼

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

is a set

(H,->)

where

is a set of hypergraphs

is non-symmetric binary relation defined using the update rule.

◼

Note: the set

will not be finite in most cases.

◼

Definition (Multiway Evolution Graph). A multiway evolution graph of an HRS, denoted

multiway

is a directed acyclic graph (represents the evolution a generally non-confluent abstract rewriting system

(A,->)

) in which each vertex corresponds to a hypergraph and in which the directed edge

a->b

exists iff there is a rewrite rule application transforming

into

, where

a,b∈A

◼

Definition (Path). There is a path from a vertex

to vertex

. There is a maximal path between

and

(∀h∈H)¬(e->h)

. We denote this by

◼

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

as the starting vertex (we can merely trace back).

◼

There is a subtlety here which is obvious mathematically but not obvious for our intuition: a HRS is

(H,->)

where

is a set of hypergraphs. We define the binary relation between hypergraphs by seeing that if a single application of an update rule can transform one hypergraph into another hypergraph. However, we are only considering hypergraphs in the set

. So if there is a rule that transforms one hypergraph into another hypergraph which is not in the set

, they cannot be related because the binary relation is only defined on the set

. So we should think of this as just a set with a binary relation on it, not really update rules: update rules generate the binary relation.

◼

Definition (Halting set). Let

(H,->)

be an HRS. Then

G∈H

is in the halting set of an HRS

(H,->)

, denoted

Ω(H)

, iff there exists a maximal path in the multiway evolution graph for

⧦

GG'

for some

G'∈G

. If

G∈H

is not in the halting set, then it means that every path in the multiway system is non-maximal i.e. it doesn’t stop. We say that

G↑

in this case.

◼

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

◼

Definition (Tape at time

t∈

). Let

T=(Q,Γ,δ,

halt

)

be a Turing machine where

is a finite set of internal states,

is the finite tape alphabet,

halt

is the halting state, and

is the initial state. Let

w∈

be the initial tape (where to the left and right we have 0s). The tape at time

, denoted

T(t)

, is defined inductively.

T(1)=w

. Then

T(t+1)=δ(T(t))

where

t>=1

where

δ(w)

for any word

is the new word produced on the tape after one application of the transition function.

Now, the definition of a HRS simulating a Turing Machine.

◼

Definition (Hypergraph rewriting system simulates a Turing machine). Let

T=(Q,Γ,δ,

halt

)

be a Turing machine where

is a finite set of internal states,

is the finite tape alphabet,

halt

is the halting state, and

is the initial state. Let

(H,->)

be a hypergraph rewriting system. Then

(H,->)

simulates

∃f

->H

such that

∀w∈Ω(T)

f(w)G'

and

G'∼f(w')

, where

w'=T(w)↓

∀w∈

\Ω(T)

(∀N∈)(∃n>=N)f(w)

, where

∼f(T(n))

It should be the case that if the HRS

(H,->)

can simulate any Turing machine

, then it should be able to compute any partial recursive function under a suitable definition of computability. Defining a precise notion of computability for hypergraphs that is able to leverage its flexibility and is most “suited” for hypergraphs is one of the future goals of the project. However, a tentative definition has been produced below (we represent

n∈

(n+1)

cyclic graph).

◼

Definition (One parameter family of maps

)

We first define a few graphs like these.

In[]:=

cyclicgraph[n_]:=If[n0,{{0,0}},Join[Table[{i,i+1},{i,0,n-1}],{{n,0}}]]

In[]:=

cyclicgraph[n_,start_]:=If[n0,{{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_]:=Ifk==1,cyclicgraph[n],Joincyclicgraph[n],Floor

,n+1,n+1+#&[χ3[n,k-1]](*CYCLICGRAPHSSTRINGEDTOGETHER*)

χ4[n_,k_]:=Ifk==1,χ2[n],JoinJoincyclicgraph[n],Floor

,n+1,n+1+#&[χ3[n,k-1]]+4,stateGraph[0],{{3,4}}(*CYCLICGRAPSHSTRINGEDTOGETHERWITHSTATEATTACHEDTOFIRSTONE(INONEEND)*)

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



->

is said to partial computable if there exists an HRS

(H,->)

(where

is a set of hypergraphs and

is a binary relation on

) and one map

χ:



->H

out of the one-parameter family of maps defined above such that

∀n∈

for which

f(n)

is defined,

χ(n)∈Ω(H)

and

χ(n)G

, where

is isomorphic to

f(n)

cyclic graph. Also, for every

outside the domain of

χ(n)

Now that we have a notion of computability, we can prove a few theorems/lemmas.

◼

Lemma. The successor function

n↦n+1

is partial computable

◼

Proof. Let

. Then, we can show that for all

(n)

n+1

under the rule successor:

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

Logic: EquationalLogic	Steps: 63
Theorem: (4⊕5)⊙((5⊕6)⊙((6⊕4)⊙((1⊕1)⊙((2⊕2)⊙((3⊕3)⊙((1⊕2)⊙(1)))))))(0⊕1)⊙(1)



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

is computable

◼

Proof. Let

. The rule is the empty rule.

In[]:=

identity={};

◼

Lemma. The function

n↦0

is computable.

◼

Proof. Let

. The rule is constant 0, given below:

In[]:=

constant0=convertToStringRule[{{1,2},{2,3}}<->{{1,3}}];

In[]:=

FindWolframModelProof[χ1[10]<->cyclicgraph[0],constant0]

Out[]=

ProofObject

Logic: EquationalLogic	Steps: 17
Theorem: (5⊕6)⊙((6⊕7)⊙((7⊕8)⊙((8⊕9)⊙(1))))0⊕0



◼

Lemma. The function

n↦kn

where

k∈

is computable.

◼

Proof. Let χ by

(with the second argument being

. Note that we can enumerate all of these). The rule is:

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



Logic: EquationalLogic	Steps: 240
Theorem: (0⊕1)⊙((1⊕2)⊙((2⊕3)⊙((3⊕4)⊙((4⊕5)⊙((5⊕6)⊙((6⊕7)⊙(1)))))))(0⊕1)⊙(1)

Data not in notebook. Store now



◼

Lemma. The function

(

)↦

is computable.

◼

Proof. let’s choose

χ[2,{

},0]

as the initial graph. The rule is as follows:

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,Σ,δ,

,F)

, we need to convert it into the associated hypergraph rewriting system i.e. an initial hypergraph and a collection of rules.

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_Integery_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

is represented by hypergraph

and 0 is represented by hypergraph

. Then, we will also have hypergraphs for the states

and

represented by

and

. Then, if the input to the DFA is 1011, then the input hypergraph would

(

)⊕

⊕

where χ and ⊕ are binary operators on the space of hypergraphs. Then, the first transition function applied would be

δ(

,1)

. There should be a rewrite rule

corresponding to this transition function that brings the hypergraph

(

)⊕

⊕

into

(

)⊕

⊕

. And so on. The rule corresponding to the transition function

δ(

,_)

should apply iff the first graph is of the form





where

can be anything. Then, we have a finite rewrite rule as well that applies to any state graph but not any other graph. Thus, we have to satisfy the following conditions:

◼

Any state graph

should not be equal to or be a subgraph of other state graph

where

i≠j

◼

Any state graph

should not be equal or be a subgraph of any other

where

j≠i

. Also,

should not be a subgraph of any other state graph

◼

Note that this implies that no graph

is a subgraph or is equal to the graph

where

(i,j)≠(k,l)

◼

The rule

, corresponding to the transition function

δ(i,j)

i.e. when in state

and alphabet

should apply iff the hypergraph is of the form



⊕

⊕

⊕..

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

δ(

,2)=

In[]:=

RulePlot[ResourceFunction["WolframModel"][DFARule[{1,2,0}]],VertexLabels->Automatic]

Out[]=

The preserved vertex is the link between the symbol (in

) to the left and the symbol to the right (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

[WSS22] Compiling different models of computation into hypergraph rewriting

Section 0: Definitions, speculations, and some preliminary results

Section 1: Converting FSMs into Hypergraph rewriting

Subsection 1. DFAs

Subsection 2. NFAs

Section 2. Converting Turing-complete Imperative machines into Hypergraph rewriting

Subsection 1. Turing Machines

Subsection 2. NFAs
