Wiring a Turing Machine in the Cellular Automaton and the Surjectivity Problem for a Parallel Map

スポンサーリンク

概要

• 論文の詳細を見る

• In [18], a sketch of the proof was given as a short note for the unsolvability of the decision problem for the surjectivity of parallel maps induced by d-dimensional cellular automata (d>1). This paper provides a full proof for the theorem. Wiring mechanism, which provides an essential idea in the proof, of Turing machines in cellular automata is also given. Rationale for the definitions of the simulators employed in the mechanism are also provided.

• 1985-03-30

著者

• Yaku T

  Nihon Univ.

• Yaku Takeo

  Department Of Computer Science And System Analysis Nihon University

関連論文

• Visual Software Development Environment Based on Graph Grammars
• Generation of the Hichart Program Diagrams
• Partitions of Graphs into Chains of the Minimum Block Number
• A Control Structure between Iteration and Recursion
• Nicely Drawing Tree-Structured Diagrams on the Euclidian Plane
• Wiring a Turing Machine in the Cellular Automaton and the Surjectivity Problem for a Parallel Map

スポンサーリンク