Lack of indirect memmory access implies need of self-modifying code (to be Turing-complete)

[hadrava]

Sorry if this issue is in wrong place. I cannot find a project about 8-bit computer. But it is still about the data that are written to EEPROM.

---

With current microcode, the memory address register can be set only by address hard-coded in instruction operand. It is now difficult* to write code that access an array element:

*) by difficult i mean that you have to use self-modifying code, which is non-standard construction

C example:

uint8_t array[4] = {10, 11, 12, 13};
uint8_t index = 2;
uint8_t c;

c = array[index];

Assembly representation:

0: LDA 0xE ; load variable index to register A
1: ADD 0x9 ; add op-code of instruction which loads first element of an array
2: STA 0x3 ; modify next instruction so it will load data from array[index] instead of array[0]
3: LDA 0xA ; this is modified to LDA 0xC (A <-- array[index]) before running
4: STA 0xF ; save result to variable c
5: HLT;
6:
7:
8:
9: LDA 0xA ; instruction which would load array[0], used for indirect access
A: 10 ; array[0]
B: 11 ; array[1]
C: 12 ; array[2]
D: 13 ; array[3]
E:  2 ; index
F:  0 ; c (the result)

"Usual" instruction sets would be Turing-complete even if we disallow self-modifying code (e. g. forbid writes to code segment of memory). In fact, this is quite common: In "normal" computers, the program is run from RAM. But it is usually in write-protected segments and data segments are protected from execution. It is not that common for code to self-modify itself. Same applies also to theoretical models. Neither Turing Machine nor Random Access Machine can modify its own code. But both are Turing-complete.

On the other hand, the Turing completeness of your 8-bit computer instruction set relies on ability of code to self-modify. Without self-modifying code, it can access only constant size of memory. So it cannot do anything like loop through an input array. In that case this 8-bit computer would not be Turing-complete anymore.

It basically means, that it is Turing-complete, but in different way than "normal" computers. I know, that you want to keep your 8-bit computer as simple as possible, but for educational purpose this difference should be at least noted somewhere.

If i may use analogy with Turing Machine from your video "Making a computer Turing complete". Turing machine's new state depends on data, so we need conditional jump. And same apply to memory address: Turing machine's next memory address (head position) also depends on data, so we need to set memory register based on data and not just to position fixed by a code.

And yes, current implementation overcomes lack of indirect access with self-modifying code. That is something that Turing Machine or Random Access Machine cannot do -- both models cannot modify their code, so they both need some kind of indirect access.

I suggest to add a pair of instructions which would do indirect load/store operations. Load is quite simple to implement: we can define LDAX instruction which will load data from address stored in register A:

 { MI|CO,  RO|II|CE,  AO|MI,  RO|AI,  0,           0, 0, 0 },   // 1001 - LDAX

But there are few issues with store. There is no instruction to manipulate with B register directly, so instruction that would save A to address stored in B would be useless. (Unless something like MOV A -> B is also added.)

So second option is to have indirect instructions LDAI/STAI load/store from/to address stored in memory address specified with operand.

 { MI|CO,  RO|II|CE,  IO|MI,  RO|BI,  BO|MI,   RO|AI, 0, 0 },   // 1001 - LDAI
 { MI|CO,  RO|II|CE,  IO|MI,  RO|BI,  BO|MI,   AO|RI, 0, 0 },   // 1001 - STAI

Only problem is, that these instructions are too long: 6 steps. But maybe it is possible to write directly from RAM register to Memory register (i am not sure about buffering there):

 { MI|CO,  RO|II|CE,  IO|MI,  RO|MI,   RO|AI, 0, 0, 0 },   // 1001 - LDAI
 { MI|CO,  RO|II|CE,  IO|MI,  RO|MI,   AO|RI, 0, 0, 0 },   // 1001 - STAI

After that, the example from beginning can be written without code modification:

0: LDA  0xE ; load variable index to register A
1: ADD  0xA ; add address of first element of an array
2: STA  0x9 ; save pointer *array[index] to temporary variable
3: LDAI 0x9 ; indirect load
4: STA  0xF ; save result to variable c
5: HLT;
6:
7:
8:
9:  0 ; temporary variable used to overcame lack of address registers
A: 10 ; array[0]
B: 11 ; array[1]
C: 12 ; array[2]
D: 13 ; array[3]
E:  2 ; index
F:  0 ; c (the result)

---

Well. What i just wrote is not entirely true. Turing Machine may be still simulated even if we do not have indirect access and we forbid self modifications of code. But we would need to extend word size to incredible lengths and store whole array in just one word. Than something as indirect access can be simulated using bit shifts and masking. So it can be computed with current instructions without self-modification. But that would be even bigger hack, which is usually forbidden even in theoretical models like Random Access machine.