An Intensional Concurrent Faithful Encoding of Turing Machines

Thomas Given-Wilson 1
1 COMETE - Concurrency, Mobility and Transactions
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : The benchmark for computation is typically given as Turing computability; the ability for a computation to be performed by a Turing Machine. Many languages exploit (indirect) encodings of Turing Machines to demonstrate their ability to support arbitrary computation. However, these encodings are usually by simulating the entire Turing Machine within the language, or by encoding a language that does an encoding or simulation itself. This second category is typical for process calculi that show an encoding of lambda-calculus (often with restrictions) that in turn simulates a Turing Machine. Such approaches lead to indirect encodings of Turing Machines that are complex, unclear, and only weakly equivalent after computation. This paper presents an approach to encoding Turing Machines into intensional process calculi that is faithful, reduction preserving, and structurally equivalent. The encoding is demonstrated in a simple asymmetric concurrent pattern calculus before generalised to simplify infinite terms, and to show encodings into Concurrent Pattern Calculus and Psi Calculi.
Type de document :
Communication dans un congrès
Ivan Lanese and Alberto Lluch-Lafuente and Ana Sokolova and Hugo Torres Vieira. 7th Interaction and Concurrency Experience (ICE 2014), Jun 2014, Berlin, Germany. Open Publishing Association, 166, pp.21-37, 2014, EPTCS. 〈10.4204/EPTCS.166.4〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00987594
Contributeur : Catuscia Palamidessi <>
Soumis le : lundi 28 juillet 2014 - 16:27:19
Dernière modification le : jeudi 9 février 2017 - 15:11:25
Document(s) archivé(s) le : mardi 25 novembre 2014 - 19:30:36

Fichiers

turing.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Thomas Given-Wilson. An Intensional Concurrent Faithful Encoding of Turing Machines. Ivan Lanese and Alberto Lluch-Lafuente and Ana Sokolova and Hugo Torres Vieira. 7th Interaction and Concurrency Experience (ICE 2014), Jun 2014, Berlin, Germany. Open Publishing Association, 166, pp.21-37, 2014, EPTCS. 〈10.4204/EPTCS.166.4〉. 〈hal-00987594v3〉

Partager

Métriques

Consultations de
la notice

495

Téléchargements du document

120