Information Technology Reference
In-Depth Information
ASSEMBLY-LANGUAGE PROGRAMMING
3.18 Write an assembly-language program in the language of Fig.
3.18
to subtract two inte-
gers.
3.19 The assembly-language instructions of Fig.
3.18
operate on integers. Show that the
operations
AND
,
OR
,and
NOT
can be realized on Boolean variables with these instruc-
tions. Show also that these operations on vectors can be implemented.
3.20 Write an assembly-language program in the language of Fig.
3.18
to form
x
y
for inte-
gers
x
and
y
.
3.21 Show that the assembly-language instructions CLR R
i
,R
i
←
R
j
,JMP
+
N
i
,andJMP
−
N
i
can be realized from the assembly-language instructions INC, DEC, CONTINUE,
R
j
JMP
+
N
i
,andR
j
JMP
N
i
.
−
TURING MACHINES
3.22 In a standard Turing machine the tape unit has a left end but extends indefinitely to the
right. Show that allowing the tape unit to be infinite in both directions does not add
power to the Turing machine.
3.23 Describe in detail a Turing machine with unlimited storage capacity that recognizes the
language
0
m
1
m
.
3.24 Sketch a proof that in
O
(
n
4
)
steps a Turing machine can verify that a particular tour
of
n
cities in an instance of the Traveling Salesperson Problem satisfies the requirement
that the total distance traveled is less than or equal to the limit
k
set on this instance of
the Traveling Salesperson Problem.
3.25 Design the additional circuitry needed to transform a sequential circuit for a random-
access memory into one for a tape memory. Give upper bounds on the size and depth
of the next-state and output functions that are simultaneously achievable.
3.26 In the proof of Theorem
3.8.1
it is assumed that the words and their addresses in a
RAM memory unit are placed on the tape of a Turing machine in order of increasing
addresses, as suggested by Fig.
3.40
. The addresses, which are
{
|
1
≤
m
}
log
m
bits in length,
are organized as a collection of
b
-bit words. (In the example,
b
=
1.) An
address is written on tape cells that immediately precede the value of the corresponding
RAM word. A RAM address
addr
is stored on the tape to the left in the shaded region.
Assume that markers can be placed on cells. (This amounts to enlarging the tape al-
phabet by a constant factor.) Show that markers can be used to move from the first
word whose RAM address matches the
ib
most significant bits of the address
a
to the
log
m
/b
Figure 3.40
A TM tape with markers on words and the first bit of each address.
Search WWH ::
Custom Search