Modeling Computer Viruses

[ Pobierz całość w formacie PDF ]

What we cannot do, according to the conventions, is have a peek at the content of the tape while the
machine has not yet halted. To allow this, we can define a tape-content-convention. We can get the tape
content after each move from the Turing Machine configuration at that point.
Definition 1.26 (Tape content convention). Let M be a Turing Machine and in " �". The tape content of M
started with in is observable as the sequence of words tseqM(in) : � �! �" such that:
M
tseqM(in)(�) = t �!�! seqM(in)(�) = (q, t, p) (for some q " Q, p " �)
Then tseqM(in)(�) is the content of the tape after � many moves. We analogously define sseqM(in) as
the unique move-connected sequence of Turing Machine states and pseqM(in) as the tape head position
sequence.
11
By observing output we also observe that a machine halts; we cannot observe that a machine does not halt.
1.2. TURING MACHINES REDEFINED 11
Using this convention we can look more closely at Turing Machines.
Definition 1.27 (Tape equivalence). Let M, N be Turing Machines. Then M and N are tape-equivalent,
written as M a"tape N if:
(" in " �") tseqM(in) = tseqN(in)
Some of the moves connecting the configurations could be viewed as just movement of the tape head .
In our formalisation we cannot distinguish between writing the same symbol to the tape or leaving the
cell untouched. There are common formalisations of Turing Machines that do distinguish these, with for
�
example tr : Q � � �! Q � (� *" {-1, 1}). The drawback here is that a machine cannot write and move the
tape head at the same time.
In any case, we like to be able to cut out the moves where the tape content does not change. By the
tape content convention we already have tape sequences available. We do not need another convention.
Definition 1.28 (Tape change sequence). Let M be a Turing Machine and in " �" . We define a tape change
M
sequences tcseqM(in) as:
tcseqM(in) : � �! �"
M
tcseqM(in)(�) = tcseqM(in)(gM,in(�))
where
gM,in(0) = 0
��
��gM,in(x) if tseqM(in)(x + 1) = tseqM(in)(gM,in(x))
��
��
gM,in(x + 1) =
��
��g(x) + 1 otherwise
ó�
Now we get our third notion of equivalence.
Definition 1.29 (Tape change equivalence). Let M, N be Turing Machines. Then M and N are tape change
equivalent, written as M a"change N if:
(" in " �") tcseqM(in) = tcseqN(in)
We can now express the fact that the (input and output) convention do matter.
Claim 1.30. These three equivalence notion are strict refinements in this order:
a"tape �" a"change �" a"func
Remark 1.31. As an example of the importance of the output conventions, we would like to quote from [19,
Section 2.1]. According to van Emde Boas:
If one wants the model to produce output, one normally adopts an ad hoc convention for ex-
tracting the output from the final configuration. (For example, the output may consist of all
nonblank tape symbols written to the left of the head in the final configuration).
Indeed, the suggested convention allows us to determine a finite output string; in order to do so the tape
head position must be observable. While it is perfectly fine to adopt an ad hoc output convention, it would
not be fine to omit the convention. The reader may verify that, even for machines that start with input in PB
and that do not write blanks, the functional equivalence derived from this output convention is incomparable
to the functional equivalence defined in this section.
1.2.4 Turing Machines with Multiple Tapes
We could conceive of a Turing Machine as having multiple tapes instead of just one. We would like to
extend our framework of the previous sections in such a way that the old definitions are a special case. We
define an n-tape Turing Machine as a Turing Machine M = (Q, �, tr, q0) with the transition function
tr : Q � (� *" { })n �! Q � �n � {-1, 0, 1}n
12 CHAPTER 1. COMPUTING MACHINES
A configuration is now a triple (q, t, p) such that q " Q, t " (SB)n and p " �n. A move is (q, t, p) �!
(q , t , p ) if (q, f rom, q , to, pos) " tr such that:
f rom = (t0(p0), . . . , tn-1(pn-1))
to = t0(p0), . . . , tn-1(pn-1)
pos = (p 0 - p0), . . . , (p n-1 - pn-1)
ti = ti pi �! ti(pi) (for all i
If we extend the input convention to multiple tapes (the initial configuration is (q0, in, 0) such that in " (PB)n
and 0 is an n-tuple with all elements zero) then the proof of Lemma 1.19 naturally extends to multiple tapes. [ Pobierz całość w formacie PDF ]

Odnośniki