2
$\begingroup$

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, ...?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Just to check I understood: so indirect addressing is just a convenience, right? $\endgroup$ – Ecir Hana Jan 4 '16 at 22:14
  • $\begingroup$ @EcirHana That's the consequence, yes. I sketch a proof (by simulation) that shows that indirect addressing is redundant. $\endgroup$ – Raphael Jan 5 '16 at 1:23
  • $\begingroup$ I'm sorry but I think I still don't get it. May I ask you for one more clarification? 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 guess the part of your answer I don't understand is how do I move back and forth among the registers? (If that's what you meant.) $\endgroup$ – Ecir Hana Jan 5 '16 at 2:21
  • $\begingroup$ @EcirHana Do you have access to constantly many "variables" with which to address registers? If not, the answer to your question is trivially "no" since then any given program can only access a fixed amount of registers no matter the input. I guess my assumption was that you have some way to access registers besides constant addresses. $\endgroup$ – Raphael Jan 5 '16 at 20:32
  • $\begingroup$ Ok, that clears it up, thanks! Btw., I thought this (no "variables") is what is called "Counter machine", isn't that correct? $\endgroup$ – Ecir Hana Jan 5 '16 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.