SIMULATION OF TURING-MACHINES BY A REGULAR REWRITE RULE

被引：18

作者：

DAUCHET, M

机构：

[1] LIFL (CNRS, U.R.A. 369), University of Lille-Flanders-Artois, UFR IEEA

来源：

THEORETICAL COMPUTER SCIENCE | 1992年 / 103卷 / 02期

关键词：

D O I：

10.1016/0304-3975(92)90022-8

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We prove that for any Turing machine, there exists a regular (i.e. left-linear and nonoverlapping, also called orthogonal) and variable-preserving rule that simulates its behaviour. The main corollary is the undecidability of termination for such a rule.

引用

页码：409 / 420

页数：12

共 7 条

[1] THUE SYSTEMS AS REWRITING-SYSTEMS
BOOK, RV
[J]. JOURNAL OF SYMBOLIC COMPUTATION, 1987, 3 (1-2) : 39 - 68
[2] DAUCHET M, 1988, LECT NOTES COMPUT SC, V324, P262, DOI 10.1007/BFb0017149
[3] DAUCHET M, 1989, LECT NOTES COMPUT SC, V355, P109
[4] TERMINATION OF REWRITING
DERSHOWITZ, N
[J]. JOURNAL OF SYMBOLIC COMPUTATION, 1987, 3 (1-2) : 69 - 116
[5] Dershowitz Nachum., 1990, HDB THEORETICAL COMP, P243
[6] WEIGHTED GRAPHS - A TOOL FOR STUDYING THE HALTING PROBLEM AND TIME-COMPLEXITY IN TERM REWRITING-SYSTEMS AND LOGIC PROGRAMMING
DEVIENNE, P
[J]. THEORETICAL COMPUTER SCIENCE, 1990, 75 (1-2) : 157 - 215
[7] JOUANNAUD JP, 1987, J SYMB COMPUT, V3, P2

← 1 →