Skip to Main content Skip to Navigation
Conference papers

An Intensional Concurrent Faithful Encoding of Turing Machines

Thomas Given-Wilson 1
1 COMETE - Concurrency, Mobility and Transactions
Inria Saclay - Ile de France, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
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.
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-00987594
Contributor : Catuscia Palamidessi <>
Submitted on : Monday, July 28, 2014 - 4:27:19 PM
Last modification on : Monday, December 14, 2020 - 5:03:05 PM
Long-term archiving on: : Tuesday, November 25, 2014 - 7:30:36 PM

Files

turing.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Thomas Given-Wilson. An Intensional Concurrent Faithful Encoding of Turing Machines. 7th Interaction and Concurrency Experience (ICE 2014), Jun 2014, Berlin, Germany. pp.21-37, ⟨10.4204/EPTCS.166.4⟩. ⟨hal-00987594v3⟩

Share

Metrics

Record views

740

Files downloads

490