patternMinor
Relation between RAM and Turing machine
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.
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.
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.