# Is there a model of computation, that tries to be realistic? [closed]

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

-

## closed as primarily opinion-based by D.W.♦, Patrick87Apr 16 '14 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.

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 '14 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 '14 at 1:28
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 '14 at 1:30
@D.W. Did modern algebraic geometers have to fully comprehend old-fashioned geometry techniques? No, not at all. – Enjoys Math Apr 16 '14 at 1:31
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 '14 at 1:32

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.