Theory of Computation: Questions and Solutions
Chapter 4: Decidability
A decider is a Turing machine that always halts. To show that a language
A
is decidable
is to show that there is a decider
M
that decides it. In other words, given a string
w
, by
simulating
M
on input
w
:
•
M
must accept
w
, if
w
∈
A
, and
•
M
must reject
w
, if
w
6∈
A
.
To show that a Turing machine is a decider is to show that it always halts. In other words,
every step of the Turing machine will take a finite amount of time (no chance for infinite
loop).
Theorem 4.1
Consider the problem of determining whether a DFA
B
accepts input string
w
.
Convert
this problem into a membership problem by converting it into a language and show that the
language is decidable.
Solution
: The problem can be converted into a membership problem as follows:
A
DFA
=
{h
B, w
i |
B
is a DFA that accepts input string
w
}
To show that
A
DFA
is decidable, we need to show that there exists a Turing machine
M
that
decides it. In other words,
M
must accept
h
B, w
i
if
h
B, w
i ∈
A
DFA
and
M
must reject
h
B, w
i
if
h
B, w
i 6∈
A
DFA
. Note that
h
B, w
i ∈
A
DFA
if an only if
B
is a DFA that accepts input string
w
. Given a DFA
B
and a string
w
, we can check whether
B
accepts
w
by simply run
B
on input
w
until the last symbol of the string
w
has been process. If the current state after
processing the last symbol of the input string
w
is an accept state,
B
accepts
w
. Otherwise,
B
rejects
w
. With this idea, the Turning machine
M
that decides
A
DFA
can be constructed
as follows:
M
=“On input
h
B, w
i
, where
B
is a DFA and
w
is a string:
1.
Simulate
B
on input
w
2.
If the simulation ends in an accept state,
accept
. If it ends in a nonaccepting state,
reject
.”
A DFA always halts after processing the last symbol of an input string. Simulating a DFA
on an input will take a finite amount of time since an input string is a finite sequence of
symbols. Checking whether a state is in a set of accept states takes a finite amount of time.
Therefore, the Turing machine
M
is a decider. Next, we need to show that
h
B, w
i ∈
A
DFA
iff
M
accepts
h
B, w
i
.
•
Assume that
h
B, w
i ∈
A
DFA
. Since
h
B, w
i ∈
A
DFA
, by the definition of the language
A
DFA
,
B
is a DFA and
B
accepts
w
. Since
B
accepts
w
, by simulating
B
on input
w
in step 1,
B
willl accept
w
which causes TM
M
to accept the input
h
B, w
i
.

CS 1502 — Formal Method in Computer Science
Page 1

Theory of Computation: Questions and Solutions