Axioma ic S uc u e o Compu a ional Uni e ses:
Disc e e Con igu a ions, Upda e Rela ions, and he
Uni ied Time Scale F amewo k
Haobo Ma1Wenlin Zhang2
1Independen Resea che
2Na ional Uni e si y o Singapo e
No embe 24, 2025
Abs ac
Unde he assump ions o ini e in o ma ion densi y and local e e sible up-
da es, we p o ide a uni ied axioma ic de ini ion o he “compu a ional uni e se.”
The co e objec is a quad uple Ucomp = (X, T,C,I), whe e Xis he disc e e con ig-
u a ion space o he en i e uni e se, T⊂X×Xis he one-s ep upda e ela ion, C
is he single-s ep cos ( ime, ene gy, o ga e coun ), and Iis a s a e unc ion cha -
ac e izing “in o ma ion quali y.” We in oduce axioms o locali y, ini e me ici y,
and (gene alized) e e sibili y, p o ing ha classical Tu ing machines, cellula au-
oma a, and e e sible quan um cellula au oma a can all be embedded as special
cases wi hin his amewo k.
Fu he mo e, we p o e ha unde he uni ied ime scale hypo hesis (i.e., he
exis ence o a single-s ep cos unc ion compa ible wi h physical sca e ing ime
scales), he con igu a ion g aph (X, T,C) induces a “complexi y geome y” in ap-
p op ia e limi s, whose geodesic dis ances a e equi alen o a con inuous e sion
o adi ional ime complexi y. Finally, we cha ac e ize ela ionships be ween di -
e en compu a ional uni e ses ia simula ion mappings, cons uc ing a ca ego y
CompUni wi h compu a ional uni e ses as objec s and s uc u e-p ese ing sim-
ula ions as mo phisms, p o ing ha he classical Tu ing uni e se, classical cellula
au oma on uni e se, and quan um cellula au oma on uni e se o m equi alen ull
subca ego ies wi hin his ca ego y.
As he i s wo k in he “Compu a ional Uni e se Theo y” se ies, his pape
aims o p o ide a minimal disc e e and physicalizable axioma ic ounda ion, es ab-
lishing a uni ied benchma k s uc u e o subsequen complexi y geome y, in o ma-
ion geome y, and he ca ego y equi alence be ween physical and compu a ional
uni e ses.
Keywo ds: Compu a ional Uni e se, Cellula Au oma a, Tu ing Machine, Quan um
Cellula Au oma a, Uni ied Time Scale, Complexi y Geome y, Simula ion, Ca ego y
Equi alence
MSC 2020: 68Q05, 68Q10, 81P68, 68Q12, 18D99
1
1 In oduc ion
“The uni e se is compu a ion” ep esen s a uni ied ision spanning physics, compu e
science, and in o ma ion heo y. I he en i e uni e se is iewed as a as disc e e dy-
namical sys em, hen adi ional models such as classical Tu ing machines, cellula au-
oma a, and e e sible quan um cellula au oma a can be unde s ood as di e en slices
o his “compu a ional uni e se.” Howe e , in exis ing li e a u e, hese models a e o -
en de eloped sepa a ely, a ely appea ing wi hin a uni ied axioma ic sys em, le alone
es ablishing sys ema ic connec ions wi h physical ime scales, geome ic s uc u es, and
ca ego y- heo e ic “equi alences be ween uni e ses.”
The goal o his pape is o cons uc such a ounda ional laye : unde minimal as-
sump ions, we p o ide an abs ac “compu a ional uni e se objec ” Ucomp, cha ac e izing
i s s uc u e and cons ain s h ough a clea se o axioms o simul aneously encompass:
1. Classical Tu ing machines and hei “Tu ing uni e ses”;
2. Classical cellula au oma a and mo e gene al local disc e e dynamical sys ems;
3. Re e sible quan um cellula au oma a (QCA) and hei uni e se models.
We emphasize wo poin s:
On one hand, he en i e amewo k is disc e e: uni e se s a es a e modeled as
poin s on a coun able se X, and ime e olu ion is ealized by s epping on a g aph
(X, T);
On he o he hand, he cos unc ion Cis in e p e ed as disc e e samples o a uni ied
ime scale, p o iding a b idge o subsequen ly iewing complexi y as “geome ic
leng h.”
On his basis, we de ine “simula ion mo phisms” be ween di e en compu a ional uni-
e ses, cons uc ing he ca ego y CompUni . This no only uni ies adi ional “mul i-
model compu abili y equi alence” esul s bu also p o ides an abs ac amewo k o
subsequen ly es ablishing “equi alence be ween physical uni e se ca ego ies and compu-
a ional uni e se ca ego ies.”
The s uc u e o his pape is as ollows. Sec ion 2 p o ides basic no a ion and p e-
limina ies. Sec ion 3 p esen s he axioma ic de ini ion o compu a ional uni e se objec s.
Sec ions 4 and 5 espec i ely explain how Tu ing machines, classical cellula au oma a,
and quan um cellula au oma a a e embedded wi hin his amewo k. Sec ion 6 in o-
duces he uni ied ime scale and basic cons uc ions o complexi y geome y. Sec ion 7
cons uc s simula ion mo phisms and he ca ego y CompUni . The appendices p o ide
de ailed p oo s o main p oposi ions and heo ems along wi h se e al echnical discus-
sions.
2 P elimina ies and No a ion
All se s, mappings, and algeb aic s uc u es in his pape a e discussed wi hin he back-
g ound o Ze melo–F aenkel se heo y wi h he axiom o choice. By de aul , all se s a e
a mos coun able unless o he wise s a ed.
2
1. Le N={0,1,2, . . . },Zbe he se o in ege s, Rbe he eal ield.
2. Fo a se X, le P in(X) deno e he amily o ini e subse s o X.
3. I G= (V, E) is a di ec ed g aph, hen Vis he e ex se and E⊂V×Vis he
di ec ed edge se .
4. Fo a Hilbe space H, le B(H) deno e he algeb a o bounded linea ope a o s. I
U∈ B(H) sa is ies U∗U=UU∗= id, hen Uis called uni a y.
5. When unambiguous, deno e he image o :A→Bas (A) and he p eimage as
−1(C).
We a e pa icula ly conce ned wi h locali y and ini e in o ma ion densi y, which
na u ally appea in classical cellula au oma a and QCA. Fo uni o mi y, we adop he
ollowing abs ac se ing.
De ini ion 2.1 (Local S uc u e).Le Xbe a coun able se . A local s uc u e is a
ini e-deg ee di ec ed g aph GX= (X, EX), whe e o each x∈X,
deg+(x) = |{y: (x, y)∈EX}| <∞
deg−(x) = |{y: (y, x)∈EX}| <∞
In ui i ely, GXcha ac e izes he ini e- ange adjacency ela ion o each con igu a ion in
“space.”
3 Axioma iza ion o Compu a ional Uni e se Objec s
This sec ion p esen s he co e objec o his pape : he axioma ic de ini ion o a compu-
a ional uni e se Ucomp.
3.1 Basic Da a o Compu a ional Uni e se
De ini ion 3.1 (Compu a ional Uni e se Objec ).A compu a ional uni e se objec is a
quad uple
Ucomp = (X, T,C,I)
whe e:
1. Xis a coun able se , called he con igu a ion space o he uni e se;
2. T⊂X×Xis he one-s ep upda e ela ion;
3. C:X×X→[0,∞] is he cos unc ion;
4. I:X→Ris he in o ma ion quali y unc ion.
To iew his as a “uni e se-scale compu a ional sys em,” we impose he ollowing
axioms on he abo e da a.
3
3.2 Axiom Sys em
Axiom 1 (Fini e In o ma ion Densi y).The e exis s a local s uc u e GX= (X, EX)
such ha o any ini e e ex se R⊂X, he se o con igu a ions adjacen o R,
N(R) = {x∈X:∃y∈R, (x, y)∈EXo (y, x)∈EX}
sa is ies |N(R)|<∞.
Addi ionally, o each x∈X, he se o “in e nal s a es” locally ele an o xis also
ini e (ensu ed by encoding in conc e e models).
Axiom 2 (Local Upda e).Fo any x∈X, he one-s ep eachable se
T(x) = {y∈X: (x, y)∈T}
is ini e, and he e exis s a ini e adius (independen o x) such ha he de e mina ion
o T(x) depends only on he in o ma ion in a neighbo hood o adius a ound xin GX.
Axiom 3 (Gene alized Re e sibili y).The e exis s a ela ion T−1⊂X×Xsuch ha
o any x∈X,
T−1(x) = {y: (y, x)∈T}
is ini e, and when es ic ed o a “physically ele an ” con igu a ion subse Xphys ⊂X,T
and T−1a e mu ually in e se unc ion g aphs on Xphys (i.e., ime e olu ion is bijec i e).
Axiom 4 (Addi i i y and Posi i i y o Cos ).Fo any (x, y)∈T, we ha e C(x, y)∈
(0,∞); i (x, y)/∈T, de ine C(x, y) = ∞.
Fo any ini e pa h γ= (x0, x1, . . . , xn), de ine
C(γ) =
n−1
X
k=0
C(xk, xk+1)
Then C(γ) depends only on Tand C, and sa is ies he iangle inequali y o pa h con-
ca ena ion.
Axiom 5 (Mono onici y o In o ma ion Quali y).The e exis s a ask amily Q(e.g.,
decision p oblems, unc ion compu a ion, o measu emen asks) such ha o each ask
Q∈ Q, he e exis s an in o ma ion quali y unc ion IQ:X→Rsa is ying: i a pa h
γsuppo s compu a ion o ask Q, hen he expec ed in o ma ion quali y along γis
non-dec easing; i.e., o ypical pa hs x0→x1→ · · · → xn,
E[IQ(xk+1)] ≥E[IQ(xk)]
In mos conc e e cases, we can ix a single ask (e.g., simula ing a ixed ex e nal
sys em) and omi he subsc ip Q, whe e Icha ac e izes in o ma ion p oximi y ela i e
o some “ ue s a e” o a ge dis ibu ion.
3.3 Pa hs, Complexi y, and Reachable Domains
Unde he abo e axioms, we ob ain he ollowing na u al de ini ions.
4
De ini ion 3.2 (Pa h and Complexi y).In a compu a ional uni e se Ucomp, a pa h om x
o yis a ini e sequence γ= (x0, x1, . . . , xn) sa is ying x0=x,xn=y, and (xk, xk+1)∈T
o all 0 ≤k < n.
The cos o a pa h is
C(γ) =
n−1
X
k=0
C(xk, xk+1)
Among all pa hs connec ing xand y, de ine he dis ance
d(x, y) = in
γ:x→y
C(γ)
called he complexi y dis ance om x o y.
P oposi ion 3.3. Unde Axioms A2 and A4, i o any x, y ∈X he e exis s a leas
one ini e pa h connec ing hem, hen dde ines a gene alized me ic on X(possibly aking
alue ∞) sa is ying:
1. d(x, x)=0;
2. d(x, y) = d(y, x)i Tis bijec i e on Xphys;
3. d(x, z)≤d(x, y) + d(y, z).
The de ailed p oo is in Appendix A.1.
De ini ion 3.4 (Reachable Domain and Complexi y Ho izon).Fo a gi en ini ial con-
igu a ion x0∈Xand esou ce budge T > 0, de ine he eachable domain
BT(x0) = {x∈X:d(x0, x)≤T}
I he e exis s x∗∈Xand cons an T∗such ha o all T < T∗,x∗/∈BT(x0), while
o all T > T∗,x∗∈BT(x0), hen T∗is called he complexi y h eshold om x0 o x∗.
Mo e gene ally, opological ansi ions in he bounda y o he eachable domain amily
{BT(x0)}T >0as a unc ion o Tcha ac e ize he “ho izons” o complexi y.
4 Embedding Classical Tu ing Machines and Cellu-
la Au oma a
This sec ion demons a es ha bo h classical Tu ing machines and cellula au oma a can
be iewed as special cases o compu a ional uni e se objec s, hus being inco po a ed
in o he Ucomp sys em.
4.1 Tu ing Machine Uni e se
Recall he de ini ion o a classical de e minis ic Tu ing machine:
De ini ion 4.1 (De e minis ic Tu ing Machine).A single- ape de e minis ic Tu ing ma-
chine is a 5- uple M= (Q, Σ,Γ, δ, q0), whe e:
1. Qis he ini e s a e se ;
5
2. Σ ⊂Γ is he inpu alphabe , Γ is he ape symbol alphabe con aining he blank
symbol;
3. δ:Q×Γ→Q×Γ× {−1,0,+1}is he ansi ion unc ion;
4. q0∈Qis he ini ial s a e.
We encode he “global con igu a ion” o a Tu ing machine un as a combina ion o
he con en s o a bi-in ini e ape, head posi ion, and cu en s a e.
De ini ion 4.2 (Con igu a ion Space o Tu ing Machine Uni e se).Le Zdeno e in ege
posi ions on he ape. De ine he con igu a ion space
XM=Q×ΓZ×Z
whe e a con igu a ion x= (q, (ai)i∈Z, p) ep esen s: he machine is in s a e q, he symbol
a ape posi ion iis ai, and he head is a posi ion p.
De ine he one-s ep ansi ion ela ion TM⊂XM×XMas: (x, y)∈TMi and only i
yis he con igu a ion ob ained by applying δonce a con igu a ion x. Le he single-s ep
cos be CM(x, y) = 1 i (x, y)∈TM, o he wise ∞.
Le IMbe he decision co ec ness in o ma ion ela i e o a gi en inpu and ask (e.g.,
a 0–1 alue o nega i e dis ance o a ge ou pu ).
P oposi ion 4.3. Fo any de e minis ic Tu ing machine M, he quad uple
Ucomp(M) = (XM,TM,CM,IM)
sa is ies Axioms A1–A5, hus is a compu a ional uni e se objec .
P oo ske ch: A1 is gua an eed by he local s uc u e o XMand ini e ape alphabe ;
A2 by he locali y o δ; A3 holds on he subse o “physically eachable con igu a ions”
(i.e., ajec o ies ac ually a e sed by he Tu ing machine and hei e e se ajec o ies);
A4 is e iden om CM≡1; A5 is ensu ed by mono onic design unde ask de ini ions (e.g.,
only eaching maximum in o ma ion alue a accep ing con igu a ions). See Appendix
A.2 o de ails.
4.2 Classical Cellula Au oma on Uni e se
De ini ion 4.4 (Classical Cellula Au oma on).Le Λ be a coun able la ice poin se
(e.g., Zd), Sa ini e s a e se . A cellula au oma on is a local upda e ule F:SΛ→SΛ,
whe e he e exis s a ini e neighbo hood N ⊂ Λ and local ule :SN→Ssuch ha
(F(c))i= ((c)i+N)
o all i∈Λ.
De ine he con igu a ion space XCA =SΛ, one-s ep ansi ion ela ion TCA ={(c, F(c)) :
c∈XCA}, single-s ep cos CCA(c, F(c)) = 1, o he s ∞. The in o ma ion quali y unc ion
ICA is de ined acco ding o asks.
P oposi ion 4.5. Fo any classical cellula au oma on F, he quad uple
Ucomp(F)=(XCA,TCA,CCA,ICA)
is a compu a ional uni e se objec .
A1–A2 come om locali y and ini e s a es; A3 s ic ly holds o e e sible cellula
au oma a, and o non- e e sible cases can be handled h ough s a e space ex ension o
subspace es ic ion; de ailed discussion in Appendix A.3.
6
5 Embedding Re e sible Quan um Cellula Au oma a
To inco po a e quan um uni e se models in o he same amewo k, we conside he ab-
s ac o m o e e sible QCA.
5.1 Basic De ini ion o QCA
De ini ion 5.1 (Re e sible Quan um Cellula Au oma on).Le Λ be a coun able la ice
poin se . Fo each i∈Λ, assign a ini e-dimensional local Hilbe space Hi. The global
Hilbe space is
H=O
i∈Λ
Hi
A e e sible QCA is a uni a y ope a o U:H → H sa is ying:
1. Locali y: Fo any bounded egion R⊂Λ, he e exis s a ini e expansion R′⊃R
such ha U∗A(R)U⊂ A(R′), whe e A(R) is he local ope a o algeb a suppo ed
on R;
2. T ansla ion symme y (op ional): Fo all ansla ions τ: Λ →Λ, Ucommu es wi h
he co esponding ansla ion ope a o .
To i he disc e e amewo k, we iew he se o basis s a es o Hin a ixed o hono -
mal basis as he con igu a ion se .
De ini ion 5.2 (Con igu a ion and Upda e o QCA Uni e se).Choose an o hono mal
basis {|s⟩:s∈Si} o each Hi. Le
XQCA =Y
i∈Λ
Si
be he se o all basis s a e labels.
Fo any x∈XQCA, deno e he co esponding basis ec o as |x⟩. De ine he one-s ep
ela ion TQCA ⊂XQCA ×XQCA as:
(x, y)∈TQCA i and only i ⟨y|U|x⟩ = 0
The single-s ep cos CQCA(x, y) is aken as a cons an co esponding o he single-
s ep physical implemen a ion ime o Uo a weigh ed alue depending on equency. The
in o ma ion quali y unc ion IQCA is de ined acco ding o he obse a ion ask o in e es
(e.g., classical pos -p ocessing o some measu emen esul ).
5.2 Axioms Sa is ied by QCA Uni e se
P oposi ion 5.3. Unde he assump ions o locali y and ini e-dimensional Hilbe space,
Ucomp(U)=(XQCA,TQCA,CQCA,IQCA)
sa is ies Axioms A1–A5.
Key p oo poin s:
Fini e in o ma ion densi y comes om he ini e dimension o each Hiand locali y;
7
Fini eness o he one-s ep eachable se is gi en by Ubeing a local linea combina-
ion;
In e se e olu ion is p o ided by U∗;
Posi i i y o single-s ep cos is gua an eed by he posi i i y o ac ual physical im-
plemen a ion ime;
Mono onici y o in o ma ion quali y can be p o ed ia ela i e en opy unc ions in
he Heisenbe g pic u e.
De ailed a gumen s in Appendix A.4.
6 Uni ied Time Scale and Ini ial Cons uc ion o Com-
plexi y Geome y
While his pape ocuses on disc e e axioms, he uni ied ime scale is he key b idge o
subsequen “complexi y geome y” and “physical-compu a ional uni e se equi alence.”
This sec ion p o ides an ini ial s uc u e: how o abs ac a geome ic dis ance compa ible
wi h physical ime scales om he single-s ep cos C.
6.1 Consis ency o Single-S ep Cos and Time Scale
Assume he e exis s a physical sca e ing p ocess whose equency- esol ed ime scale den-
si y is κ(ω) (e.g., de ined by sca e ing phase de i a i e, spec al shi unc ion de i a i e,
o g oup delay ace). We conside ha he single-s ep cos C(x, y) in he compu a ional
uni e se is a combina ion o se e al such basic physical p ocesses, wi h implemen a ion
ime cos w i able as
C(x, y) = ZΩ(x,y)
κ(ω) dµx,y(ω)
whe e Ω(x, y) is he se o ac i a ed equency bands in he co esponding physical p o-
cess, and µx,y is he co esponding spec al measu e. Thus, he pa h cos
C(γ) = X
k
C(xk, xk+1)
can be app oxima ely iewed as disc e e sampling o some con inuous ime in eg al, ul i-
ma ely inducing a “complexi y dis ance consis en wi h physical ime scale” d(x, y).
6.2 Complexi y Geome y o Con igu a ion G aph
Unde Axioms A1–A4, we can iew (X, T,C) as a weigh ed g aph and conside i s ge-
ome iza ion in ce ain limi s.
De ini ion 6.1 (Complexi y G aph).The complexi y g aph o a compu a ional uni e se
is a weigh ed di ec ed g aph Gcomp = (X, T,C), wi h edge weigh s C.
In some cases (e.g., when con inuous con ol pa ame e s exis and local ules app oach
con inuous ans o ma ions), h ough G omo –Hausdo limi s o spec al analysis o
g aph Laplacians, one can ob ain a con inuous mani old Mwi h me ic Gsuch ha
8
sho es pa h dis ances on he g aph con e ge o geodesic dis ances on he mani old
a app op ia e scales. This p ocess cons i u es he b idge om disc e e complexi y o
con inuous complexi y geome y.
P oposi ion 6.2 (Con inuous Limi o G aph Me ic, Schema ic).Le {U(h)
comp}be a
amily o compu a ional uni e ses co esponding o complexi y g aphs G(h)
comp, whe e “mesh
size” h→0. I he e exis s a mani old Mwi h me ic Gsuch ha (X(h), d(h))con e ges
o (M, dG)in he G omo –Hausdo sense, hen disc e e complexi y can be iewed a
la ge scales as “ ime complexi y” gi en by geodesic dis ance o G.
This p oposi ion is schema ic; a p ecise e sion equi es addi ional echnical assump-
ions; see Appendix B.1 o discussion.
7 Simula ion Mo phisms and he Ca ego y CompUni
To compa e di e en compu a ional uni e ses, we in oduce he concep o simula ion
mo phisms.
7.1 De ini ion o Simula ion Mapping
De ini ion 7.1 (Simula ion Mapping).Le Ucomp = (X, T,C,I), U′
comp = (X′,T′,C′,I′)
be wo compu a ional uni e ses. I he e exis s a map :X→X′and cons an s α, β > 0
such ha :
1. S ep p ese a ion: I (x, y)∈T, hen ( (x), (y)) ∈T′;
2. Cos con ol: Fo any pa h γ:x→y, he e exis s γ′: (x)→ (y) such ha
C′(γ′)≤αC(γ) + β
3. In o ma ion ideli y: The e exis s a mono one unc ion Φ : R→Rsuch ha o all
x∈X,
I(x)≤Φ(I′( (x)))
hen is called a simula ion mapping om Ucomp o U′
comp, deno ed :Ucomp ⇝U′
comp.
I is in e ible on i s image ( he e exis s g:X′→Xsuch ha g◦ and ◦ga e
homo opic o iden i y on ele an subse s), and α, β a e wi hin accep able complexi y
scaling anges, hen Ucomp and U′
comp a e called equi alen in complexi y sense.
7.2 Ca ego y S uc u e
P oposi ion 7.2. Taking compu a ional uni e se objec s as objec s and simula ion map-
pings as mo phisms, we ob ain a ca ego y CompUni :
1. Fo any Ucomp, he iden i y map idX:X→Xis a simula ion mapping;
2. I :Ucomp ⇝U′
comp and g:U′
comp ⇝U′′
comp a e simula ion mappings, hen he
composi e g◦ is also a simula ion mapping;
3. Composi ion o simula ion mappings sa is ies associa i i y.
9
This pape p o ides basic axioma ic sys em o compu a ional uni e se, embedding o
classical and quan um models, and p o o ype cons uc ion o simula ion ca ego y s uc-
u e, laying a disc e e and igo ous ounda ion o subsequen complexi y geome y, in-
o ma ion geome y, and uni ica ion wi h physical uni e se.
16
