Simulations between Programs as Cellular Automata
Simulations between Programs as Cellular Automata
复制标题
作为元胞自动机的程序之间的模拟
DOI：
10.1007/3-540-63255-7_9
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
Paul R. Humenn
中科院分区：
文献类型：
--
作者：
H. A. Blair;Fred Dushin;Paul R. Humenn
我们在适当的有向图上给出了元胞自动机，并证明了任何覆盖的正常逻辑程序都是元胞自动机。将程序视为元胞自动机将注意力从Herbrand模型类转移到Herbrand解释轨道。轨道捕获程序的声明性、模型理论意义以及它们的推理行为。逻辑上和有意的不同程序可以产生相互模拟的轨道。作为元胞自动机的程序的时空图有力地展示了这种行为的简单例子。将程序解释为元胞自动机导致了用霍恩子句程序模拟任何覆盖程序的通用方法。这意味着霍恩计划的轨道完全代表了覆盖正常计划的轨道。
We present cellular automata on appropriate digraphs and show that any covered normal logic program is a cellular automaton. Seeing programs as cellular automata shifts attention from classes of Herbrand models toorbitsof Herbrand interpretations. Orbits capture both the declarative, model-theoretic meaning of programs as well as their inferential behavior. Logically and intentionally different programs can produce orbits that simulate each other. Simple examples of such behavior are compellingly exhibited with space-time diagrams of the programs as cellular automata. Construing a program as a cellular automaton leads to a general method for simulating any covered program with a Horn clause program. This means that orbits of Horn programs are completely representative of orbits of covered normal programs.