| Yeah, that disturbed me too, but I don't think you can bound the compute
time by the dictionary size. For specific dictionaries, however, the problem
is decidable; the simplest example is a dictionary in which each right-hand
word is not longer than its left-hand word. When this doesn't hold, the
only way to make the problem decidable is to come up with a proof that
bounds the space of intermediate results; a trivial example of that would
be if the only entry in the dictionary whose right-hand side was larger was:
a -> zzz
and no left-hand word in the dictionary had any z's in it (I told you it
was trivial).
This dictionary problem has some parallels to the "3n+1" problem in one of
the previous Notes - is there a finite dictionary for which they are equivalent?
|
| (This is rebuilt from a vague memory from a text by Kfoury, Moll, and
Arbib.)
Take any Turing Machine. There is a set, S, of symbols (including
blank) which may appear on tapes of this machine. It has some number,
n, of states.
Create a new set, S', with all the elements of S plus n+2 more, one of
them being denoted here by % and another by $.
A string of the form $pdq%t%xyz$ will represent the Turing Machine in
state t with a tape that has on it pdqxyz, with the I/O head of the
machine positioned over the x.
For every pair of symbols each in S, a and b, and every state of the
Turing machine, c, define a substitution from a%c%b to %d%ae or a%d%e or
ae%d%, depending on whether the Turing Machine's rules state to move
backward, not at all, or forward when input character b is seen in
state c, and where d is the new state of the machine and e is the
character to be written (or b if there is no change).
Also define substitions from "$%" to "$ %" and "%$" to "% $" and from
"$ " and " $" to "$". This permits us to mimic an infinite tape
initially filled with blanks and to clean up the unneeded blanks after
they are used.
This gives us a way to change any Turing Machine into a dictionary of
substitutions, only one (at most) substitution of which can be made at
any particular time (making the substitutions deterministic). (Except
for creating and deleting blanks.)
Suppose there is an algorithm that determines if one string is
derivable from another with a particular set of rules. To find out if
any Turing Machine halts with some specified input, add a routine to
the end of the Turing Machine that leaves only "I stop." on the tape,
with the machine positioned in state x with the I/O head at "I". Ask
our algorithm if "$%x%I stop.$" can be derived from the specified input
(with the initial Turing Machine state-string embedded) using the rules
produced for that machine. We have just solved the Halting Problem.
-- edp
|