4 ms·
Actually, I thought you don’t even need unbounded memory because it’s proven that the register machine [0] with limited memory is still Turing complete. [0] ht
by Item_Boring 6y ago
Actually, I thought you don’t even need unbounded memory because it’s proven that the register machine [0] with limited memory is still Turing complete.
[0] https://en.wikipedia.org/wiki/Register_machine https://en.wikipedia.org/wiki/Register_machine
- ivanbakel 6y agoAbstract register machines are normally considered to have infinite memory - because even though the number of registers can be bounded, their size is often not. Unlike the fixed-width registers of a real CPU, abstract registers are typically capable of storing any positive integer.
- Item_Boring 6y agoI’m aware and that’s how they are usually introduced. However, there’s also the model of such that have a further restricted set of instructions and only have limited memory.
- ivanbakel 6y agoCould you please give a reference for such a model, and the proof that it's Turing complete? I don't see it described on the Wikipedia page, which explicitly states that registers are unbounded.