Computer
Science
and
Inf
ormation
T
echnologies
V
ol.
7,
No.
2,
July
2026,
pp.
196
∼
202
ISSN:
2722-3221,
DOI:
10.11591/csit.v7i2.p196-202
❒
196
Complexity
of
nite
state
T
uring
machine
with
other
domain
Rajesh
K
umar
1
,
Anju
J
ain
2
,
Rak
esh
K
umar
3
1
Department
of
Computer
Science
and
Applications,
Chhaju
Ram
Memorial
Jat
Colle
ge,
Hisar
,
India
2
Department
of
Computer
Science,
Go
v
ernment
Colle
ge
Hansi,
Hansi,
India
3
Department
of
Computer
Science
and
Applications,
K
urukshetra
Uni
v
ersity
,
K
urukshetra,
India
Article
Inf
o
Article
history:
Recei
v
ed
Sep
21,
2025
Re
vised
Apr
25,
2026
Accepted
May
16,
2026
K
eyw
ords:
Comple
xity
Finite
state
automata
Non-deterministic
FSA
P
artial
function
T
uring
machine
ABSTRA
CT
In
this
paper
,
the
authors
in
v
estig
ate
and
discussed
the
non-det
erministic
state
comple
xity
of
certain
operations
on
nite
state
T
uring
machine
on
other
domain
which
includes
parti
al
function
and
natural
function
o
v
er
an
alphabet
se
t
Σ
∗
.
It
is
found
that
in
some
boolean
operations
on
said
domains,
the
state
comple
xity
reaches
up
to
upper
bound
O
(
√
n
!)
.
This
result
is
complement
for
the
operation
on
Kleen
star
-free
unary
and
recursi
v
e
languages
a
ccepted
by
the
nite
state
T
uring
machine.
This
is
an
open
access
article
under
the
CC
BY
-SA
license
.
Corresponding
A
uthor:
Rajesh
K
umar
Department
of
Computer
Sciences
and
Applications,
Chhaju
Ram
Memorial
Jat
Colle
ge
Hisar
,
Haryana,
India
Email:
rajtaya@kuk.ac.in
1.
INTR
ODUCTION
The
descripti
v
e
comple
xity
issues
about
operation
problem
for
re
gular
languages
of
nite
state
T
uring
machine
ha
v
e
been
discussed
by
the
authors
in
this
paper
.
The
operation
problem
on
a
language
f
amily
is
dened
in
term
of
total
states
in
relation
to
accepting
state
by
deterministic
nite
state
T
uring
machine.
It
is
well
kno
wn
that
deterministic
and
non-deterministic
nite
state
machines
are
equi
v
alent
in
terms
of
their
computational
po
wer
[1],
[2].
In
terms
of
states,
a
gi
v
en
n-state
NF
A,
one
can
al
w
ays
construct
an
equi
v
alent
DF
A
with
at
most
2
n
state
b
ut
the
space
comple
xity
of
this
ne
wly
constructed
DF
A
will
be
huge.
It
has
been
found
that
in
most
of
the
cases
when
an
operation
is
e
xpensi
v
e
[3]
for
NF
A,
it
is
v
ery
cheap
for
DF
A
and
vice
v
ersa.
In
this
paper
,
the
author
gi
v
es
tw
o
e
xamples:
-
In
the
tw
o
languages
accepted
by
M-
and
N-state
DF
A
in
Figure
1,
after
concatenation
it
has
a
upper
bound
of
m
∗
2
n
−
t
∗
2
n
−
1
states
[4],
where
t
is
the
number
of
nal
states
it
goes
m
+
n
+
1
when
considering
NF
As.
-
When
complement
operation
appl
ied
to
a
language,
a
n-state
NF
A
in
Figure
2
gi
v
es
an
upper
bound
of
2
n
states
[5]
whereas
by
an
n-state
DF
A
results
in
e
xactly
the
same
number
of
states
in
the
complemented
DF
A
and
vice
v
ersa.
J
ournal
homepage:
http://iaesprime
.com/inde
x.php/csit
Evaluation Warning : The document was created with Spire.PDF for Python.
Comput
Sci
Inf
T
echnol
ISSN:
2722-3221
❒
197
q
1
start
q
2
q
3
q
m
1
0
1
0
1
0
1
0
1
0
0
0
Figure
1.
L
1
=
{
(0
,
1)
∗
1
m
|
(0,1)
∈
Σ
}
q
1
start
q
2
q
3
q
m
1
0
1
0
1
0
1
0
1
0
0
0
Figure
2.
L
1
=
{
Σ
∗
−
(0
,
1)
∗
1
m
|
(0
,
1)
∈
Σ
}
2.
TURING
MA
CHINE:
A
ST
AND
ARD
MODEL
The
e
v
olution
of
machine
or
automata
are
as:
i)
nite
memory
(encloded
in
state)
—DF
As/
NF
As;
ii)
unbounded
stack
—NPD
As/DPD
As;
and
iii)
unbound
memory
—TMs.
2.1.
Denition
A
turing
machine:
T=
⟨
Q,
Σ
,
τ
|
{z
}
Σ
⊆
τ
−
{
□
}
,
δ
B
△
,
Q
o
,
Q
F
⊆
Q,
□
|{z}
bl
ank
sy
mbol
⟩
where
δ
B
△
=
⇒
δ
B
:
Q
×
τ
⇀
|{z}
par
tial
f
unction
Q
×
τ
×
{
L,
R
}
△
⊆
f
(
Q
×
τ
)
×
(
Q
×
τ
×
{
L,
R
}
)
.
Figure
3
depicts
the
interaction
between
these
components.
Innite
tape
[6],
[7]
F
S
C
q
[8],
[9]
Figure
3.
F
S
C
q
-
is
the
read/
write
head
of
nite
state
control
whereas
innite
tape-
is
used
for
storing
input,
as
scratch
pad
and
also
(in
the
case
of
T
uring
machine
as
transducers)
for
storing
the
output
2.1.1.
Instantaneous
Description
(ID)
An
instantaneous
description
[10],
[11]
of
a
TM
is
a
sequence
of
the
form
xq
y
where
x,y
∈
τ
∗
such
that
x
̸
=
□
∗
̸
=
y
.
-
There
is
non-blank
symbol
either
to
the
left
of
x
or
to
the
right
of
y
,
-
The
rst
symbol
of
x
and
the
last
symbol
of
y
are
both
non-blank,
-
The
rst
symbol
of
y
is
the
symbol
immediately
under
the
read/write
head,
-
q
is
the
current
state
of
the
FSC.
Comple
xity
of
nite
state
T
uring
mac
hine
with
other
domain
(Rajesh
K
umar)
Evaluation Warning : The document was created with Spire.PDF for Python.
198
❒
ISSN:
2722-3221
An
ID
is
also
called
a
conguration.
A
mo
ve
of
the
TM
from
an
ID
x
1
q
1
y
1
to
another
ID
x
2
q
2
y
2
is
denoted
x
1
q
1
y
1
⊢
x
2
q
2
y
2
where
x
1
=
a
1
....a
k
;
y
1
=
b
1
....b
l
is
possible
pro
vided
one
of
the
follo
wing
holds.
-
δ
(
q
1
,
b
1
)
=
(
q
2
,
c,
R
)
and
x
2
=
a
1
....a
k
c
;
y
2
=
b
2
....b
l
or
-
δ
(
q
1
,
b
1
)
=
(
q
2
,
c,
L
)
and
x
2
=
a
1
....a
k
−
1
;
y
2
=
a
k
cb
1
....b
l
.
The
language
accepted
by
a
turing
machine
T
is
L
(
T
)=
{
x
∈
Σ
∗
|
q
0
x
⊢
∗
y
q
f
z
,
y
,
z
∈
τ
∗
,
q
f
∈
F
}
3.
TURING
MA
CHINE
AS
A
CCEPT
ORS
Example
1:
L
=
{
a
n
b
n
|
n
≥
1
}
[12],
[13].
T
able
1
describes
the
transition
function
of
the
T
uring
machine
for
Example
1.
T
able
1.
T
ransition
table
for
turing
machine
which
accept
the
language
L
=
{
a
n
b
n
|
n
≥
1
}
Q
τ
a
b
A
B
□
q
0
(
q
a
,
A
,
R
)
(
q
2
,
B
,
R
)
q
a
(
q
a
,
A
,
R
)
(
q
b
,
B
,
R
)
(
q
a
,
B
,
R
)
q
b
(
q
b
,
A
,
L
)
(
q
0
,
A
,
R
)
(
q
b
,
B
,
L
)
q
′
0
(
q
′
0
,
B
,
R
)
(
q
f
,
□
,
R
)
q
f
In
an
y
ID
the
tape
contents
are
of
the
follo
wing
in
v
ariant
property
can
be
used
to
determine
the
transition:
A
∗
a
∗
B
∗
b
∗
(1)
if
n
≥
0
then
the
follo
wing
transi
tion
could
also
be
included:
δ
(
q
0
,
□
)
=
(
q
f
,
□
,
R
)
(2)
3.1.
Algorithm
Problem:
a
language
L
=
{
xx
|
x
∈
(
a,
b
)
∗
}
.
Finding
the
midpoint
of
the
sub-string
and
ins
erting
a
symbol
”
C
”
at
the
midpoi
nt.
Solution
schema:
-
Starting
from
the
leftmost
symbol
mo
v
e
to
the
rightmost
symbol
and
replace
the
rst
”
□
”
by
”
C
”.
-
Change
the
leftmost
lo
wercase
symbol
to
UPPERCASE
and
the
rightmost
lo
wercase
symbol
to
UPPER-
CASE.
-
Exchange
the
”
C
”
with
the
ne
w
uppercase
s
y
m
bol
immediately
preceding
it.
-
The
tape
in
v
ariant
is
no
w
something
lik
e
(
A
+
B
)
∗
.
(
a
+
b
)
∗
.C
.
(
A
+
B
)
∗
.
-
Repeat
steps
2-3
till
the
tape
contents
become
(
A
+
B
)
∗
C
(
A
+
B
)
∗
.
-
No
w
change
all
uppercase
letter
e
xcept
C
to
lo
wercase
(if
necessary).
4.
RESUL
TS
AND
DISCUSSION
Clearly
the
T
uri
ng
machine
discussed
in
pre
vious
section
can
only
compute
functions
o
v
er
strings
o
v
er
a
nite
alphabet
[14],
[15].
What
about
computing
functions
o
v
er
arbitrary(computable)
domains
such
as
the
naturals
[16],
[17],
inte
gers
or
the
rationals
or
e
v
en
Cartesian
products
[18],
[19]
of
such
domains
or
e
v
en
more
generally
functions
from
one
domain
to
another?
4.1.
Computability
in
other
domains
Clearly
if
the
elements
of
such
domains
can
be
represented
as
string
o
v
er
an
alphabet,
then
one
can
talk
about
T
uring
machine
computability
o
v
er
such
domains
[20],
[21].
Comput
Sci
Inf
T
echnol,
V
ol.
7,
No.
2,
July
2026:
196–202
Evaluation Warning : The document was created with Spire.PDF for Python.
Comput
Sci
Inf
T
echnol
ISSN:
2722-3221
❒
199
4.1.1.
Denition
A
set
S
is
represented
by
elements
of
another
set
R
if
there
e
xists
a
partial
surjecti
v
e
function
[22]
R
⇀
S
called
the
interpretation
[23],
[24]
of
R
onto
S
,
as
in
Figure
4,
where:
-
P
artial
is
not
e
v
ery
element
in
R
need
ha
v
e
a
meaning
in
S
.
-
Surjecti
v
e
is
e
v
ery
element
of
S
should
ha
v
e
a
representation
in
R
.
-
On
the
other
hand
tw
o
or
more
elements
of
R
may
be
interpreted
as
representing
the
same
element
in
S
.
R
S
◦
◦
◦
◦
•
•
•
•
Figure
4.
Mapping
diagram
of
partial
surjecti
v
e
function
R
⇀
S
Example:
consider
the
unary
representation
of
the
naturals
as
strings
of
‘1
S
‘
terminated
by
a
single
‘0‘
.
Clearly
I
:
{
0
,
1
}
∗
⇀
N
is
a
partial
function
because
strings
such
as
‘00100‘
ha
v
e
no
interpretation
in
N
.
I
is
also
surjecti
v
e
since
e
v
ery
natural
does
ha
v
e
a
representation
in
{
0
,
1
}
∗
.
If
leading
0
S
are
allo
wed
in
the
representation,
then
each
natural
has
more
than
one
possible
representation.
Gi
ving
tw
o
sets
S
1
and
S
2
represented
by
R
1
and
R
2
respecti
v
ely
through
interpretations
I
1
and
I
2
respecti
v
ely
,
as
in
Figure
5.
R
1
R
2
S
1
S
2
F
I
2
I
1
G
Figure
5.
A
partial
function
F
:
R
1
⇀
R
2
represents
a
partial
function
G
:
S
1
⇀
S
2
if
for
all
r
1
∈
D
o
m
(
I
1
)
,
G
(
I
1
(
r
1
))
=
I
2
(
F
(
r
1
))
i.e.
the
abo
v
e
commutati
v
e
diagram
holds
Alternati
v
ely
,
one
may
attempt
to
construct
F
as
a
representation
of
G
as
a
total
function,
rather
than
e
xpressing
the
diagram
as
a
partial
function.
As
in
Figure
6,
gi
v
en
I
1
:
R
1
⇀
S
1
consider:
I
−
1
1
:
S
1
→
N
R
−
{
ϕ
}
where
I
−
1
1
(
s
1
)
=
{
r
1
∈
R|I
1
(
r
1
)
=
s
1
}
i.e.
I
−
1
1
for
an
y
s
1
∈
S
1
yield
the
set
of
all
possible
representati
on
s
of
s
1
.
Then
F
:
R
1
:
⇀
R
2
may
also
be
e
xtended
to
subsets
of
R
1
as:
F
:
N
R
1
⇀
N
R
2
is
dened
for
each
X
1
⊆
R
1
as
f
(
X
1
)
=
{
f
(
r
1
)
|
r
1
∈
X
1
}
=
X
1
⊆
R
2
.
But
one
should
be
interested
in
ensuring
that
the
follo
wing
diagram
holds
for
an
y
s
1
∈
S
1
,
if
G
(
s
1
)
∈
S
2
,
require
that:
-
There
is
at
least
one
representation
r
1
∈
R
1
such
that
I
2
(
F
(
r
1
))
=
G
∈
S
1
.
-
r
1
̸
=
r
‘
1
⋏
I
1
(
r
1
)
=
I
1
(
r
2
)
=
s
1
⋏
F
(
r
1
)
,
F
(
r
‘
1
)
∈
R
2
⇒
I
2
(
F
(
r
1
))
=
I
2
(
F
(
r
‘
1
))
.
-
There
may
be
representation
of
s
1
in
R
1
for
which
F
(
r
1
)
may
not
be
dened.
Comple
xity
of
nite
state
T
uring
mac
hine
with
other
domain
(Rajesh
K
umar)
Evaluation Warning : The document was created with Spire.PDF for Python.
200
❒
ISSN:
2722-3221
S
1
N
R
1
S
2
N
R
2
I
−
1
1
F
G
I
−
1
2
Figure
6.
A
function
F
:
N
R
1
1
⇀
N
R
2
2
represents
the
possibility
that
F
may
not
be
dened
for
some
v
alue
in
f
(
X
1
)
=
{
f
(
r
1
)
|
r
1
∈
X
1
}
=
X
1
⊆
R
2
4.2.
T
uring-computable
As
in
Figure
7,
a
partial
function
G
:
S
1
⇀
S
2
is
T
uring-computable
[25],
[26]
if
there
e
xists
a
T
uring-computable
function
F
:
Σ
∗
⇀
Σ
∗
on
an
alphabet
Σ
and
interpretations
I
1
,
I
2
with
I
1
:
Σ
∗
⇀
S
1
and
I
2
:
Σ
∗
⇀
S
2
such
that:
-
F
or
each
s
1
∈
S
1
and
F
(
s
1
)
=
s
2
∈
S
2
,
∃
x
1
,
x
2
∈
Σ
∗
[
I
1
(
x
1
)
=
s
1
⋏
I
2
(
x
2
)
=
s
2
⋏
F
(
x
1
)
=
x
2
⋏
∀
y
1
∈
Σ
∗
[
x
1
̸
=
y
1
⋏
I
1
(
y
1
)
=
s
1
⇒
F
(
y
1
)
/
∈
Σ
∗
⋎
I
2
(
F
(
y
1
))
=
s
2
]]
-
F
or
each
s
1
∈
S
1
,
such
that
G
(
s
1
)
/
∈
s
2
,
∀
x
1
∈
Σ
∗
[
I
1
(
x
1
)
=
s
1
⇒
F
(
x
1
)
/
∈
Σ
∗
⋎
I
2
(
F
(
x
1
))
/
∈
s
2
]]
X
1
X
2
S
1
Y
1
S
2
Y
2
F
I
1
I
2
I
1
F
G
I
2
Figure
7.
F
or
an
y
partial
function
G
:
S
1
⇀
S
2
where
G
(
s
1
)
/
∈
S
2
if
and
only
if
s
1
/
∈
D
om
(
G
)
5.
CONCLUSION
A
consequences
of
the
abo
v
e
denition
is
that
the
implem
entation
of
an
y
function
of
an
y
arity
is
that
of
a
unary
function
on
Σ
∗
for
the
chosen
alphabet.
F
acts:
with
addition
to
natural
function
a
binary
function
is
considered
which
is
dened
as
:
+
:
N
×
N
⇒
N
.
Ho
we
v
er
for
an
y
pair
of
naturals
m,
n
∈
N
it
can
be
encoded
o
v
er
Σ
∗
=
{
0
,
1
}
∗
in
unary
with
‘0‘
as
a
separator
between
the
components
of
the
pair
.
Hence
Σ
∗
⇒
N
×
N
is
dened
as
I
1
(1
m
01
n
)
=
(
m,
n
)
and
all
other
patterns
of
strings
x
∈
Σ
∗
−
L
(1
∗
01
∗
)
,
I
1
(
x
)
is
undened.
Similarly
I
2
for
all
the
result
is
simply
dened
as:
I
2
(
y
)
=
(
P
if
y
=
1
p
∈
1
∗
undened
otherwise
W
ith
abo
v
e
representation
the
partial
function
ˆ
+
:
Σ
∗
⇀
Σ
∗
that
we
require
is
gi
v
en
by:
ˆ
+(
x
)
=
(
1
m
+
n
if
x
=
1
m
01
n
for
all
m,
n
≥
0
undened
otherwise
An
y
T
uring
machine
T
ˆ
+
which
implement
ˆ
+
is
a
correct
implementation
of
addition
on
the
naturals.
Comput
Sci
Inf
T
echnol,
V
ol.
7,
No.
2,
July
2026:
196–202
Evaluation Warning : The document was created with Spire.PDF for Python.
Comput
Sci
Inf
T
echnol
ISSN:
2722-3221
❒
201
FUNDING
INFORMA
TION
Authors
state
no
funding
in
v
olv
ed.
A
UTHOR
CONTRIB
UTIONS
ST
A
TEMENT
This
journal
uses
the
Contrib
utor
Roles
T
axonomy
(CRediT)
to
recognize
indi
vidual
author
contrib
utions,
reduce
authorship
disputes,
and
f
acilitate
collaboration.
Name
of
A
uthor
C
M
So
V
a
F
o
I
R
D
O
E
V
i
Su
P
Fu
Rajesh
K
umar
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
Anju
Jain
✓
✓
✓
✓
✓
✓
✓
Rak
esh
K
umar
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
C
:
C
onceptualization
I
:
I
n
v
estig
ation
V
i
:
V
i
sualization
M
:
M
ethodology
R
:
R
esources
Su
:
Su
pervision
So
:
So
ftw
are
D
:
D
ata
Curation
P
:
P
roject
Administration
V
a
:
V
a
lidation
O
:
Writing
-
O
riginal
Draft
Fu
:
Fu
nding
Acquisition
F
o
:
F
o
rmal
Analysis
E
:
Writing
-
Re
vie
w
&
E
diting
CONFLICT
OF
INTEREST
ST
A
TEMENT
Authors
state
no
conict
of
interest.
D
A
T
A
A
V
AILABILITY
The
data
that
support
the
ndings
of
this
study
are
a
v
ailable
from
the
corresponding
author
,
[RK],
upon
reasonable
request.
REFERENCES
[1]
H.
M.
Y
ao
and
L.
Jiang,
“Machine-learning-based
PML
for
the
FDTD
method,
”
IEEE
Antennas
and
W
ire
less
Propag
ation
Letters
,
v
ol.
18,
no.
1,
pp.
192–196,
2019,
doi:
10.1109/LA
WP
.2018.2885570.
[2]
N.
Boull
´
e
and
A.
T
o
wnsend,
“Learning
elliptic
partial
dif
ferential
equations
with
randomized
linear
algebra,
”
F
oundations
of
Computational
Mathematics
,
v
ol.
23,
no.
2,
pp.
709–739,
Apr
.
2023,
doi:
10.1007/s10208-022-09556-w
.
[3]
J.
L.
Hennessy
and
D.
P
atterson,
“
A
Ne
w
Golden
Age
for
Computer
Architecture
Inno
v
ations
lik
e
domain-specic
hardw
are,
enhanced
security
,
open
instruction
sets,
and
agile
chip
de
v
elopment
will
lead
the
w
ay
.
”
Cacm.acm.or
g.
Accessed
Jun.
21,
2025.
[Online].
A
v
ailable:
https://cacm.acm.or
g/research/a-ne
w-golden-age-for
-computer
-architecture/
[4]
G.
Jir
´
ask
o
v
´
a,
A.
Szabari,
and
J.
ˇ
Sebej,
“The
comple
xity
of
languages
resulting
from
the
concatenation
operation,
”
in
International
Conference
on
Descriptional
Comple
xity
of
F
ormal
Systems
,
2016,
pp.
153–167,
doi:
10.1007/978-3-319-41114-9
12.
[5]
G.
Jir
´
ask
o
v
´
a
and
A.
Okhotin,
“State
com
ple
xity
of
unambiguous
operations
on
nite
automata,
”
Theor
etical
Computer
Science
,
v
ol.
798,
pp.
52–64,
Dec.
2019,
doi:
10.1016/j.tcs.2019.04.008.
[6]
Y
.
Oktar
,
“
A
computing
m
achinery
using
a
continuous
memory
tape,
”
arXi
v:
2401.02420,
2023.
[7]
M.
Boja
´
nczyk
and
R.
Stef
a
´
nski,
“Single-use
automata
and
transducers
for
innite
alphabets,
”
in
47th
International
C
olloquium
on
Automata,
Languages,
and
Programming
(ICALP
2020)
,
2020,
pp.
1–14,
doi:
10.4230/LIPIcs.ICALP
.2020.113.
[8]
H.
Boche,
A.
Grigorescu,
R.
F
.
Schaefer
,
and
H.
V
.
Poor
,
“
Algorithmic
computability
of
the
capacity
of
additi
v
e
colored
Gaussian
noise
channels,
”
in
GLOBECOM
2023
-
2023
IEEE
Global
Communications
Conference
,
Dec.
2023,
pp.
4375–4380,
doi:
10.1109/GLOBECOM54140.2023.10436918.
[9]
L.
Dartois,
P
.
Gastin,
L.
G.
Guizouarn,
R.
Go
vind,
and
S.
Krishna,
“Re
v
ersible
transducers
o
v
er
innite
w
ords,
”
arXi
v:
2406.11488,
2024.
[10]
M.
de
Benedetto,
“Explication
as
a
three-step
procedure:
the
case
of
the
Church-T
uring
thesis,
”
European
Journal
for
Philosoph
y
of
Science
,
v
ol.
11,
no.
1,
p.
21,
Mar
.
2021,
doi:
10.1007/s13194-020-00337-2.
[11]
O.
Goldreich,
S.
Micali,
and
A.
W
igderson,
“Ho
w
to
play
an
y
mental
g
ame
,
or
a
completeness
theorem
for
protocols
with
honest
ma
jority
,
”
in
Pro
viding
Sound
F
oundations
for
Cryptograph
y:
On
the
W
ork
of
Sha
Goldw
asser
and
Silvio
Micali
,
2019,
pp.
218–229,
doi:
10.1145/3335741.3335755.
[12]
H.
B.
Ax
elsen
and
R.
Gl
¨
uck,
“On
re
v
ersible
T
uring
machines
and
their
function
uni
v
ersality
,
”
Acta
Informatica
,
v
ol.
53,
no.
5,
pp.
509–543,
Aug.
2016,
doi:
10.1007/s00236-015-0253-y
.
[13]
B.
Gonc
¸
alv
es,
“The
T
uring
test
is
a
thought
e
xperiment,
”
Minds
and
Machines
,
v
ol.
33,
no.
1,
pp.
1–31,
Mar
.
2023,
doi:
10.1007/s11023-022-09616-8.
[14]
F
.
Ne
v
en,
T
.
Schwentick,
and
V
.
V
ianu,
“Finite
state
machines
for
strings
o
v
er
innite
alphabets,
”
A
CM
T
ransactions
on
Computational
Logic
(T
OCL)
,
v
ol.
5,
no.
3,
pp.
403–435,
Jul.
2004,
doi:
10.1145/1013560.1013562.
[15]
Y
.
F
orster
,
F
.
K
unze,
and
M.
W
uttk
e,
“V
eried
programming
of
T
uring
machi
nes
in
Coq,
”
in
Proceedings
of
the
9th
A
CM
SIGPLAN
International
Conference
on
Certied
Programs
and
Proofs
,
Jan.
2020,
pp.
114–128,
doi:
10.1145/3372885.3373816.
Comple
xity
of
nite
state
T
uring
mac
hine
with
other
domain
(Rajesh
K
umar)
Evaluation Warning : The document was created with Spire.PDF for Python.
202
❒
ISSN:
2722-3221
[16]
T
.
Ha,
V
.
Harizano
v
,
L.
Marshall,
and
H.
W
alk
er
,
“Comput
ability
and
denability
,
”
in
Structure
and
Randomness
in
Computability
and
Set
Theory
,
D.
Cenzer
,
C.
Porter
,
and
J.
Zapletal,
Eds.,
Sing
apore:
W
orld
Scientic,
2021,
pp.
285–355.
[17]
K.
Mainzer
,
“Logical
thinking
becomes
automatic,
”
in
Articial
Intelligence
-
When
do
Machines
T
ak
e
Ov
er?
,
K.
Mainzer
,
Ed.,
Berlin:
Springer
Berlin
Heidelber
g,
2020,
pp.
15–45,
doi:
10.1007/978-3-662-59717-0
3.
[18]
J
.
Y
ou,
R.
Y
ing,
and
J.
Lesk
o
v
ec,
“Design
space
for
graph
neural
netw
orks,
”
in
Adv
ances
in
Neural
Information
Processing
Systems
,
H.
Larochelle,
M.
Ranzato,
R.
Hadsell,
M.
F
.
Balcan,
and
H.
Lin,
Eds.,
Ne
w
Y
ork,
NY
:
Curran
Associates,
Inc,
2020,
pp.
17009–17021.
[19]
B
.
Jacquet,
F
.
Jamet,
and
J.
Baratgin,
“On
the
pragmatics
of
the
T
uring
test,
”
in
2021
International
Conference
on
Information
and
Digital
T
echnologies
(IDT)
,
Jun.
2021,
pp.
123–130,
doi:
10.1109/IDT52577.2021.9497570.
[20]
W
.
Si
e
g,
“G
¨
odel’
s
philosophical
challenge
(to
T
uring),
”
Studia
Semiotyczne
,
v
ol.
34,
no.
1,
pp.
57–80,
2020.
[21]
V
.
Brattka
and
P
.
Hertling,
Handbook
of
computability
and
comple
xity
in
analysis
.
Cham:
Springer
International
Publishing,
2021,
doi:
10.1007/978-3-030-59234-9.
[22]
C
.
Borlido
and
B.
McLean,
“Dif
ference–restriction
algebras
of
partial
functions
with
operators:
discrete
duality
and
completion,
”
Journal
of
Algebra
,
v
ol.
604,
pp.
760–789,
Aug.
2022,
doi:
10.1016/j.jalgebra.2022.03.039.
[23]
J.
Mayr
et
al.,
“Thermal
issues
in
machi
ne
tools,
”
CIRP
Annals
,
v
ol.
61,
no.
2,
pp.
771–791,
2012,
doi:
10.1016/j.cirp.2012.05.008.
[24]
C.
Knapp,
“P
artial
functions
and
recursion
in
uni
v
alent
type
theory
,
”
arXi
v:
2011.00272,
2020.
[25]
Z.
Hou,
“T
uring
machi
nes
and
computability
,
”
in
Fundamenta
ls
of
Logic
and
Computation:
W
ith
Practical
Automated
Reasoning
and
V
erication
,
Z.
Hou,
Ed.,
Cham:
Springer
International
Publishing,
2021,
pp.
163–205,
doi:
10.1007/978-3-030-87882-5
5.
[26]
H.
Pe
tersen,
“Some
remarks
on
real-time
T
uring
machines,
”
arXi
v:
1902.00975,
2019.
BIOGRAPHIES
OF
A
UTHORS
Rajesh
K
umar
obtained
his
B.Sc.
De
gree,
Master’
s
De
gree
(Master
of
Computer
Applications)
and
Ph.D.
from
K
urukshetra
Uni
v
ersity
,
K
urukshetra.
Currently
,
he
is
head
of
the
Department
of
Computer
Science
and
Applications,
Chhaju
Ram
Memorial
Jat
Colle
ge,
Hisar
,
Haryana,
India.
He
is
a
co-author
of
three
books.
His
research
interests
are
in
genetic
algorithm,
theory
of
automata,
softw
are
engineering,
articial
intelligence,
design
and
analysis
of
algorithm
and
Linux
administration
and
k
ernel
design.
He
can
be
contacted
at
email:
rajtaya@kuk.ac.in.
Anju
J
ain
holds
a
Ph.D.
in
Computer
Science
and
Engineering
from
Guru
Jambheshw
ar
Uni
v
ersity
of
Science
and
T
echnology
(GJUS&T),
India.
She
has
serv
ed
in
v
arious
academic
roles
including
lecturer
,
teaching
associate,
and
assistant
professor
across
academies,
colle
ges,
and
uni
v
ersities.
A
tw
o-time
Gold
Medalist,
Dr
.
Jain
has
published
se
v
eral
research
papers
in
reputed
journals
and
conference
proceedings.
She
possesses
nearly
15
years
of
teaching
e
xperienc
e,
with
o
v
er
7
years
i
n
the
Computer
Science
departm
ent
in
higher
education
in
India.
Her
broad
research
interests
include
machine
learning,
data
analytics,
data
mining,
and
e
v
olutionary
algorithms.
She
can
be
contacted
at
email:
anjuaryan2012@gmail.com.
Rak
esh
K
umar
obtained
his
B.Sc.
De
gree,
Master’
s
De
gree
–
Gold
Medalist
(Master
of
Computer
Applications)
and
Ph.D.
(Computer
Science
and
Applications)
from
K
urukshetra
Uni
v
ersity
,
K
urukshetra.
Currently
,
he
is
dean
academic
af
f
ai
rs,
professor
and
chairperson
in
the
Department
of
Computer
Science
and
Applications,
K
urukshetra
Uni
v
ersity
,
K
urukshetra,
Haryana,
India.
His
research
interests
are
in
genetic
algorithm,
softw
are
testing,
articial
intelligence,
and
netw
orking.
He
is
a
senior
member
of
International
Association
of
Computer
Science
and
Information
T
echnology
(IA
CSIT).
He
ca
n
be
contacted
at
email:
rak
eshkumar@kuk.ac.in.
Comput
Sci
Inf
T
echnol,
V
ol.
7,
No.
2,
July
2026:
196–202
Evaluation Warning : The document was created with Spire.PDF for Python.