Cheap and Secure Web Hosting Provider : See Now

[Solved]: Explanation for indirect addressing

, , No Comments
Problem Detail: 

While reading about minimal instruction set computer I found out that one needs at least (for example) the ability to increment or decrement the value stored in register, a test for zero and a jump.

A machine with such instruction set would be Turing-complete, correct? Is this called "Counter machine"?

But then I found out about the so-called "Random-access machine" which adds "indirect addressing", meaning I can access a register not just by explicitly specifying memory address or label but I can also fetch an address out of an address. This should be useful for enabling mechanisms akin to "pointers" in C-like languages, for example.

My question is, why there is the need for "indirect addressing"? Since I presume both machines (without and with indirect addressing) are Turing complete, is it "merely" for convenience? Or are some programs which cannot by expressed without indirection?

PS: I'm complete noob in this area so please bear with me: if I was to implement memcpy, i.e. to transfer the values of bunch of registers to other bunch of registers, how would I do it without indirection? I mean, I can write copy 1 word from x to y, copy 2 words from x to y, ... but in general, how do I say copy n words from x to y without it?

Edit:

For example, imagine I receive zero-terminated string via network, say "1 2 3 0" which I would like to store to some of my infinitely-many registers. Receiving "0" halts the program. I have a instruction "take r" which copies one word from the input to register "r". No indirection means (?) that "r" has to be direct constant number. How do I then move to "n-th" register? In other words, I don't understand how do I move back and forth among the registers, when the only mechanism I have is to read/set register 1, 2, 3, ...?

Asked By : Ecir Hana

Answered By : Raphael

Here is how you can implement indirect addressing without an atomic operation that does so.

We assume that we can label memory cells (either tape cells or registers, or whatever) in some way. This can be implemented by marked copies of the tape alphabet, or a special encoding of the content.

Idea: Addresses are offsets. If you want the $n$th cell, move a marker $n$ steps from the beginning. For that, you maintain a counter at a fixed location (determined by the programmer/compiler). After that, perform your operation on the first marked cell. Remove the marking when you are done.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51444

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback