|
To demonstrate that a problem is computable, all you need is an algorithm for it. For example, take the language
PRIME = {n | n is a prime integer}where the alphabet is the set of decimal digits. (An integer n is prime if n > 1 and the only factors of n are 1 and n.)
Any algorithm will do. Here is a sketch of one.
isprime(n)
if n < 2 then
return false
else
for k = 2,...,n-1 do
if n mod k = 0 then
return false
end if
end for
return true
end if
Suppose
E1 = {3}Is E computable? Sure! Here is an algorithm that solves it.
inE(n)
if n == 3 then
answer yes
else
answer no
end if
What about E2 = {2,4}? Sure!.
inE2(n)
if n == 2 or n == 4 then
answer yes
else
answer no
end if
Is {} computable? Sure! The answer is always no.
inEmpty(n) Answer no
We will get a lot of useful results out of problems that ask questions about programs. To start, let's concentrate on finite state machines.
It is easy to come up with a textual description of finite state machines. For example, list the alphabet, the set of states, the start state, the accepting states and a table giving the transition function.
‹M› is the a textual description of finite state machine M.
For our first problem about finite state machines, lets use
ACCEPT-DFA = {(‹M›, s) | M accepts string s}(An ordered pair can also be encoded in text; I just did it in the line above.)
You should immediately realize that ACCEPT-DFA is computable. Just use the characters of s to follow transitions in M. Writing a program to do that is just a trivial programming exercise.
Define language
NONEMPTY-DFA = {‹M› | M accepts at least one string}To solve NONEMPTY-DFA, it is just a matter of finding out if any accepting state is accessible by a sequence of transitions from the start state.
nonempty(‹M›)
markAllAccessible(‹M›)
If any accepting state of M has a mark in it then
return true
else
return false
endif
markAllAccessible(‹M›)
put a mark in the start state of M.
finished = false.
while not finished do
finished = true.
for each state q of M
if q has a mark in it
for every state q' where there
is a transition from q to q'
if q' does not have a mark in it
put a mark in state q'.
finished = false.
end if
end for
end if
end for
end while
That is all it takes to show that NONEMPTY-DFA is computable (plus, of course, an argument that the algorithm works, which I leave to you.)
Define language
ALL-DFA = {‹M› | M accepts all strings over its alphabet}Think for a moment about how you would solve ALL-DFA. Here is a spurious argument that ALL-DFA is not computable.
To ask whether ‹M› ∈ ALL-DFA, you try every string s, and check whether M accepts s.But there are infinitely many strings to check! So the algorithm never stops. Since an algorithm needs to stop for us to say that it solves a problem, ALL-DFA must not be computable.
Nonsense! That is the naive argument: "I thought of an approach that does not work, therefore no approach will work."
In fact, ALL-DFA is computable, and it is not really very difficult.
Start by marking all states of M that are accessible from the start state, as in the preceding algorithm.
If, after all accessible states have been marked, you find that all marked states are accepting states, then the answer is true, M ∈ ALL-DFA.
If there is an accessible state that is rejecting, then the answer is false.
|