Nestedly Recursive Functions extend traditional recursion by embedding self-referential calls within layered structures, leading to complex and often unpredictable computational behaviors. This project studies a specific Nestedly Recursive Function which could simulate 2-tag system, that is Turing complete. This shows NRF is indeed capable of universal computation, and sheds light into a deeper question: “what is the simplest universal nested recursive function?”.

1:Project Background

1.1:Introduction to Nestedly Recursive Functions

Nestedly Recursive Functions (NRF) are essentially functions that, when evaluated, access recursively other values on their domain. An example is:
F(n)n-F(F(n-1)),F(1)F(3)1
NRF leads to complex and often unpredictable computational behaviors. As explored by Stephen Wolfram in Nestedly Recursive Functions, these functions arise in combinatorics, formal systems, and foundational computation, revealing deep connections between recursion and universality.
A nested recurrence relation
A(n)
is said to be undecidable if the following problem is undecidable: given a finite set of initial conditions for
A(n)
, is the recurrence relation calculable? Here calculable means that for every
n≥0
, either
A(n)
is an initial condition or the calculation of
A(n)
involves only invocations of
A
on arguments in
{0,1,...,n-1}
.

1.2:Introduction to 2-tag system

A 2-tag system is a computationally universal string rewriting model with a finite alphabet that operates by iteratively deleting a fixed number of leading 2 symbols and appending new symbols based on simple production rules. Despite their minimalistic design, these systems can simulate Turing machines and exhibit complex computational behaviors.
A 2-tag systems is depicted below, which uses alphabet
Σ{a,b,c}
, an initial string
W
0
abab
and production rules
Δ
given by:
Δ:aabb,bc,ca
In[]:=
TagSystemNew[2,{"a"->"abb","b"->"c","c"->"a"},Characters@"abab"]
Out[]=
{abab,ababb,abbabb,babbabb,bbabbc,abbcc,bccabb,cabbc,bbca,cac,ca,a}
We use red to represent
a
, and green for
b
, blue for
c
, and produce an array plot.
In[]:=
TagPlot@TagToIntList@TagSystemNew[2,{"a"->"abb","b"->"c","c"->"a"},Characters@"abab",20]//Grid[{{#},{"2-Tag System"}},Frame->All]&
Out[]=
2-Tag System

2:Simulating 2-tag system with a NRF

The question being attacked here “can a nestedly recursive function be universally computable”, or more specifically in this scenario, “is there such a NRF that is capable of simulating any 2-tag system？”
The formulation studied and presented here was proposed by An Undecidable Nested Recurrence Relation. Such construction relies on tag system writing one symbol at a time, what leads to another computational model.

2.1:Reverse tag system

A reverse tag system consists of a finite set of symbols
Σ
, a set of production rules
δ:
2
Σ
Σ
, a function
d:ΣN
, and an initial word
W
0
∈
*
Σ
. While an ordinary tag system modifies a word by removing a fixed number of symbols from the beginning and adding a variable number of symbols to the end, the situation is reversed in a reverse tag system. A single computation step of a reverse tag system is described by the operation
w
1
...
w
k

w
d(y)+1
...
w
k
y,
where
yσ(
w
1
,
w
k
)
. Given a word that starts with
w
1
and ends with
w
k
, the production rule for the pair
(
w
1
,
w
k
)
yields a symbol
y
which is appended to the end of the word. Then, the first
d(y)
symbols are removed from the beginning of the word. If at some point the
d(y)
exceeds k, then the reverse tag system halts.

2.2:Reverse tag system to 2-tag system

We follow by showing how one can use reverse tag system to simulate/run 2-tag system.Consider a 2-tag system
T(Σ,Δ,
W
0
)
, let
u
be the maximum length of strings replaced in the substitution rules, and
′
Σ
be an alphabet of size u times the length of
Σ
, where each letter consists of an original letter from
Σ
augmented with
u
subscripts
1,2,...,u
.For each
s
i
∈Σ
, write
Δ(
s
i
)
as
s
i,
l
i
...
s
i,2
s
i,1
.The production rules of
δ
include the rules
δ(
[
s
i
]
*
,
[*]
1
)
[
s
i,
l
i
]
l
i
​
δ
[
s
i
]
*
,
[
s
i,j
]
j

[
s
i,j-1
]
j-1
where
*
represents an arbitrary symbol or subscript.
The deletion numbers are specified by
d
[s]
j

