Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

For instance, the tape on a Turing machine is infinite, where as we usually only have a finite amount of available memory. Secondly Turing machines are not really convenient IMHO for proving things about everyday algorithms on an everyday computer.

I want a model that makes computations in a ring, namely $\Bbb{Z}_p\times \dots \times \Bbb{Z}_p = (\Bbb{Z}_p)^k$, where $p$ is prime (for a good reason... later on that). Since that's what bytes on a computer look like they look like values in $\Bbb{Z}_8$ and even some of the instructions on those bytes on modern computers cause wrap around that looks like that of $\Bbb{Z}_8$. It's obvious to me that any computation on my home PC can be done with computations in said ring. But of course I'd have to prove that formally if I wrote a paper. I can already write conditional assignments of a memory slot (element of $\Bbb{Z}_p$), as the value of a polynomial in $\Bbb{Z}_p[x_1, \dots, x_k]$.

It's hard to find literature on this, but to me it seems so obvious that this is a nice approach and I'm shocked that no one's considered this yet. Or have they? Links please...

share|improve this question

closed as primarily opinion-based by D.W., Patrick87 Apr 16 at 17:11

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise.If this question can be reworded to fit the rules in the help center, please edit the question.

2  
Are you familiar with the RAM machine model? It is more realistic than the Turing machine model, in some respects. (It has nothing to do with rings, which probably aren't very relevant here anyway.) –  D.W. Apr 16 at 1:26
    
@D.W. I disagree. Rings are a well-understood algebraic structure and any time you can "algebratize" something you can solve new problems. –  Enjoys Math Apr 16 at 1:28
1  
EnjoysMaths, we expect you to do a serious amount of research before asking. Try Google, or some standard textbooks on algorithms and complexity theory. Trust me, there's lots of information about the RAM machine model out there. Don't be lazy. You asked for a link just 1 minute after I post about the RAM machine model; you need to put in more effort yourself. Only ask questions about topics that you really want to know the answer to. –  D.W. Apr 16 at 1:30
1  
@D.W. Did modern algebraic geometers have to fully comprehend old-fashioned geometry techniques? No, not at all. –  Enjoys Math Apr 16 at 1:31
3  
EnjoyMaths, if you are not familiar with the RAM model (a basic concept in this area), one might reasonably ask whether you have enough background knowledge to have a well-informed opinion about whether rings are very relevant here. In any case, take this comment as an opportunity to edit your question to make the connection to rings clearer, if you think that connection is essential. Personally, I still think they might be tangential. Anyway, frankly, I'm not sure there's much point in asking here, if you're going to reject the reactions and advice you get here. –  D.W. Apr 16 at 1:32

1 Answer 1

As D.W. mentions in the comments, the model you are looking for is the RAM machine. In fact, there are several different models, and I recommend the following recent paper of Fürer's for a good overview.

In contrast to what you describe, the correct ring is $\mathbb{Z}_{2^n}$, where $n$ is the width of registers – up to 512 bits in future Intel processors. The exact value of $n$ doesn't matter at all as long as it's constant, since in computational complexity we are always interested in time and space complexity up to a multiplicative constant. Therefore, to make matters interesting, the RAM models described above let $n$ depend on the input size.

Regarding finitude of memory, this is captured, to some extent, by space constraints – polynomial space (or linear/quasilinear space) for algorithms working on normal data, logarithmic space (or polylogarithmic space) for algorithms working on big data; there are also streaming models for even less space. Restricting the space altogether would be destructive since then all deterministic algorithms would terminate in constant time – to make sense of asymptotics, we must allow space to grow with input size.

share|improve this answer

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