4 ms·
Computer science assumes that the code is run on a machine with a very specific set of operations since otherwise you wouldn't be able to calculate time complex
by Klockan 10y ago
Computer science assumes that the code is run on a machine with a very specific set of operations since otherwise you wouldn't be able to calculate time complexity. The set of operations were deliberately chosen to be a reasonable abstraction of a modern computer. Thus computer science would look very differently if computers had different capabilities.
For example, lets say that a new computer could switch places of two blocks of memory in constant time no matter their sizes. That would completely revolutionize computer science since many of our old results hinges on the fact that moving memory takes linear time.
- Ar-Curunir 10y agoThe extended Turing thesis says that whatever is efficiently computable in one "reasonable" model of computation, is also efficiently computable in another reasonable model of computation. Of course, the truth of this thesis has been called into question with the advent of quantum computers, but it holds otherwise.