# Can you embed a Turing Machine into the Pi calculus with just one replication operator?

See title. If it is not universal, then how is the power of the pi calculus with this restriction characterized?

• Not sure why this is voted down, this is an interesting question. @Timothy why do you think that you need more than one replication? Such questions are subtle, and depend on exactly the variant of pi-calcululs used. See for a start: On Recursion, Replication and Scope Mechanisms in Process Calculi by Aranda et al. Jul 13 at 9:39
• @MartinBerger Thank you for showing interest in my question. Please consider taking a look at the construction I have provided in my answer, hopefully you will find it also interesting. Jul 15 at 1:55

I found that the answer is yes, you can construct a Turing Machine in the Pi calculus with just one replication operator. Here is how I constructed the tape for a Turing machine using the syntax of this interpreter.

(!(choose
choose
when write(new_value) then head<new_value, left, right>;
when move_left(unused) then
new (new_right) (
left(new_value, new_left) head<new_value, new_left, new_right> ;
| cell<value, new_right, right> ; )
when move_right(unused) then
new (new_left) (
right(new_value, new_right) head<new_value, new_left, new_right> ;
| cell<value, new_left, left> ; )
end
when cell(value, top, bottom) then top<value, bottom> ;
when tape_end(channel) then
new (new_channel) (channel<blank, new_channel> tape_end<new_channel> ;)
end))
|
(new (left) new (right) tape_end<left> head<blank, left, right> tape_end<right>;)


To complete the Turing machine you just need to add the finite state machine to interact with this tape on the channels "read", "write", "move_left", and "move_right". This can be done by adding a "when" clause listening on its own channel for each state of the finite state machine, which then signals/queries the tape and signals the appropriate next state of the finite state machine.

One interesting property of this solution is that it does not make use of recursive channel types, which the second edition of Practical Foundations for Programming Languages by Robert Harper suggests is required for the Pi Calculus to be universal.