[ Pobierz całość w formacie PDF ]
The natural extension of the meaning of Turing Machines follows.
Definition 1.32 (Functional interpretation). Let n
the function fM : (£")n ’! (£")n such that, for all in " (£")n:
ñø
ôøout if " out " (£")n such that in ’!M out
ôø
òø
fM(in) =
ôø
ôø‘! otherwise
óø
We can choose to give an n-tape Turing Machine other meaning. For instance, we can only use the
first tape for input and output and use the other tapes as working memory . This can expressed as
( f (in) “! '" f (in) = out) Ð!Ò! (in, , . . . , ) ’!M (out, w2, . . . , wn-1) (where is the empty string and
, w2, . . . , wn-1, in, out " £"). We can think of other variations, for instance designating some tapes for
input, other for output, etc. In each case we have to be specific about our definitions and conventions.
As proved in [9, Theorem 2.1], multiple tape Turing Machines (with the first tape as input/output tape)
are equivalent in the sense that for any n-tape Turing Machine M there is a single tape Turing Machine
M such that fM fM . We have no reason to doubt that this extends to multiple tape Turing Machines as
defined in this section. The proof is beyond the scope of this thesis, however.
1.3 Persistent Turing Machines
There is an ongoing debate about the status of Turing Machine computations [26, 36, 38]. Do Turing Ma-
chines capture all modern notions of computation? Are there notions of computation that are more expres-
sive than computing functions and yet realistic?
We will now explore Persistent Turing Machines (PTMs), which are due to Goldin et al. [26]. Our
specific interest in PTMs stems from [33], wherein Hao, Yin and Zhang model computer viruses on (Uni-
versal) PTMs. We will discuss to what extent (Universal) PTMs model computers in Section 2.1; we
discuss whether they are suitable to define computer viruses in Section 2.4.3. Universal PTMs are intro-
duced in Section 1.5.4. In this section we will introduce the reader to the basic definition of PTMs.
Definition 1.33 (Persistent Turing Machine). A Persistent Turing Machine (PTM) is a 3-tape Turing Ma-
chine (3TM) as defined in Section 1.2.4, where each tape has special meaning:
" The first tape contains the input. In principle, the machine will not write on this tape (this restricts
the transition function).
" The second tape is the work tape. The content of this tape is persistent; this is the distinguishing
feature of PTMs.
" The content of the third tape after computation has halted, is designated as output .
1.4. TURING S ORIGINAL MACHINES 13
We intend to repeatedly feed the PTM with new input and wait for the output. This process of feeding
is meant to be sequential - and the machine may remember what input was fed to it. When we say that
the content of the work tape is persistent, we mean that in the sequential process of feeding inputs to the
machine we leave the work tape undisturbed.
As correctly noted in [36, Section 5.2], a 3-tape Turing Machine can be simulated by a normal (modern
1-tape) Turing Machine. A function computed by a 3-tape machine can be computed by some 1-tape ma-
chine. The observation that the authors fail to make, is that if we give new meaning to what the machine
does, this new meaning might not be equivalent to the old. Never mind that we use three tapes for a PTM;
this just eases the definitions (and our intuitions).
We can formally define PTMs on the basis 3TMs as defined in Section 1.2.4. This is a slight deviation
from [26] as our definitions are more restrictive in the use of blanks. (The input and output is restricted to
pure content).
Definition 1.34 (PTM Macrosteps [26]). Let M be a 3-tape Turing Machine with alphabet £. We define
PTM macrosteps - on top of macrosteps of a 3-tape Turing Machine (see Section 1.2.4). Let i, w, w , o "
’!
M
P£*"{ } and be a tape containing only blanks. Then
·
i/o
w -’! w Ð!Ò! (i, w, ) ’!M i, w , o
-
M
Macrosteps only express the fact that we can feed the PTM a single input. To capture the sequential
process that the PTM is meant to carry out, we define PTM sequences. These sequences should capture
three notions. First that the input is unknown beforehand (we remain free to choose it). Second, the work
tape content is determined by the machine, and is used in the next step. Last, the output is determined by
the machine and a given input.
"
Definition 1.35 (PTM sequences). A PTM sequence for machine M is a sequence p : ± ’! (P£ *"{ })3 such
·
[ Pobierz całość w formacie PDF ]