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

• 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, 2014 at 1:26
• 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, 2014 at 1:30
• @D.W. Did modern algebraic geometers have to fully comprehend old-fashioned geometry techniques? No, not at all. Apr 16, 2014 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, 2014 at 1:32
• @EnjoysMath: TMs have never been a technology, nor are they obsolete. I recommend you widen your horizon by reading this. That said, there already is a perfect model for real computers: finite automata. They are not very useful for deriving properties and algorithms for real computers, but well. For that, we have other models. All models are designed to model some trait of real systems, but they also all simplify (for good reason). Apr 16, 2014 at 12:20

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.