FAST SIMULATION OF TURING-MACHINES BY RANDOM-ACCESS MACHINES

被引：7

作者：

KATAJAINEN, J ^{[1
]}

VANLEEUWEN, J ^{[1
]}

PENTTONEN, M ^{[1
]}

机构：

[1] UNIV UTRECHT,DEPT COMP SCI,3508 TA UTRECHT,NETHERLANDS

来源：

SIAM JOURNAL ON COMPUTING | 1988年 / 17卷 / 01期

关键词：

Computer Metatheory;

D O I：

10.1137/0217005

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We prove that a T(n) time-bounded, S(n) space-bounded and U(n) output-length-bounded Turing machine can be simulated in O(T(n)+(n+U(n)) log log S(n)) time by a random access machine (with no multiplication or division instructions) under the logarithmic cost criterion.

引用

页码：77 / 88

页数：12

共 16 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER, V1st

[2]

Cook S. A., 1973, Journal of Computer and System Sciences, V7, P354, DOI 10.1016/S0022-0000(73)80029-7

[3]

DEITEL HM, 1984, INTRO OPERATING SYST

[4] SPEEDUPS OF DETERMINISTIC MACHINES BY SYNCHRONOUS PARALLEL MACHINES [J].

DYMOND, PW ;

TOMPA, M .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1985, 30 (02) :149-161

[5]

Fischer M.J., 1974, SIAM AMS P, V7, P113

[6] TIME-SPACE-OPTIMAL STRING MATCHING [J].

GALIL, Z ;

SEIFERAS, J .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1983, 26 (03) :280-294

[7]

Hopcroft J, 1975, 16 ANN S FDN COMP SC, P57

[8]

Hopcroft J.E., 1979, INTRO AUTOMATA THEOR

[9]

LOUI MC, 1984, J COMPUT SYST SCI, V28, P359, DOI 10.1016/0022-0000(84)90019-9

[10]

PAUL W, 1978, KOMPLEXITATSTHEORIE

← 1 2 →