Closed-form analytic maps in one and two dimensions can simulate universal Turing machines

被引：47

作者：

Koiran, P

Moore, C

机构：

[1] Santa Fe Inst, Santa Fe, NM 87501 USA

[2] Ecole Normale Super Lyon, Lab Informat Parallelisme, F-69364 Lyon 07, France

来源：

THEORETICAL COMPUTER SCIENCE | 1999年 / 210卷 / 01期

关键词：

D O I：

10.1016/S0304-3975(98)00117-0

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show closed-form analytic functions consisting of a finite number of trigonometric terms can simulate Turing machines, with exponential slowdown in one dimension or in real time in two or more. (C) 1999-Elsevier Science B.V. All rights reserved.

引用

页码：217 / 223

页数：7

共 14 条

[1] REACHABILITY ANALYSIS OF DYNAMICAL-SYSTEMS HAVING PIECEWISE-CONSTANT DERIVATIVES [J].

ASARIN, E ;

MALER, O ;

PNUELI, A .

THEORETICAL COMPUTER SCIENCE, 1995, 138 (01) :35-65

[2] FUNCTIONAL-EQUATIONS ASSOCIATED WITH CONGRUENTIAL FUNCTIONS [J].

BURCKEL, S .

THEORETICAL COMPUTER SCIENCE, 1994, 123 (02) :397-406

[3]

CONWAY JH, 1972, P 1972 NUMB THEOR C, P49

[4] COMPUTABILITY WITH LOW-DIMENSIONAL DYNAMICAL-SYSTEMS [J].

KOIRAN, P ;

COSNARD, M ;

GARZON, M .

THEORETICAL COMPUTER SCIENCE, 1994, 132 (1-2) :113-128

[5]

Koiran P., 1993, THESIS ECOLE NORMALE

[6] THE 3X+1 PROBLEM AND ITS GENERALIZATIONS [J].

LAGARIAS, JC .

AMERICAN MATHEMATICAL MONTHLY, 1985, 92 (01) :3-23

[7]

Lindgren K., 1990, Complex Systems, V4, P299

[8] BUSY BEAVER COMPETITION AND COLLATZ-LIKE PROBLEMS [J].

MICHEL, P .

ARCHIVE FOR MATHEMATICAL LOGIC, 1993, 32 (05) :351-367

[9]

Minsky M. L., 1967, COMPUTATION FINITE I

[10] GENERALIZED SHIFTS - UNPREDICTABILITY AND UNDECIDABILITY IN DYNAMIC-SYSTEMS [J].

MOORE, C .

NONLINEARITY, 1991, 4 (02) :199-230

← 1 2 →