Machine models and simulations

作者: Peter van EMDE BOAS

DOI: 10.1016/B978-0-444-88071-0.50006-0

关键词:

摘要: Publisher Summary This chapter discusses machine models and simulations. The existence of many different does not necessarily mean that there are no uniform underlying notions computational complexity. In the theory computation, a large variety formal calculi has been proposed to capture notion effective computation. lead proliferation computation theories, because basic fact formalisms have all shown be equivalent in following sense—each one formalism can simulated by other formalism. From equivalence, it concluded if problem is unsolvable particular model, then also for formalized computing devices which this model related mutual simulation. Consequently solvability really depend on used. themselves remain shelf, used when needed.

参考文章(107)
Mark Jerrum, The complexity of finding minimum-length generator sequences Automata, Languages and Programming. pp. 270- 280 ,(1984) , 10.1007/3-540-13345-3_24
P. van Emde Boas, The second machine class: models of parallelism Parallel computers and computations. pp. 133- 161 ,(1985)
J. M. Robson, The Complexity of Go. ifip congress. pp. 413- 417 ,(1983)
Juraj Wiedermann, Deterministic and Nondeterministic Simulation of the RAM by the Turing Machine. ifip congress. pp. 163- 168 ,(1983)
H-J Stoß, Zwei-Band Simulation von Turingmaschinen Computing. ,vol. 7, pp. 222- 235 ,(1971) , 10.1007/BF02242349
Peter van Emde Boas, The second machine class 2, an encyclopedic view on the parallel computation thesis Banach Center Publications. ,vol. 21, pp. 235- 256 ,(1988) , 10.4064/-21-1-235-256
Ming Li, Luc Longpré, Paul MB Vitányi, None, The Power of the Queue structure in complexity theory annual conference. pp. 218- 233 ,(1986) , 10.1007/3-540-16486-3_101
David Harel, Recurring dominoes: making the highly undecidable highly understandable North-holland Mathematics Studies. ,vol. 102, pp. 51- 71 ,(1985) , 10.1016/S0304-0208(08)73075-5
Arnold Schönhage, On the Power of Random Access Machines international colloquium on automata, languages and programming. pp. 520- 529 ,(1979) , 10.1007/3-540-09510-1_42
Wolfgang Maass, Georg Schnitger, An optimal lower bound for Turing machines with one work tape and a two-way input tape structure in complexity theory annual conference. pp. 249- 264 ,(1986) , 10.1007/3-540-16486-3_103