0
if j>1
2
if j1
Finally let
′
W
0
be the result of adding a superscript
1
to each character in
W
0
.
Now we say reverse tag system
R(
′
Σ
,δ,d,
′
W
0
)
simulates 2-tag system
T(Σ,Δ,
W
0
)
. It can be proven that extracting every step where delete function gives
2
from
R
(ignoring the subscripts) yields the execution steps of
T
.
See some examples of tag systems X their reverse tag system version being simulated:
In[]:=
With[{rule={"a"->"abb","b"->"c","c"->"a"},initial=Characters@"abb"},​​{revSymbols,revInitials,revRulesA,revRules,RevDelete}=TagToReverseTagSystem[2,rule,initial];​​{TagPlot@TagToIntList@TagSystemNew[2,rule,initial,20],TagPlot@RevTagToIntList@ReverseTagSystem[revRules,RevDelete,revInitials,20]}​​]//Grid[{#,{"2-Tag","Reverse 2-Tag"}},Frame->All]&
Out[]=
2-Tag
Reverse 2-Tag

2.3: Reverse tag system to
B(n)

We define a conditional NRF
B(n)
(defined on natural numbers) as
B(n)
B(n-2)+2B(B(n-1))
if n is even,
B(2B(n-2-B(n-1))+B(n-2))
if n is odd.
And we aim to simulate a reverse tag system
R(Σ,δ,d,
W
0
)
by carefully selecting the initial condition of
B(n)
- in fact this is the only way one can encapsulate information in a potential computational NRF.
Assuming
Σ{
s
1
,
s
2
,...,
s
t
}
, a function
α
is defined as follows:
α(
s
i
)
i+1
4
+2
2i+2
2
+2
,​
α(
s
i
,
s
j
)2α(
s
i
)+α(
s
j
)
2i+3
2
+
2j+2
2
+6
.
The fact that
α
is injective can be seen by considering the binary representation of such numbers.
The encoding for
d
and
δ
is done respectively as follows:
B(α(
s
i
))1-d(
s
i
)
​
B(α(
s
i
,
s
j
))αδ(
s
i
,
s
j
)
Let
c
0
α(
s
t
,
s
t
)+2
, we encode
W
0
(suppose
W
0

q
1
q
2
...
q
m
) as follows:
B(
c
0
+2k-1)α(
q
k
),1≤k≤m
Specifically, we let
B(
c
0
+2m)2m-2
, and let
B(k)0
if
0≤k<
c
0
+2m
and
B(k)
hasn’t been defined above.
Suppose that at the
i
th computation step of
R
, the word
W
w
1
w
2
...
w
k
is produced. It can be proven that the following equalities hold :
(B(n-2k+1),...,B(n-3),B(n-1))(α(
w
1
),α(
w
2
),...,α(
w
k
))
​
​
B(n)2k-2
where
n
c
0
+2m+2i
.
Thus we can say
B(n)
with the initial condition given above simulates
R(Σ,δ,d,
W
0
)
.
But the function itself is conditional, so we still need one extra step in order to provide a “truly” Nested Recursive Function:
A(n)
.
In[]:=
With[{rule={"a"->"abb","b"->"c","c"->"a"},initial=Characters@"abb"},​​{revSymbols,revInitials,revRulesA,revRules,RevDelete}=TagToReverseTagSystem[2,rule,initial];​​{BG,steps}=ReverseTagToBGraph[revSymbols,revInitials,revRulesA,revRules,RevDelete];​​BG[steps-1]​​]
Out[]=
The following gif show how
B(n)
computes step by step:
In[]:=
With[{rule={"a"->"abb","b"->"c","c"->"a"},initial=Characters@"abb"},​​{revSymbols,revInitials,revRulesA,revRules,RevDelete}=TagToReverseTagSystem[2,rule,initial];​​{BG,steps}=ReverseTagToBGraph[revSymbols,revInitials,revRulesA,revRules,RevDelete];​​graphList=BG/@Range[0,steps-1];​​coordinates=Thread[VertexList[Last@graphList]->GraphEmbedding[Last@graphList]];​​Graph[#,​​ImageSize->1400,PlotRange->{{-5.5,9.5},{0.5,5.5}},​​GraphLayout->{"LayeredDigraphEmbedding","Orientation"->Left},​​VertexCoordinates->coordinates,EdgeShapeFunction->"CurvedArc",EdgeStyle->Arrowheads[0.05]​​]&/@graphList​​]//ListAnimate

Concluding Remarks

Acknowledgments

Pietro Pepe, Stephen Wolfram

References

1
.
Stephen Wolfram (2024), “Nestedly Recursive Function,”.https://writings.stephenwolfram.com/2024/09/nestedly-recursive-functions/
2
.
A. Marcel Celaya and B. Frank Ruskey (2012), “An Undecidable Nested Recurrence Relation”. https://arxiv.org/pdf/1203.0586

Cite This Notebook

“Computability on Nestedly Recursive Functions (NRF)”
by Bowei Xv
Wolfram Community, 2025.7.9
https://community.wolfram.com/groups/-/m/t/3497880