Theo e ical Compu e Science 972 (2023) 114077
Con en s lis s a ailable a ScienceDi ec
Theo e ical Compu e Science
jou nal homepage: www.else ie .com/loca e/ cs
Gene a ing, compu ing and ecognizing wi h i us machines✩
An onio Ramí ez-de-A ellanoa,b, Da id O ellana-Ma ína,b,∗,
Ma io J. Pé ez-Jiméneza,b
aResea ch G oup on Na u al Compu ing, Depa men o Compu e Science and A ificial In elligence, Uni e sidad de Se illa, A da. Reina
Me cedes s/n, 41012, Se illa, Spain
bSCORE Labo a o y, I3US, Uni e sidad de Se illa, A da. Reina Me cedes s/n, 41012, Se illa, Spain
a i c l e i n o a b s a c
A icle his o y:
Recei ed 3 Feb ua y 2023
Recei ed in e ised o m 11 July 2023
Accep ed 14 July 2023
A ailable online 20 July 2023
Keywo ds:
Na u al compu ing
Vi us machines
Func ions compu ing
Fini e se s
Na u al compu ing is a esea ch a ea o compu e science whe e di e en models o
compu a ion a ise om he inspi a ion o eal-li e na u al p ocesses. In pa icula , i us
machines a e de ices inspi ed by he ansmission o i uses be ween di e en hos s, and
how hey eplica e in he o ganism. This pa adigm p o ides de ices ha can be seen
as a ne wo k o hos s whe e he communica ion be ween hem is con olled by a se
o ins uc ions ha lead o he ansmission o i uses. Vi us machines can be seen as
gene a ing de ices, compu ing de ices and ecognizing de ices, depending on he possible
inpu and he ou pu o he sys ems. In his wo k, we p esen some machines gene a ing
basic se s, compu ing basic unc ions and we p esen ecognize i us machines, capable o
sol ing decision p oblems in o de o c ea e a new complexi y heo y pa adigm wi h i us
machines.
©2023 The Au ho s. Published by Else ie B.V. This is an open access a icle unde he
CC BY license (h p://c ea i ecommons .o g /licenses /by /4 .0/).
1. In oduc ion
In he a ea o Na u al Compu ing, se e al di e en compu ing pa adigms ha e a ised inspi ed by some physical/biological
eal-li e p ocesses. This is he case in DNA compu ing [1], memb ane compu ing [2], a ificial neu al ne wo ks [3]and
cellula au oma a [4], among o he s. A compu ing pa adigm is a amewo k whe e di e en models o compu a ion wi h
common cha ac e is ics coexis . F om he basic model [5] o a en ion ne wo ks [6], se e al ypes ha e been defined in he
amewo k o neu al ne wo ks [7–13], as new equisi es a e imposed by new p oblems. They ha e been demons a ed o
be e y good models in a wide spec um o applica ions [14–17]. In he amewo k o memb ane compu ing, h ee main
a ian s we e defined depending o hei s uc u e: cell-like memb ane sys ems [2], issue-like memb ane sys ems [18]and
neu al-like memb ane sys ems [19], al hough se e al o he classes o P sys ems ha e been defined [20–26]. These models
ha e been applied o e y di e en fields [27–31].
In 2015, he pape [32]p esen ed a new model o compu a ion inspi ed by he way i uses sp ead be ween hos s
and eplica e hei gene ic code by “ icking” he hos en i ies. Then, some pape s ela ed wi h he uni e sali y o hese
de ices ha e been published [33–35]. La ely, he a ea has been e isi ed and some new esul s ha e been ob ained [36].
In his wo k, we ocus on he design and o mal e ifica ion o i us machines sol ing “simple” p oblems, being easy
✩This a icle belongs o Sec ion C: Theo y o na u al compu ing, Edi ed by Lila Ka i.
*Co esponding au ho a : Resea ch G oup on Na u al Compu ing, Depa men o Compu e Science and A ificial In elligence, Uni e sidad de Se illa,
A da. Reina Me cedes s/n, 41012, Se illa, Spain.
E-mail add esses: a ami ezdea [email p o ec ed] (A. Ramí ez-de-A ellano), do [email p o ec ed] (D. O ellana-Ma ín), [email p o ec ed] (M.J. Pé ez-Jiménez).
h ps://doi.o g/10.1016/j. cs.2023.114077
0304-3975/©2023 The Au ho s. Published by Else ie B.V. This is an open access a icle unde he CC BY license (h p://
c ea i ecommons .o g /licenses /by /4 .0/).
A. Ramí ez-de-A ellano, D. O ellana-Ma ín and M.J. Pé ez-Jiménez Theo e ical Compu e Science 972 (2023) 114077
o p o e and unde s and he co esponding solu ions. This pape is an ex ension o he pape “Gene a ing, compu ing and
ecognizing wi h i us machines” p esen ed in he 23 d Con e ence on Memb ane Compu ing loca ed in T ies e, I aly [37]. In
he p esen wo k, new machines gene a ing and ecognizing fini e se s a e in oduced. In pa icula , he machines p esen ed
in Sec ion 3.3 ha gene a e fini e se s and he machines p esen ed in Sec ion 5.3 ha ecognize fini e se s.
The wo k is o ganized as ollows: In Sec ion 2, he defini ion o i us machines is gi en, and bo h he syn ax and
seman ics o hem a e de ailed. Sec ion 3is de o ed o he design and e ifica ion o ou i us machines in gene a ing
mode. In he nex sec ion, some i us machines compu ing di e en unc ions a e in oduced, gi ing an explici e ifica ion
o hei beha io . In Sec ion 5, ecognize i us machines a e in oduced in addi ion o a compu a ional complexi y class
wi h i us machines and h ee i us machines sol ing decision p oblems a e explained. The pape finishes wi h some
conclusions and open esea ch lines in he a ea.
2. Vi us machines
Vi us machines we e in oduced in [32]as uni e sal de ices capable o simula ing egis e machines i no es ic ions a e
imposed, and simple languages can be ecognized i he e a e es ic ions in he numbe o hos s, ins uc ions o i uses
p esen in he machines. Now we ecall he defini ion o a i us machine.
Defini ion 1. A i us machine o deg ee (p, q), p, q ≥1is a uple
=(,H,I,DH,DI,GC,n1,...,np,i1,hou ),
whe e:
1.  ={ }is he single on alphabe ;
2. H={h1, ..., hp}and I={i1, ..., iq}a e o de ed se s such ha /∈H∪I, H∩I=∅ and hou ∈Ho hou =h0;
3. DH=(H∪{hou }, EH, wH)is a weigh ed di ec ed g aph, whe e EH⊆H×(H∪{hou }), (h, h) /∈EH o each h ∈H,
ou −deg ee(hou ) =0 and wHis a mapping om EHon o N {0};
4. DI=(I, EI, wI)is a weigh ed di ec ed g aph, whe e EI⊆I×I, wIis a mapping om EIon o N {0}and he ou -
deg ee o each node is less han o equal o 2;
5. GC=(VC, EC)is an undi ec ed bipa i e g aph, wi h VC=I∪EHbeing {I, EH} he pa i ion associa ed wi h i : e e y
edge connec s an elemen om Iwi h, a mos , one a c om EH;
6. nj∈N(1 ≤j ≤p).
A i us machine (VM, o sho )
=(,H,I,DH,DI,GC,n1,...,np,i1,hou )
o deg ee (p, q), can be iewed as an o de ed se o phos s labelled by elemen s om H, whe e each hos hjini ially
con ains nj i uses, and an o de ed se o q con ol ins uc ion uni s labelled by elemen s om I. hou ep esen s he ou pu
egion, being a hos i hou ∈H, and he en i onmen o he machine i hou =h0. A cs om he di ec ed g aph DH ep esen
ansmission channels h ough which i uses can ansmi om one hos hs(di e en om hou ) o ano he di e en hos
hso o he en i onmen . The en i onmen plays a passi e ole in i us machines, in he sense ha i can only ecei e
i uses om he de ice, bu canno ake hem back o i . A cs om he di ec ed g aph DI ep esen ins uc ion ans e
pa hs. Finally, he undi ec ed bipa i e g aph GC ep esen s he ins uc ion-channel ne wo k by which an edge (ij, (hs, hs))
indica es a con ol ela ionship be ween he ins uc ion ijand he channel (hs, hs).
G aphically, a i us machine o deg ee (4, 6)can be depic ed as a he e ogeneous ne wo k consis ing o h ee g aphs, as
illus a ed in Fig. 1. Each hos is ep esen ed as a ec angle and each ins uc ion is ep esen ed by a ci cle. A ows be ween
hos s ep esen ansmission channels, a ows be ween ins uc ions ep esen ins uc ion ans e pa hs and edges be ween
ins uc ions and channels ep esen ins uc ion-channel connec ions. The weigh s o he edges a e ep esen ed as posi i e
numbe s besides he edge (i he weigh is 1, hen i is no ep esen ed).
In he ollowing pa ag aphs, he seman ics o a i us machine will be desc ibed. Fi s , we define he ins an aneous de-
sc ip ion o a configu a ion C a an ins an o a i us machine by a uple (a1, ..., ap, u, a0), whe e a0, a1, ..., ap∈Nand
u ∈I∪{#}, whe e # /∈H∪{h0} ∪Iis an objec ha cha ac e izes a hal ing configu a ion. The meaning o C is he ollowing:
a an ins an , each hos hjcon ains exac ly aj i uses, he en i onmen con ains exac ly a0 i uses and, i u ∈I, hen he
ins uc ion uwill be ac i a ed a s ep +1, o he wise, hen no ins uc ion will be ac i a ed and he machine will hal . The
ini ial configu a ion o a i us machine  =(, H, I, DH, DI, GC, n1, ..., np, i1, hou )is C0=(n1, ..., np, i1, 0). A configu a-
ion C yields configu a ion C +1in one ansi ion s ep o compu a ion s ep i we can pass om C o C +1(and we deno e i
by C ⇒C +1) in he ollowing o m.
1. Fi s , gi en ha C is a non-hal ing configu a ion, we ha e ha u ∈I. Then, he con ol ins uc ion uni uis ac i a ed.
2. I uis a ached o a channel (hs, hs), hen he channel will be opened and:
•I as≥1 hen only one i us is consumed om hos hsand ws,scopies o a e p oduced in he egion hs.
2
A. Ramí ez-de-A ellano, D. O ellana-Ma ín and M.J. Pé ez-Jiménez Theo e ical Compu e Science 972 (2023) 114077
Fig. 1. Vi us machine o o de (4,6).
•I as=0 hen no i uses a e consumed om hos hsand no i uses a e p oduced in he egion hs.
3. I uis no a ached o any channel hen he e is no ansmission o i uses.
4. The nex ins uc ion o be execu ed is ob ained as ollows:
•I ou −deg ee(u) =2 hen he e a e wo di e en ins uc ions uand u such ha (u, u), (u, u) ∈EI(wi h weigh s
wu,uand wu,u , espec i ely).
–I he ins uc ion uis a ached o a channel (hs, hs):
∗I as≥1 hen he nex ins uc ion co esponds o he highes weigh pa h (max({wu,u, wu,u })).
∗I as=0 hen he nex ins uc ion co esponds o he lowes weigh pa h (min({wu,u, wu,u })).
∗In ei he case, i wu,u=wu,u , he nex ins uc ion is selec ed in a non-de e minis ic way.
–I ins uc ion uis no a ached o a channel, hen he nex ins uc ion is selec ed in a non-de e minis ic way.
•I ou −deg ee(u) =1 hen he sys em beha es de e minis ically and uis he nex ins uc ion ha e ifies (u, u) ∈
EI.
•I ou −deg ee(u) =0 hen u =# and C +1is a hal ing configu a ion.
A compu a ion C=(C0, C1, ...) o a i us machine is a (possibly infini e) sequence o configu a ions such ha C0is he
ini ial configu a ion o and o each ∈N, C ⇒C +1. A compu a ion C=(C0, C1, ..., Ck)is called a hal ing compu a ion
i he e exis s a ksuch ha Ckis a hal ing configu a ion; ha is, u =#.
An in a ian is a o mula φ ha holds h ough all he compu a ion o a i us machine. Le M=(, H, I, DH, DI, GC, n1,
...,
np, i1, hou )be a i us machine o deg ee (p, q). The in a ian φ≡C =(a1, , ..., ap, , u , a0, )holds i : (a) a configu a-
ion C o he i us machine , he cu en ins uc ion is u ; (b) he con en s o he hos i ∈{1, ..., p}a configu a ion C is
ai, ; and (c) he con en s o he en i onmen a configu a ion C is a0, . This o mula can con ain pa ame e s ha can lead
o use ul o mulas o di e en configu a ions. Fo ins ance, he in a ian φ(k) =Ck=(1, 0, i1, k), o 0 ≤k ≤9, indica es
ha he en i onmen mus con ain exac ly k i uses in he configu a ion Ckdu ing he fi s 10 configu a ions. This ype o
o mula is use ul o p o e he co ec ness o de ices such as i us machines.
In his wo k, i us machines a e used o gene a e se s o numbe s, o compu e unc ions o e na u al numbe s and
o sol e decision p oblems. Thus, di e en defini ions mus be in oduced o know wha is o gene a e se s, o compu e
unc ions and o sol e (decision) p oblems wi h i us machines.
Defini ion 2. Le Fbe a (fini e o infini e) se o na u al numbe s, and le |F|be he ca dinal o F(i.e. he numbe o
elemen s o F). We say ha Fis gene a ed by a i us machine i he ollowing holds:
•I Fis a fini e se , hen he i us machine has exac ly |F|compu a ions. Each one o he compu a ions gene a e
exac ly one elemen om F, and each elemen o Fis gene a ed by exac ly one compu a ion; ha is, an elemen k ∈F
is gene a ed by means o a compu a ion o i and only i he e exis s a compu a ion o such ha he e exis s k
i uses in he egion hou a he las s ep o he compu a ion.
•I Fis an infini e se , hen he i us machine has infini e compu a ions, and one o hem is infini e. Each one
o he fini e compu a ions gene a e exac ly one elemen om F, and each elemen o Fis gene a ed by exac ly one
compu a ion; ha is, an elemen k ∈Fis gene a ed by means o a compu a ion o i and only i he e exis s a
3
A. Ramí ez-de-A ellano, D. O ellana-Ma ín and M.J. Pé ez-Jiménez Theo e ical Compu e Science 972 (2023) 114077
compu a ion o such ha he e exis s k i uses in he egion hou a he las s ep o he compu a ion, and he e
exis s a compu a ion o  ha ne e hal s.
Defini ion 3. Le :Nk→Nbe a unc ion. We say ha he unc ion is compu able by a i us machine wi h kinpu
hos s i he ollowing condi ions a e e ified:
•Fo each ins ance (x1, ..., xk) ∈Nk, he i us machine will ha e kinpu hos s h 1, ..., h k∈H , and in he ini ial
configu a ion, he hos h iwill con ain exac ly n i+xi i uses.
•Fo each ins ance (x1, ..., xk) ∈Nk, he i us machine will ha e he ollowing beha io :
–I (x1, ..., xk) =y, hen he i us machine will hal and ha e exac ly y i uses in he egion hou in he las s ep
o he compu a ion.
–I (x1, ..., xk)is no defined, hen he i us machine will no hal .
Defini ion 4. Le X=(IX, θX)be a decision p oblem, whe e IXis a language o e a fini e alphabe (ins ances) and θXis
a o al boolean unc ion o e IX(p edica e). We say ha he decision p oblem is sol able in polynomial ime by a amily
 ={(n) | n ∈N}o ecognize i us machines i he ollowing condi ions a e e ified:
•The amily is polynomial uni o m by Tu ing Machines.
•Exis s a pai (cod, s)o unc ions o e IX(compu ed in polynomial ime) such ha :
–Fo each ins ance u ∈IX, s(u)is a na u al numbe and cod(u)is a alid inpu o he ecognize i us machine (s(u)).
–The amily is polynomial bounded wi h espec o (X, cod, s), i.e. ∃ppolynomial such ha ∀u ∈IX, (s(u)) +cod(u)
hal s in p(s(u)) s eps.
–The amily is sound wi h espec o (X, cod, s), ∀u ∈IX. Tha is, i he e exis s an accep ing compu a ion o (s(u)) +
cod(u), hen θX(u) =1.
–The amily is comple e wi h espec o (X, cod, s), ∀u ∈IX. Tha is, i θX=1, hen e e y compu a ion o (s(u)) +
cod(u)is an accep ing compu a ion.
Defini ion 5. We say ha a decision p oblem X=(IX, θX)is sol able in polynomial ime by a amily  ={(n) | n ∈N}o
i us machines wi h inpu , in a de e minis ic and uni o m way (we deno e i by X∈PVM), i he e exis s k ∈Nsuch ha
Xis sol able by he amily in ime bounded by a polynomial, in a de e minis ic and uni o m way.
3. Gene a ing i us machines
In [34], he uni e sali y o i us machines is p o ed by showing hei capaci y o gene a e Diophan ine se s. By using he
non-de e minis ic na u e o hese de ices, each compu a ion is able o gene a e a di e en numbe , ob aining in his sense
a de ice capable o gene a ing an infini e se . In his sec ion, we show wo simple cases o gene a ing machines ( ollowing
he Defini ion 2) wi h some in a ian s ha show he co ec ness o he co esponding i us machines and gene a ing fini e
se s is also s udied. Le us ecall some no a ion:
Fo each p, q, n ≥1, we deno e by NVM(p, q, n)[34] he amily o all subse s o Ngene a ed by i us machines wi h
a mos phos s, qins uc ions and all hos s ha ing a mos na any ins an o each compu a ion. I one o he pa ame e s
p, q, nis no bounded, hen i is eplaced wi h ∗.
3.1. Gene a ing e en numbe s
Le  =(, H, I, DH, DI, GC, n1, n2, i1, hou ), whe e:
1.  ={ };
2. H={h1, h2};
3. I={i1, i2, i3, i4};
4. DH={H∪{hou }, {(h1, h2), (h2, h1), (h2, hou )}, wH}, whe e wH((h1, h2)) =1, wH((h2, h1)) =wH((h2, hou )) =2;
5. DI={I, {(i1, i2), (i1, i3), (i2, i1), (i2, i2), (i3, i3), (i3, i4)}, wI}, whe e wI((i1, i2)) =wI((i1, i3)) =wI((i2, i1)) =
wI((i3, i4)) =1, wI((i2, i2)) =wI((i3, i3)) =2;
6. GC=(I∪EH, {(i1, (h2, h1)), (i2, (h1, h2)), (i3, (h2, hou ))});
7. n1=0, n2=1; and
8. hou =h0.
A isual ep esen a ion o his i us machine can be ound in Fig. 2. Le us p o e ha o each n ∈N, he e exis s a
compu a ion o such ha p oducing 2n i uses in he en i onmen in he hal ing configu a ion, and he e exis s a non-
hal ing compu a ion. Le 2nbe he numbe gene a ed in he compu a ion C=(C0, C1, ...) The ollowing in a ian s hold in
his machine:
4
A. Ramí ez-de-A ellano, D. O ellana-Ma ín and M.J. Pé ez-Jiménez Theo e ical Compu e Science 972 (2023) 114077
Fig. 2. Vi us machine gene a ing he se {2n:n∈N}.
φ(k)≡C4k=(0,n+1,i1,0), o 0 ≤k≤n
φ(k)≡C4k+1=(2,n,i2,0), o 0 ≤k≤n
When he non-de e minis ic s ep om ins uc ion i1goes o i3ins ead o i2, hen he machine s a s sending i uses o he
en i onmen , and i will ake exac ly ns eps, hen ins uc ion i4will be selec ed and he e o e he sys em will hal in he
ollowing s ep, hus he ollowing in a ian s hold:
φ ≡C4n+1=(2,n,i3,0)
φ ≡C4n+n+2=(2,0,i4,2n)
φ(IV)≡C4n+n+3=(2,0,#,2n)
F om i1, anon-de e minis ic s ep selec s he nex ins uc ion om {i2, i3}. I is easy o see ha he e exis s an infini e
compu a ion aking in o accoun he ollowing configu a ions:
C0=(0,1,i1,0)
C1=(2,0,i2,0)
C2=(1,1,i2,0)
C3=(0,2,i2,0)
C4=(0,2,i1,0)
...
C8=(0,3,i1,0)
...
When making he non-de e minis ic decision, he ins uc ion selec ed in he s ep 4k +1can be always i2, hus making he
machine non-hal ing.
3.2. Gene a ing powe s o wo
Le  =(, H, I, DH, DI, GC, n1, n2, i1, hou ), whe e:
1.  ={ };
2. H={h1, h2};
3. I={i1, i2, i3, i4, i5, i6, i7};
5

A. Ramí ez-de-A ellano, D. O ellana-Ma ín and M.J. Pé ez-Jiménez Theo e ical Compu e Science 972 (2023) 114077
Fig. 3. Vi us machine gene a ing he se {2n:n∈N}.
4. DH={H∪{hou }, {(h1, h2), (h2, h1), (h1, hou ), (h2, hou )}, wH}, whe e wH((h1, h2)) =wH((h2, h1)) =2, wH((h1, hou )) =
wH((h2, hou )) =1;
5. DI={I, {(i1, i2), (i1, i5), (i2, i2), (i2, i3), (i3, i4), (i3, i6), (i4, i4), (i4, i1), (i5, i5), (i5, i7), (i6, i6), (i6, i7)}, wI}, whe e
wI((i1, i2)) =wI((i1, i5)) =wI((i2, i3)) =wI((i3, i4)) =wI((i3, i6)) =wI((i4, i1)) =wI((i5, i7)) =wI((i6, i7)) =1,
wI((i2, i2)) =wI((i4, i4)) =wI((i5, i5)) =wI((i6, i6)) =2;
6. GC=(I∪EH, {(i2, (h1, h2)), (i4, (h2, h1)), (i5, (h1, hou )), (i6, (h2, hou ))});
7. n1=1, n2=0; and
8. hou =h0.
A isual ep esen a ion o his i us machine can be ound in Fig. 3. Le us p o e ha o each n ∈N, he e exis s a
compu a ion o such ha i p oduces 2n i uses in he en i onmen in he hal ing configu a ion, and he e exis s a non-
hal ing compu a ion. Le 2nbe he numbe gene a ed in he compu a ion C=(C0, C1, ...) Le αk=k
i=02iThe ollowing
in a ian s hold in his machine:
φ≡Cαk+k=(2k,0,i1,0), o 0 ≤k≤n,ke en
φ≡Cαk+k=(2k,0,i3,0), o 0 ≤k≤n,kodd
When he non-de e minis ic s ep om ins uc ion i1( espec i ely, i3) goes o i5( esp., i6) ins ead o i2( espec i ely, i4),
hen he machine s a s sending i uses o he en i onmen , and i will ake exac ly 2n+1s eps, hen ins uc ion i7will
be selec ed and he e o e he sys em will hal in he ollowing s ep, hus he ollowing in a ian s hold:
φ ≡C2n+n+1=(2n,0,i5,0),ne en
φ ≡C2n+n+1=(0,2n,i6,0),nodd
φ(IV)≡C2·2n+n+2=(0,0,i7,2n)
φ(V)≡C2·2n+n+3=(0,0,#,2n)
F om i1( espec i ely, i3), anon-de e minis ic s ep selec s he nex ins uc ion om {i2, i5}( espec i ely, {i4, i6}). I is
easy o see ha he e exis s an infini e compu a ion aking in o accoun he ollowing configu a ions:
6
A. Ramí ez-de-A ellano, D. O ellana-Ma ín and M.J. Pé ez-Jiménez Theo e ical Compu e Science 972 (2023) 114077
Fig. 4. Vi us machine gene a ing he fini e se F.
C0=(1,0,i1,0)C6=(4,0,i4,0)
C1=(1,0,i2,0)C7=(4,0,i1,0)
C2=(0,2,i2,0).
.
.
C3=(0,2,i3,0)C13 =(0,8,i3,0)
C4=(0,2,i4,0).
.
.
C5=(2,1,i4,0)C23 =(16,0,i1,0)
When making he non-de e minis ic decisions, he ins uc ions i5and i6will ne e be selec ed in such a compu a ion, hus
making he machine non-hal ing.
3.3. Gene a ing fini e se s
In his subsec ion, wo di e en ways o gene a ing he fini e se s a e s udied.
Lemma 1 (Hos ). Le F={m1, ..., mk}a o de ed ( om lowe o highe ) fini e se o na u al numbe s g ea e han ze o. Then Fcan
be gene a ed by a i us machine o 1hos , mk+1ins uc ions and mk i uses a each hos a mos .
P oo . Le  =(, H, I, DH, DI, GC, n1, i1, hou ), whe e:
1.  ={ };
2. H={h1};
3. I={i1, ..., imk+1};
4. DH=(H∪{hou }, {(h1, hou )}, wH), whe e wH((h1, hou )) =1;
5. DI=(I, EI={(ia, ia+1) | ia∈I imk+1} ∪{(ib, imk+1) | b ∈F}, wI), whe e wI((id, ie)) =1 ∀(id, ie) ∈EI;
6. GC=(I∪EH, {(i , (h1, hou ))}) ∀i ∈I {imk+1};
7. n1=mk; and
8. hou =h0.
A isual ep esen a ion o his i us machine can be ound in Fig. 4. Le us p o e ha o each mj∈F, he e exis s a
compu a ion o such ha i p oduces mj i uses in he en i onmen in he hal ing configu a ion. Le mj he numbe
gene a ed in he compu a ion C=(C0, C1, ...), he ollowing in a ian holds in his machine:
φ(x)≡Cx=(mk−x,i1+x,x), o 0 ≤x≤mj−1
F om his, φ(mj)is ue and ins uc ion imjis eached; hus he non-de e minis ic s ep selec s imk+1as he nex ins uc-
ion (i mj=mk, he decision is de e minis ic) and he e o e he sys em will hal in he ollowing s ep:
Cmj+2=(mk−mj,#,mj)
I is in e es ing o poin ou ha , since all he connec ions om ij(1 ≤j ≤mk) o imk+1 ulfil he es ic ion j ∈F, he
only elemen s ha can be gene a ed a e he elemen s om F. I we hink o an elemen xgene a ed om he i us machine
ha does no belong o F, we mus hink ha he e mus exis a connec ion om ix o imk+1, and his pa h will only exis
i x ∈F, ha con adic s he p emise o xno belonging o F.
7
A. Ramí ez-de-A ellano, D. O ellana-Ma ín and M.J. Pé ez-Jiménez Theo e ical Compu e Science 972 (2023) 114077
Fig. 5. Vi us machine gene a ing he fini e se F.
Lemma 2 (Vi uses). Le F={m1, ..., mk}an o de ed ( om lowe o highe ) fini e se o k >1na u al numbe s g ea e han ze o.
Then Fcan be gene a ed by a i us machine o k hos s, 2k ins uc ions and 1 i us a each hos a mos .
P oo . Le  =(, H, I, DH, DI, GC, n1, n2, ..., nk, i1, hou ), whe e:
1.  ={ };
2. H={h1, h2, ..., hk};
3. I={i1, ..., i2k};
4. DH=(H∪{hou }, {(hl, hou ) | hl∈H}, wH), whe e wH((hl, hou )) =nl o 1 ≤l ≤k;
5. DI=(I, EI, wI), whe e EI={(i2a, i2k) | a ∈{1, ..., k −1}} ∪{(i2k−1, i2k), (i2(k−1)−1, i2k−2), (i2(k−1)−1, i2k−1)} ∪
{(i2a+1, i2a+2), (i2a+1, i2a+3) | a ∈{0, ..., k −2}}, wI((ij, ij)) =1 ∀(ij, ij) ∈EI;
6. GC=(I∪EH, {(i2k−1, (hk, hou ))} ∪{(i2 , (h , hou )) | ∈{1 ..., k −1}});
7. n1=n2=···=nk=1; and
8. hou =h0.
A isual ep esen a ion o his i us machine can be ound in Fig. 5. Le us p o e ha o each mj∈F, he e exis s a
compu a ion o such ha i p oduces mj i uses in he en i onmen in he hal ing configu a ion. Le mj= mk he numbe
gene a ed in he compu a ion C=(C0, C1, ...), he ollowing in a ian holds in his machine:
φ(x)≡Cx=(1,1,...,1,i2x+1,0), o 0 ≤x≤j−1.
F om his, φ(j −1)is ue and om ins uc ion i2j−1a non-de e minis ic decision is made and goes o i2jwhich is
a ached o he channel (hj, hou )and i2kwill be ac i a ed in he nex s ep, finally, he sys em will hal in ollowing s ep:
C2j+1=(1,1,...,1,0

hos j
,1,...,1,#,mj).
Le us suppose now ha mkis gene a ed, hen he ollowing in a ian holds:
φ(x)≡Cx=(1,1,...,1,i2x+1,0), o 0 ≤x≤k−2.
F om his, φ(k −2)is ue and o m ins uc ion i2k−3a non-de e minis ic decision is made and goes o i2k−1which is
a ached o he channel going om, hos h :mk o he en i onmen . A e ha , i2kwill be ac i a ed so he sys em will hal
in he ollowing s ep:
C2j+1=(1,1,...,1,0,#,mk). 
8
A. Ramí ez-de-A ellano, D. O ellana-Ma ín and M.J. Pé ez-Jiménez Theo e ical Compu e Science 972 (2023) 114077
Fig. 6. Vi us machine compu ing (x)=0.
Fig. 7. Vi us machine compu ing (x)such ha dom( (x)) =∅.
Theo em 1. NFIN⊆NVM(1, ∗, ∗)and NFIN⊆NVM(∗, ∗, 1).
4. Compu ing i us machines
F om now on, since he numbe o elemen s p esen in he i us machines can g ow and he desc ip ion can be edious
o ead, i is easy o depic hem wi h g aphics whe e he ini ial configu a ion is desc ibed (only o he smalle de ices).
Le us ecall ha i1is he ini ial ins uc ion, and hou =h0. We ollow he Defini ion 3 o know wha does i mean o
compu e a unc ion by means o a i us machine. Since we a e using i us machines as compu ing de ices, we mus ha e
inpu o he machine. Le us ecall, om [36], ha a i us machine wi h inpu , o deg ee (p, q, ), p, q, ≥1is a uple
 =(, H, H , I, DH, DI, GC, n1, ..., np, i1, hou ), whe e:
•(, H, I, DH, DI, GC, n1, ..., np, i1, hou )is a i us machine o deg ee (p, q); and
•H ={hj1, ..., hj } ⊆His he o de ed se o inpu hos s and hou /∈H .
The ini ial configu a ion o a i us machine wi h inpu (a1, ..., a ) ∈N is gi en by (n1, ..., nj1+a1, ..., nj +a , ..., np).
We deno e a i us machine wi h inpu (a1, ..., a )by  +(a1, ..., a ). I he e is a single inpu , i can be deno ed by
 +a1.
In he g aphical desc ip ion, inpu hos s will be ma ked wi h a double bo de in he co esponding hos . I mo e han
one hos is an inpu hos , hen hei o de wi h espec o he inpu uple is he alphanume ical o de .
4.1. Ze o unc ion
A isual ep esen a ion o his i us machine can be ound in Fig. 6. I is easy o see ha his machine always hal s
and does no send any i us o he en i onmen . The compu a ion would go om C0=(n, i1, 0) o C1=(n, #, 0), a hal ing
configu a ion, no ma e which is he inpu ha is gi en o he i us machine.
4.2. Emp y unc ion
A isual ep esen a ion o his i us machine can be ound in Fig. 7. I is easy o see ha his machine ne e hal s. The
compu a ion would go om C0=(n, i1, 0) o C1=(n, i2, 0), and hen back o C2=(n, i1, 0), which is equi alen o C0. Thus
he compu a ion ne e hal s.
9