On the computational strength of pure ambient calculi
File(s)DTR03-10.pdf (472.49 KB)
Published version
Author(s)
Maffeis, Sergio
Type
Report
Abstract
Cardelli and Gordon's calculus of Mobile Ambients has attracted widespread interest
as a model of mobile computation. The standard calculus is quite rich, with a variety
of operators, together with capabilities for entering, leaving and dissolving ambi-
ents. The question arises of what is a minimal Turing-complete set of constructs.
Previous work has established that Turing completeness can be achieved without
using communication or restriction. We show that it can be achieved merely using
movement capabilities (and not dissolution). We also show that certain smaller sets
of constructs are either terminating or have decidable termination.
as a model of mobile computation. The standard calculus is quite rich, with a variety
of operators, together with capabilities for entering, leaving and dissolving ambi-
ents. The question arises of what is a minimal Turing-complete set of constructs.
Previous work has established that Turing completeness can be achieved without
using communication or restriction. We show that it can be achieved merely using
movement capabilities (and not dissolution). We also show that certain smaller sets
of constructs are either terminating or have decidable termination.
Date Issued
2003-01-01
Citation
Departmental Technical Report: 03/10, 2003, pp.1-54
Publisher
Department of Computing, Imperial College London
Start Page
1
End Page
54
Journal / Book Title
Departmental Technical Report: 03/10
Copyright Statement
© 2003 The Author(s). This report is available open access under a CC-BY-NC-ND (https://creativecommons.org/licenses/by-nc-nd/4.0/)
Publication Status
Published
Article Number
03/10