Computational complexity: Difference between revisions

Revision as of 03:24, 6 April 2020

Revision as of 03:25, 6 April 2020

Line 43:

A [[deterministic model]] of computation is a model of computation such that the successive states of the machine and the operations to be performed are completely determined by the preceding state. Historically, the first deterministic models were [[μ-recursive function|recursive function]]s, [[lambda calculus]], and [[Turing machine]]s. The model of [[Random access machine]]s (also called RAM-machines) is also widely used, as a closer counterpart to real [[computer]]s.

When the model of computation is not specified, it is generally theassumed modelto be ofa [[multitape Turing machine]]s. For most algorithms, the time complexity is the same on multitape Turing machines andas on RAM-machines, although, some care may be needed in storinghow data foris stored in memory to gettingget this equivalence.

===Non-deterministic computation===