One of the fundamental results in computational complexity theory is the linear speed-up theorem for turing machines. This theorem states that for every multitape turing machine of time complexity T(n)>n and for every constant c>0 there is a multitape machine that accepts the same language in time cT(n). One question is, could linear speed-up be a pathological artifact of the turing machine model? This project involves the determination of which properties are not artifacts of turing machines. Specifically, the computational complexity of the random access machine (RAM) and two related models, the storage modification machine (SMM) and the parallel random access machine (PRAM) will be investigated.
