HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Relation between RAM and Turing machine

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
andbetweenmachineturingrelationram

Problem

Denote $D$ a set of finite sequences of integers. In Papadimitriou's "Computational Complexity" in theorem 2.5 it is proved that if a RAM program $\Pi$ computes a function $\phi$ from $D$ to integers in time $f(n)$, then there is a $7$-string Turing machine $M$, which computes $\phi$ in time $O(f(n)^3)$.

Consider the following example: $\phi(S)$ is a sum of first two numbers of a finite sequence $S$, or $0$, if $|S| < 2$. It seems to me that a RAM, defined in Papadimitriou's book computes $\phi$ in time $O(1)$. Thought, any Turing machine, computing $\phi$, should work for at least linear time (we can take an input of length $n$ with only two numbers in sequence). I don't see how to cope with this contradiction.

Could you please describe me, where I am wrong? Thanks a lot.

Solution

You're right, there is a missing assumption that f(n) is at least O(n).
Indeed, the last line of the proof state that the operand are of size O(f(n)), while what has been proven before is O(f(n)+l(I)+l(B)). Since l(I) is O(n), the hypothesis is needed for this simplification.

Context

StackExchange Computer Science Q#24361, answer score: 2

Revisions (0)

No revisions yet.